分数: 900 点
问题陈述
给你一个正整数 m,一个非负整数 a (0\leq a < m),以及正整数序列 A = (A_1, \ldots, A_N).
一套 正整数的 X 定义为 X = \{x>0\mid x\equiv a \pmod{m}\}.
Alice 和 Bob 将互相玩游戏。他们将轮流执行以下操作,爱丽丝先行:
- 选择一对 索引的 (i,x) 一个索引的 i (1\leq i\leq N) 和一个正整数 x\in X 这样 x\leq A_i。改变 A_i to A_i - x。如果没有这样的 (i, x),当前玩家失败,游戏结束。
求模数 998244353,成对 (i, x) 爱丽丝可以在她的第一回合中选择,这样如果两个玩家在随后的回合中都表现最佳,她就获胜。
约束
- 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
输出
打印数字,模数 998244353,成对 (i, x) 爱丽丝可以在她的第一回合中选择,这样如果两个玩家在随后的回合中都表现最佳,她就获胜。
示例输入 1
3 1 0 5 6 7
示例输出 1
3
我们有 X = \{1, 2, 3, 4, 5, \ldots\}。三对 (i,x) 满足条件: (1,4), (2,4), (3,4).
示例输入 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
4 10 8 100 101 102 103
示例输出 3
0
Alice 即使发挥最佳也无法获胜。因此,零对 (i,x) 满足条件。
示例输入 4
5 2 1 111111111111111 222222222222222 333333333333333 444444444444444 555555555555555
示例输出 4
943937640
833333333333334 对 (i,x) 满足条件。打印计数模数 998244353.