CF2032F Peanuts

拥有神奇豆茎的 Jack 最近收集了许多花生。最终，他得到了 $n$ 袋花生，这些花生袋从左到右依次编号为 $1$ 到 $n$。第 $i$ 袋中有 $a_i$ 个花生。 Jack 和他的童年好友 Alice 决定围绕这些花生玩一个游戏。首先，Alice 会将这些花生袋分成若干个盒子；每个盒子必须包含至少一个连续的花生袋，并且每个花生袋只能属于一个盒子。与此同时，Alice 不会改变盒子的顺序，也就是说，盒子的编号按照其中花生袋的编号递增排列。 之后，Alice 和 Jack 将轮流进行操作，Alice 先手。 每一回合，当前玩家必须从最左边的非空盒子（即最左边至少有一个非空花生袋的盒子）中的某一个花生袋中取出正数个花生。换句话说，只有当前面所有盒子都已经没有花生时，玩家才能从更右边的盒子中取花生。无法进行有效操作的玩家判负。 由于 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$ 取模后的结果。

在第一个测试用例中，Alice 获胜的唯一分盒方式是将花生袋分为两个盒子：$([1, 2], [3])$（第一个盒子包含第 1 和第 2 袋，第二个盒子包含第 3 袋）。Alice 通过从第二袋取走所有花生获胜，剩下 $([1], [3])$。Jack 被迫从第一个盒子中唯一的袋子取花生，Alice 就能取走第二个盒子剩下的花生。 在第二个测试用例中，Alice 获胜的分盒方式有 $([1], [2, 3, 1])$、$([1, 2, 3, 1])$、$([1, 2], [3], [1])$ 和 $([1, 2], [3, 1])$。 在第三个测试用例中，无论 Alice 如何分盒，她都能获胜。 在第四个测试用例中，无论 Alice 如何分盒，她都无法获胜。 由 ChatGPT 4.1 翻译