#P13665. [ARC144F] Arithmetic Sequence Nim

    ID: 12867 传统题 3000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3200NOI/NOI+/CTSSG 函数mex 计算异或合并扩展欧几里得算法模逆元坐标变换向下取整与向上取整二分查找

[ARC144F] Arithmetic Sequence Nim

题目描述

给定一个正整数 mm,一个非负整数 aa(0≤a<m0 \le a < m),以及一个正整数序列 A=(A1,…,AN)A = (A_1, \ldots, A_N)。

定义一个正整数集合 XX,这个集合中的元素满足 x>0x > 0 且 x≡a(modm)x \equiv a \pmod{m}。

在这个游戏中,先手玩家太郎君和后手玩家次郎君轮流操作。游戏从太郎君开始进行,操作如下:

  • 选择一个下标 ii(1≤i≤N1 \le i \le N)和一个正整数 x∈Xx \in X 的组合 (i,x)(i, x),要求 x≤Aix \le A_i。然后将 AiA_i 更改为 Ai−xA_i - x。如果找不到符合条件的 (i,x)(i, x) 组合,当前回合的玩家即输掉游戏。

你的任务是计算,在太郎君第一次操作中,能够选择的所有组合 (i,x)(i, x) 中,经双方均采取最佳策略后,能让太郎君赢得游戏的组合数量。请输出该数量对 998244353998244353 取模的结果。

输入格式

输入以如下格式从标准输入给出:

N m a A1 A2 … ANN\ m\ a\ A_1\ A_2\ \ldots\ A_N

输出格式

输出满足条件的首回合组合数对 998244353998244353 取模的结果。

输入输出样例 #1

输入 #1

3 1 0
5 6 7

输出 #1

3

输入输出样例 #2

输入 #2

5 10 3
5 9 18 23 27

输出 #2

3

输入输出样例 #3

输入 #3

4 10 8
100 101 102 103

输出 #3

0

输入输出样例 #4

输入 #4

5 2 1
111111111111111 222222222222222 333333333333333 444444444444444 555555555555555

输出 #4

943937640

说明/提示

  • 1≤N≤3×1051 \le N \le 3 \times 10^5
  • 0≤a<m≤1090 \le a < m \le 10^9
  • max⁡(1,a)≤Ai≤1018\max(1, a) \le A_i \le 10^{18}

示例解释 1

集合 X={1,2,3,4,5,…}X = \{1, 2, 3, 4, 5, \ldots\}。符合条件的组合有 (1,4)(1, 4), (2,4)(2, 4), (3,4)(3, 4),共 33 个。

示例解释 2

集合 X={3,13,23,33,43,…}X = \{3, 13, 23, 33, 43, \ldots\}。符合条件的组合有 (4,23)(4, 23), (5,3)(5, 3), (5,13)(5, 13),共 33 个。

示例解释 3

太郎君无论如何都无法赢得比赛,因此,符合条件的组合是 00 个。

示例解释 4

符合条件的组合有 833333333333334833333333333334 个,输出其对 998244353998244353 取模的结果。