← 返回题目列表

Codeforces · 2032/F

F. 花生

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

杰克拥有神奇的豆茎,最近收集了很多花生。最终,他得到了 $$$n$$$ 袋花生,方便地从左到右编号为 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 个口袋里有 $$$a_i$$$ 花生。

杰克和他儿时的朋友爱丽丝决定围绕花生玩一个游戏。首先,爱丽丝将口袋分成几个盒子;每个盒子都有非零数量的连续口袋,并且每个口袋显然都属于一个盒子。同时,Alice 并没有改变盒子的顺序,即盒子按照盒子中口袋索引的升序进行编号。

之后,Alice和Jack将轮流轮流,Alice先走。

每回合,当前玩家将从属于最左边非空盒子(即最左边至少包含一个非空口袋)的一个口袋中取出正数的花生。换句话说,如果我们从左到右对盒子进行编号,那么只有当第 $$$(j - 1)$$$ 个盒子没有剩下花生时,每个玩家才能从第 $$$j$$$ 个盒子 ($$$j \ge 2$$$) 的口袋里取出花生。无法做出有效动作的玩家失败。

Alice确信她会赢,因为她有自己将口袋分成盒子的优势。因此,她想知道在游戏开始时她有多少种方法可以将花生分入盒子中,以便在双方都发挥最佳的情况下获胜。你能帮她计算一下吗?

由于结果可能非常大,因此输出它对 $$$998\,244\,353$$$ 取模。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — 口袋的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) - 每个口袋中花生的数量。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,输出一个整数 - Alice 在游戏开始时将口袋分成盒子以保证获胜的方式数量,假设两个玩家都发挥最佳,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

5
3
1 2 3
4
1 2 3 1
5
1 1 1 1 1
2
1 1
10
1 2 3 4 5 6 7 8 9 10

输出 #1

1
4
16
0
205

注意

在第一个测试用例中,Alice 获胜的唯一方法是将口袋分成两个盒子,如下所示:$$$([1, 2], [3])$$$(第一个盒子包含前两个口袋,第二个盒子包含第三个口袋)。爱丽丝从第二个口袋里拿走了两个花生,从而获胜,给杰克留下了 $$$([1], [3])$$$。杰克被迫拿走第一个盒子里剩下的花生,这使得爱丽丝可以拿走第二个盒子里剩下的花生。

在第二个测试用例中,Alice 的获胜分区是 $$$([1], [2, 3, 1])$$$、$$$([1, 2, 3, 1])$$$、$$$([1, 2], [3], [1])$$$ 和 $$$([1, 2], [3, 1])$$$。

在第三个测试用例中,无论 Alice 如何将口袋分成盒子,她总是赢。

在第四个测试用例中,无论Alice如何将口袋分成盒子,她总是输。