No.2215 Slide Subset Sum
レベル :
/ AI推定難易度 : 1950
/ 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 48
作問者 :
Shirotsume
/ テスター :
ygussany
kaichou243
タグ : / 解いたユーザー数 48
作問者 :
問題文最終更新日: 2023-02-05 20:22:14
English (AI translation)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。