問題一覧 > 通常問題

No.2215 Slide Subset Sum

レベル : / AI推定難易度 : 1950 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 48
作問者 : Shirotsume / テスター : ygussany kaichou243
お気に入りにしたユーザー ProblemId : 9032 / 自分の提出
問題文最終更新日: 2023-02-05 20:22:14
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 376 (順位表) の他の問題:

Problem Statement

You are given a sequence of non-negative integers $A = (A_1, A_2, \dots, A_N)$ of length $N$ and positive integers $M, K$. For each integer $k = 1, 2, \dots, N - M + 1$, solve the following problem.

  • Find the number, modulo $998244353$, of subsequences (not necessarily contiguous) of length at least $1$ of the sequence of non-negative integers $(A_k, A_{k+1}, \dots, A_{k+M-1})$ of length $M$ whose sum is a multiple of $K$.

Here, subsequences taken from different positions are counted as different subsequences, even if they are equal as sequences.

Constraints

  • All input values are integers.
  • $1 \leq M \leq N \leq 2 \times 10^5$
  • $1 \leq K \leq 100$
  • $0 \leq A_i \lt K$

Input

The input is given from Standard Input in the following format.

$N$ $M$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Print $N - M + 1$ lines. The $i$-th line should contain the answer for $k = i$.

Sample

Sample 1
Input
5 3 3
0 1 1 1 2
Output
1
1
2

The answer for each case is as follows.

  • For $k = 1$, the only subsequence of $(0,1,1)$ satisfying the condition is $(0)$, so there is $1$ of them. Print $1$.
  • For $k = 2$, the only subsequence of $(1,1,1)$ satisfying the condition is $(1,1,1)$, so there is $1$ of them. Print $1$.
  • For $k = 3$, the subsequences of $(1,1,2)$ satisfying the condition are $(1,2),(1,2)$, so there are $2$ of them. Subsequences taken from different positions are counted as different, even if they are equal as sequences. Print $2$.
Sample 2
Input
40 35 22
19 20 21 18 8 17 13 10 14 8 17 9 7 6 3 18 17 5 7 16 8 0 5 6 19 9 21 21 13 16 3 16 10 0 1 11 5 20 4 2
Output
563563214
563561834
563561950
563561730
563562150
563562062

For each case, print the remainder when the answer is divided by $998244353$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。