← 返回题目列表

Codeforces · 2043/F

F. 尼姆

中文机器翻译题面 查看原题

回忆一下“Nim”游戏的规则。有 $$$n$$$ 堆石头,其中第 $$$i$$$ 堆最初包含一定数量的石头。两名玩家轮流选择一个非空堆并从中取出任何正数(严格大于 $$$0$$$)的石子。无法采取行动的玩家输掉游戏。

给定一个数组 $$$a$$$,由 $$$n$$$ 整数组成。 Artem 和 Ruslan 决定在该阵列的各个部分上扮演 Nim 的角色。每个 $$$q$$$ 轮都由段 $$$(l_i, r_i)$$$ 定义,其中元素 $$$a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$$$ 代表石子堆的大小。

游戏开始前,鲁斯兰可以从所选部分移除任意数量的桩。然而,至少必须保留一堆,因此在一轮中他最多可以移除 $$$(r_i - l_i)$$$ 堆。他被允许移除 $$$0$$$ 堆。移除后,游戏在该段内剩余的桩上进行。

所有轮次都是独立的:一轮中所做的更改不会影响原始数组或任何其他轮次。

鲁斯兰想要尽可能多地移除一堆牌,这样总是先走一步的阿乔姆就会输。

对于每一轮,确定:

1. Ruslan 可以移除的最大桩数;
2.数量方式选择最大拆除桩数。

如果存在索引 $$$i$$$ 使得索引 $$$i$$$ 处的堆以一种方式被删除,但以另一种方式则不被删除,则两种方式被认为是不同的。由于路数可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。

如果Ruslan无法确保Artem在特定回合中失败,则该回合输出-1。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 10^5$$$) - 数组的大小和需要计算答案的段数。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 50$$$) — 初始数组的元素。

接下来的 $$$q$$$ 行的第 $$$i$$$ 行包含两个整数 $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — 在第 $$$i$$$ 轮中男孩们想要玩游戏的线段的边界。

输出

每轮:

- 如果 Ruslan 能够获胜,则打印两个整数——可以移除的最大桩数,以及移除最大桩数的方法数,以 $$$998\,244\,353$$$ 为模;
- 否则打印-1。

示例

输入 #1

9 5
0 1 2 1 3 4 5 6 0
1 5
2 5
3 5
4 5
1 9

输出 #1

4 1
2 1
0 1
-1
8 2