Codeforces Round 983 (Div. 2) |
---|
Закончено |
Имея волшебную бобовую палку, Джек в последнее время собирал много арахисов. В конечном итоге он получил $$$n$$$ мешков с арахисом, удобно пронумерованных от $$$1$$$ до $$$n$$$ слева направо. В $$$i$$$-м мешке находится $$$a_i$$$ арахисов.
Джек и его подруга детства Алиса решили сыграть в игру с арахисом. Сначала Алиса делит мешки на несколько коробок; каждая коробка будет содержать ненулевое количество последовательных мешков, и каждый мешок, очевидно, будет лежать в ровно одной коробке. При этом Алиса не меняет порядок коробок, то есть коробки пронумерованы в порядке возрастания номеров мешков в них.
После этого Алиса и Джек будут по очереди делать ходы, при этом Алиса ходит первой.
На каждом ходе текущий игрок будет забирать положительное количество арахисов из ровно одного мешка, который лежит в самой левой непустой коробке (т.е. самой левой коробке, содержащей хотя бы один непустой мешок). Другими словами, если мы пронумеруем коробки слева направо, то каждый игрок может забирать арахисы из мешка в $$$j$$$-й коробке ($$$j \ge 2$$$) только в том случае, если в $$$(j - 1)$$$-й коробке не осталось арахисов. Игрок, который не может сделать допустимый ход, проигрывает.
Алиса уверена, что она выиграет, так как у нее есть преимущество в том, что она сама делит мешки на коробки. Она хочет знать, сколько существует способов разделить мешки на коробки в начале игры, чтобы она выиграла, предполагая, что оба игрока играют оптимально. Можете помочь ей с расчетами?
Поскольку результат может быть очень большим, выведите его по модулю $$$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$$$.
Для каждого набора входных данных выведите одно целое число — количество способов для Алисы разделить мешки на коробки в начале игры, чтобы гарантировать ее победу, предполагая, что оба игрока играют оптимально, по модулю $$$998\,244\,353$$$.
531 2 341 2 3 151 1 1 1 121 1101 2 3 4 5 6 7 8 9 10
1 4 16 0 205
В первом наборе входных данных единственный способ для Алисы выиграть — это разделить мешки на две коробки следующим образом: $$$([1, 2], [3])$$$ (первая коробка содержит первые два мешка, а вторая коробка содержит третий мешок). Алиса выигрывает, забирая оба арахиса из второго мешка, оставляя Джеку $$$([1], [3])$$$. Джек вынужден забрать единственный оставшийся арахис в первой коробке, что позволяет Алисе забрать оставшиеся в второй коробке.
Во втором наборе входных данных выигрышные разделения для Алисы — это $$$([1], [2, 3, 1])$$$, $$$([1, 2, 3, 1])$$$, $$$([1, 2], [3], [1])$$$ и $$$([1, 2], [3, 1])$$$.
В третьем наборе входных данных Алиса всегда выигрывает, независимо от того, как она разделяет мешки на коробки.
В четвертом наборе входных данных Алиса всегда проигрывает, независимо от того, как она разделяет мешки на коробки.
Название |
---|