問題一覧 > 通常問題

No.2215 Slide Subset Sum

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 40
作問者 : ShirotsumeShirotsume / テスター : 👑 ygussanyygussany kaichou243kaichou243
4 ProblemId : 9032 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-02-05 20:22:14

問題文

長さ $N$ の非負整数列 $A = (A_1, A_2, \dots, A_N)$ と正整数 $M, K$ が与えられます。整数 $k = 1, 2, \dots, N - M + 1$ のそれぞれについて、以下の問題を解いてください。

  • 長さ $M$ の非負整数列 $(A_k, A_{k+1}, \dots, A_{k+M-1})$ の連続とは限らない長さ $1$ 以上の部分列であって、総和が $K$ の倍数であるものの個数を $998244353$ で割った余りを求めてください。

ただし、部分列は列として同じであっても、取り出す位置が異なれば異なる部分列として数えます。

制約

  • 入力は全て整数
  • $1 \leq M \leq N \leq 2 \times 10^5$
  • $1 \leq K \leq 100$
  • $0 \leq A_i \lt K$

入力

入力は標準入力から以下の形式で与えられる。

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

出力

$N - M + 1$ 行出力せよ。 $i$ 行目には、 $k = i$ であるときの答えを出力せよ。

サンプル

サンプル1
入力
5 3 3
0 1 1 1 2
出力
1
1
2

それぞれの場合についての答えは以下の通りです。

  • $k = 1$ のとき、$(0,1,1)$ について条件を満たす部分列は $(0)$ の $1$ つです。 $1$ を出力してください。
  • $k = 2$ のとき、$(1,1,1)$ について条件を満たす部分列は $(1,1,1)$ の $1$ つです。 $1$ を出力してください。
  • $k = 3$ のとき、$(1,1,2)$ について条件を満たす部分列は $(1,2),(1,2)$ の $2$ つです。部分列は列として等しくても、取る位置が異なれば別のものとして数えます。$2$ を出力してください。
サンプル2
入力
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
出力
563563214
563561834
563561950
563561730
563562150
563562062

それぞれの場合について、 $998244353$ で割った余りを出力してください。

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