← 返回题目列表

AtCoder · arc144_f

F. 算术序列 Nim

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

分数: 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.