201445: [AtCoder]ARC144 F - Arithmetic Sequence Nim

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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$.

Input

加入题单

上一题 下一题 算法标签: