F - ABS Permutation (Count ver.) Editorial /

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N) のうち、以下を満たすものの個数を 998244353 で割ったあまりを各 K=0,1,2,\dots,N-1 に対して求めてください。

  • 1 \le i \le N-1 を満たす整数 i のうち、|P_i - P_{i+1}|=M を満たすものがちょうど K 個ある。

制約

  • 2 \le N \le 250000
  • 1 \le M \le N-1
  • 入力は全て整数である。

入力

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

N M

出力

各 K=0,1,2,\dots,N-1 に対して、条件を満たす順列の個数を 998244353 で割ったあまりを出力せよ。

入力例 1

3 1

出力例 1

0 4 2
  • K=0 の時は条件を満たす順列 P は存在しません。
  • K=1 の時は条件を満たす順列 P は (1,3,2),(2,1,3),(2,3,1),(3,1,2) の 4 個あります。
  • K=2 の時は条件を満たす順列 P は (1,2,3),(3,2,1) の 2 個あります。

入力例 2

4 3

出力例 2

12 12 0 0

入力例 3

10 5

出力例 3

1263360 1401600 710400 211200 38400 3840 0 0 0 0

Score : 900 points

Problem Statement

Find the number of permutations P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N) that satisfy the following, modulo 998244353, for each K=0,1,2,\dots,N-1.

  • There are exactly K integers i such that 1 \le i \le N-1 and |P_i - P_{i+1}|=M.

Constraints

  • 2 \le N \le 250000
  • 1 \le M \le N-1
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M

Output

Print the number of permutations that satisfy the condition, modulo 998244353, for each K=0,1,2,\dots,N-1.

Sample Input 1

3 1

Sample Output 1

0 4 2
  • For K=0, the condition is satisfied by no permutations P.
  • For K=1, the condition is satisfied by four permutations P: (1,3,2),(2,1,3),(2,3,1),(3,1,2).
  • For K=2, the condition is satisfied by two permutations P: (1,2,3),(3,2,1).

Sample Input 2

4 3

Sample Output 2

12 12 0 0

Sample Input 3

10 5

Sample Output 3

1263360 1401600 710400 211200 38400 3840 0 0 0 0