#P13173. [ARC140F] ABS Permutation (Count ver.)

    ID: 12357 传统题 8000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF2900组合数学多项式FFT生成函数

[ARC140F] ABS Permutation (Count ver.)

题目描述

对于 (1,2,…,N) (1,2,\dots,N) 的一个排列 P=(P1,P2,…,PN) P=(P_1,P_2,\dots,P_N) ,请你对于每个 K=0,1,2,…,N−1 K=0,1,2,\dots,N-1 ,求出满足下述条件的排列的个数,并对 998244353 998244353 取模:

  • 在所有满足 1≤i≤N−1 1\leq i\leq N-1 的整数 i i 中,恰好有 K K 个 i i 满足 ∣Pi−Pi+1∣=M |P_i - P_{i+1}| = M 。

输入格式

输入从标准输入中给出,格式如下:

N N M M

输出格式

对于每个 K=0,1,2,…,N−1 K=0,1,2,\dots,N-1 ,输出满足条件的排列个数,对 998244353 998244353 取模。

输入输出样例 #1

输入 #1

3 1

输出 #1

0 4 2

输入输出样例 #2

输入 #2

4 3

输出 #2

12 12 0 0

输入输出样例 #3

输入 #3

10 5

输出 #3

1263360 1401600 710400 211200 38400 3840 0 0 0 0

说明/提示

限制条件

  • 2≤N≤250000 2\leq N\leq 250000
  • 1≤M≤N−1 1\leq M\leq N-1
  • 输入均为整数。

样例解释 1

  • 当 K=0 K=0 时,不存在满足条件的排列 P P 。
  • 当 K=1 K=1 时,满足条件的排列 P P 有 (1,3,2),(2,1,3),(2,3,1),(3,1,2) (1,3,2),(2,1,3),(2,3,1),(3,1,2) 共 4 4 个。
  • 当 K=2 K=2 时,满足条件的排列 P P 有 (1,2,3),(3,2,1) (1,2,3),(3,2,1) 共 2 2 个。