No.2215 Slide Subset Sum

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 41
作問者 :

Shirotsume / テスター : 👑

ygussany

kaichou243

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$ で割った余りを求めてください。

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

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

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

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

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$ を出力してください。

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

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

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