No.2144 MM
タグ : / 解いたユーザー数 65
作問者 :
milkcoffee
/ テスター :
first_vil
nok0
Problem Statement
You are given positive integers $N,M$.
For the given $N,M$, a good sequence is defined as follows.
- It has length $N$, and each element is at least $0$ and at most $M-2$ .
- By repeating the following operation (any number of times), all elements can be made multiples of $M$.
- Choose $2$ adjacent elements and add $1$ to each of them.
You are given a sequence $A$ of non-negative integers of length $N$. Determine whether it is a good sequence.
Also, if it is a good sequence, find its position in lexicographic order among the good sequences, modulo $998244353$.
Input
$N$ $M$ $A_1$ $A_2$ $\cdots$ $A_N$
- $2 \leq N \leq 2 \times 10^5$
- $3 \leq M \leq 10^6$
- $0 \leq A_i \leq M-2$ $(1 \leq i \leq N)$
- All input values are integers.
Output
If the sequence $A$ of non-negative integers is a good sequence, output as an integer its position in lexicographic order among the good sequences, modulo $998244353$.
If it is not a good sequence, output -1.
Sample
Sample 1
Input
3 5 2 0 3
Output
8
For $N=3,M=5$, listing the good sequences in lexicographic order up to the $8$-th gives the following.
$(0,0,0),(0,1,1),(0,2,2),(0,3,3),(1,1,0),(1,2,1),(1,3,2),(2,0,3)$
Performing the operation "add $1$ to the $1,2$-th elements" $3$ times on $(2,0,3)$ gives $(5,3,3)$.
Then, performing the operation "add $1$ to the $2,3$-th elements" $2$ times on $(5,3,3)$ gives $(5,5,5)$.
Since all elements could be made multiples of $5$, $(2,0,3)$ is a good sequence.
Sample 2
Input
2 1000000 0 1
Output
-1
It is impossible to make both the $1,2$-th elements multiples of $1000000$, so $(0,1)$ is not a good sequence.
Sample 3
Input
15 840067 703190 347257 169927 111976 170201 451648 473561 341367 803725 263056 785072 155864 274520 420688 391794
Output
293678726
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。