G - Coin Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 3 点

問題文

1 円硬貨、2 円硬貨、\dots, M 円硬貨が無限にあります。同じ金額の硬貨同士は区別できません。
整数 N, L が与えられます。m=1, 2, \dots, M-L+1 について次の問題を解いてください。

  • あなたは m 円硬貨, m+1 円硬貨, \dots, m+L-1 円硬貨を自由に使うことが出来ます。(形式的に言い換えると、m \leq x \leq m+L-1 を満たす x において x 円硬貨を自由に使うことが出来ます。)
    これらを用いて N 円ちょうどを払う方法の個数を 998244353 で割った余りを求めてください。
    ただし、2 つの払い方は、払う枚数が 2 つの払い方の間で異なる硬貨が存在する時に別々に数えます。

制約

  • 1 \leq L \leq M \leq N \leq 5000
  • N, M, L は整数

入力

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

N M L

出力

M-L+1 行出力せよ。i 行目には m = i の時の答えを出力せよ。

入力例 1

5 3 2

出力例 1

3
1

m=1 の場合、1 円硬貨と 2 円硬貨を用いて 5 円ちょうどを払う方法は以下の 3 通りです。

  • 1 円硬貨を 5 枚払う。
  • 1 円硬貨を 3 枚、2 円硬貨を 1 枚払う。
  • 1 円硬貨を 1 枚、2 円硬貨を 2 枚払う。

m=2 の場合、2 円硬貨と 3 円硬貨を用いて 5 円ちょうどを払う方法は以下の 1 通りです。

  • 2 円硬貨を 1 枚、3 円硬貨を 1 枚払う。

入力例 2

5000 2500 2495

出力例 2

878712345
520404421
886134625
125526485
307727973
257205353

Score: 3 points

Problem Statement

You have an unlimited number of coins of denominations 1, 2, \dots, M yen.
Coins of the same denomination are indistinguishable.

You are given integers N and L. For each m = 1, 2, \dots, M-L+1, solve the following problem:

  • You may use coins of denominations m, m+1, \dots, m+L-1 freely.
    (Formally, you may use coins of denomination x for all x satisfying m \leq x \leq m+L-1.)
    Find the number of ways to pay exactly N yen using these coins, modulo 998244353.

Two payment methods are considered different if there exists at least one denomination for which the number of coins used differs.

Constraints

  • 1 \leq L \leq M \leq N \leq 5000
  • N, M, L are integers

Input

The input is given from standard input in the following format:

N M L

Output

Print M-L+1 lines. On the i-th line, output the answer for m = i.

Sample Input 1

5 3 2

Sample Output 1

3
1

For m=1, using coins of denominations 1 and 2, there are 3 ways to pay exactly 5 yen:

  • Pay 5 coins of 1 yen.
  • Pay 3 coins of 1 yen and 1 coin of 2 yen.
  • Pay 1 coin of 1 yen and 2 coins of 2 yen.

For m=2, using coins of denominations 2 and 3, there is 1 way to pay exactly 5 yen:

  • Pay 1 coin of 2 yen and 1 coin of 3 yen.

Sample Input 2

5000 2500 2495

Sample Output 2

878712345
520404421
886134625
125526485
307727973
257205353