/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 900 点
問題文
正整数 m, 非負整数 a (0\leq a < m) および正整数列 A = (A_1, \ldots, A_N) が与えられます．
正整数からなる集合 X を X = \{x>0\mid x\equiv a \pmod{m}\} により定めます．
先手太郎君と後手次郎君が対戦ゲームをします．ゲームでは先手太郎君の手番から始めて，交互に以下の操作を行います．
- 添字 i (1\leq i\leq N) と正整数 x\in X の組 (i,x) であって，x\leq A_i を満たすものをひとつ選ぶ．A_i を A_i - x に変更する．ただしそのような (i, x) が存在しないならば，手番のプレイヤーの負けとしてゲームを終了する．
先手太郎君が最初の手番に選ぶことができる (i, x) のうち，それ以降の手番で両者が最善を尽くした場合に先手太郎君が勝つことができるものの個数を 998244353 で割った余りを答えてください．
制約
- 1\leq N\leq 3\times 10^5
- 0\leq a < m\leq 10^9
- \max(1, a) \leq A_i\leq 10^{18}
入力
入力は以下の形式で標準入力から与えられます．
N m a A_1 A_2 \ldots A_N
出力
先手太郎君が最初の手番に選ぶことができる (i, x) のうち，それ以降の手番で両者が最善を尽くした場合に先手太郎君が勝つことができるものの個数を 998244353 で割った余りを出力してください．
入力例 1
3 1 0 5 6 7
出力例 1
3
X = \{1, 2, 3, 4, 5, \ldots\} です．条件を満たす (i,x) は (1,4), (2,4), (3,4) の 3 個です．
入力例 2
5 10 3 5 9 18 23 27
出力例 2
3
X = \{3, 13, 23, 33, 43, \ldots\} です．条件を満たす (i,x) は (4,23), (5,3), (5,13) の 3 個です．
入力例 3
4 10 8 100 101 102 103
出力例 3
0
先手太郎君は最善を尽くしても勝つことはできません．したがって条件を満たす (i, x) は 0 個です．
入力例 4
5 2 1 111111111111111 222222222222222 333333333333333 444444444444444 555555555555555
出力例 4
943937640
条件を満たす (i, x) は 833333333333334 個あります． 998244353 で割った余りを出力してください．
Score : 900 points
Problem Statement
You are given a positive integer m, a non-negative integer a (0\leq a < m), and a sequence of positive integers A = (A_1, \ldots, A_N).
A set X of positive integers is defined as X = \{x>0\mid x\equiv a \pmod{m}\}.
Alice and Bob will play a game against each other. They will alternate turns performing the following operation, with Alice going first:
- Choose a pair (i,x) of an index i (1\leq i\leq N) and a positite integer x\in X such that x\leq A_i. Change A_i to A_i - x. If there is no such (i, x), the current player loses and the game ends.
Find the number, modulo 998244353, of pairs (i, x) that Alice can choose in her first turn so that she wins if both players play optimally in subsequent turns.
Constraints
- 1\leq N\leq 3\times 10^5
- 0\leq a < m\leq 10^9
- \max(1, a) \leq A_i\leq 10^{18}
Input
Input is given from Standard Input in the following format:
N m a A_1 A_2 \ldots A_N
Output
Print the number, modulo 998244353, of pairs (i, x) that Alice can choose in her first turn so that she wins if both players play optimally in subsequent turns.
Sample Input 1
3 1 0 5 6 7
Sample Output 1
3
We have X = \{1, 2, 3, 4, 5, \ldots\}. Three pairs (i,x) satisfy the condition: (1,4), (2,4), (3,4).
Sample Input 2
5 10 3 5 9 18 23 27
Sample Output 2
3
We have X = \{3, 13, 23, 33, 43, \ldots\}. Three pairs (i,x) satisfy the condition: (4,23), (5,3), (5,13).
Sample Input 3
4 10 8 100 101 102 103
Sample Output 3
0
Alice cannot win even if she plays optimally. Thus, zero pairs (i,x) satisfy the condition.
Sample Input 4
5 2 1 111111111111111 222222222222222 333333333333333 444444444444444 555555555555555
Sample Output 4
943937640
833333333333334 pairs (i,x) satisfy the condition. Print the count modulo 998244353.