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