問題一覧 > 通常問題

No.2653 [Cherry 6th Tune] Re: start! (Make it Zero!)

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 44
作問者 : 👑 Kazun / テスター : 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 5909 / 自分の提出
問題文最終更新日: 2024-02-23 21:37:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 418 (Re: start!) (順位表) の他の問題:

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)$.
    Also, $A$ cannot be made a zero sequence in fewer than $2$ moves. Therefore, the answer to Make it Zero! for $A=(4,9,7)$ is $2$.

    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もしくは右上の雲マークをクリックしてアカウントを作成してください。