No.2653 [Cherry 6th Tune] Re: start! (Make it Zero!)
タグ : / 解いたユーザー数 44
作問者 : 👑
Kazun
/ テスター :
👑 Introduction
Shall we start over again, from zero?
Problem Statement
Make it Zero!
You are given an integer sequence $B=(B_1, \dots, B_N)$ of length $N$. Each term is an integer at least $0$ and less than $M$. It is also guaranteed that $\displaystyle \sum_{i=1}^N B_i$ is a multiple of $M$.
Here, a non-empty integer sequence whose terms are all $0$ is called a zero sequence.
Make $B$ a zero sequence by repeating the following operation $0$ or more times.
- Operation: Choose $2$ consecutive integers in $B$ and delete them. Then, letting $x,y$ be the $2$ deleted integers, insert the remainder of $(x+y)$ divided by $M$ at their original position.
What is the minimum number of operations required to make $B$ a zero sequence?
It can be proved that, under the constraints of this problem, it is possible to make $B$ a zero sequence by repeating the operation $0$ or more times.
You are given an integer sequence $X=(X_1, \dots, X_N)$ of length $N$. Each term of $X$ is either an integer at least $0$ and less than $M$, or $-1$.
Consider the integer sequences $A=(A_1, \dots, A_N)$ of length $N$ satisfying the following $3$ conditions. Find the sum of the answers to Make it Zero! over all such $A$, modulo $998244353$.
- For $i=1,2, \dots, N$, $0 \leq A_i \lt M$.
- For $i=1,2, \dots, N$, if $X_i \neq -1$, then $A_i=X_i$.
- $\displaystyle \sum_{i=1}^N A_i$ is a multiple of $M$.
If no such $A$ exists, the sum of the answers is defined to be $0$.
Solve $T$ test cases.
Constraints
- $1 \leq T \leq 10^5$
- Constraints for each test case
- $1 \leq N \leq 2 \times 10^5$.
- $1 \leq M \leq 10^9$.
- $X_i$ is either an integer at least $0$ and less than $M$, or $-1$. $\quad (1 \leq i \leq N)$.
- Constraints for each test file
- The sum of $N$ over the $T$ test cases is at most $2 \times 10^5$.
- All input values are integers.
Input
$T$
${\rm case}_1$
$\vdots$
${\rm case}_T$
Each test case is given in the following format.
$N$ $M$ $X_1$ $X_2$ $\cdots$ $X_N$
Output
The output consists of $T$ lines. On line $t~(1 \leq t \leq T)$, print the answer to test case $t$ as an integer.
Do not forget the newline at the end.
Sample
Sample 1
Input
4 3 10 4 -1 7 5 100 10 20 30 40 50 6 123456789 0 0 0 0 0 0 6 20230628 -1 -1 -1 -1 -1 -1
Output
2 0 0 324811269
[Test case $1$] There is exactly $1$ sequence $A$ satisfying the conditions, namely $A=(4,9,7)$. Let us solve Make it Zero! for this $A$. For example, the following operations turn it into a zero sequence in $2$ operations.
- Choose term $2$ and term $3$. That is, delete $9,7$ from $A$ and insert at that position $6$, the remainder of $9+7$ divided by $10$. Now $A$ becomes $(4,6)$.
- Choose term $1$ and term $2$. That is, delete $4,6$ from $A$ and insert at that position $0$, the remainder of $4+6$ divided by $10$. Now $A$ becomes $(0)$.
Thus, since the only $A$ satisfying the conditions is $A=(4,9,7)$, the required answer is $2$.
[Test case $2$] No $A$ satisfying the conditions exists. Therefore, the required answer is $0$.
[Test case $3$] The only $A$ satisfying the conditions is $A=(0,0,0,0,0,0)$. Since this $A$ itself is a zero sequence, the answer to Make it Zero! for this $A$ is $0$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。