A15109. Koishi's Unconscious Permutation
编程题
普及/提高-
知识点
题目描述
As she closed the Satori's eye that could read minds, Koishi gained the ability to live in unconsciousness. Even she herself does not know what she is up to.
— Subterranean Animism
Koishi is unconsciously permuting $n$ numbers: $1, 2, \ldots, n$ .
She thinks the permutation $p$ is beautiful if $s=\sum\limits_{i=1}^{n-1} [p_i+1=p_{i+1}]$ . $[x]$ equals to $1$ if $x$ holds, or $0$ otherwise.
For each $k\in[0,n-1]$ , she wants to know the number of beautiful permutations of length $n$ satisfying $k=\sum\limits_{i=1}^{n-1}[p_i<p_{i+1}]$ .
— Subterranean Animism
Koishi is unconsciously permuting $n$ numbers: $1, 2, \ldots, n$ .
She thinks the permutation $p$ is beautiful if $s=\sum\limits_{i=1}^{n-1} [p_i+1=p_{i+1}]$ . $[x]$ equals to $1$ if $x$ holds, or $0$ otherwise.
For each $k\in[0,n-1]$ , she wants to know the number of beautiful permutations of length $n$ satisfying $k=\sum\limits_{i=1}^{n-1}[p_i<p_{i+1}]$ .
输入格式
There is one line containing two intergers $n$ ( $1 \leq n \leq 250\,000$ ) and $s$ ( $0 \leq s < n$ ).
输出格式
Print one line with $n$ intergers. The $i$ -th integers represents the answer of $k=i-1$ , modulo $998244353$ .
输入输出样例
输入 #1
2 0
输出 #1
1 0
输入 #2
4 1
输出 #2
0 3 6 0
输入 #3
8 3
输出 #3
0 0 0 35 770 980 70 0
说明/提示
Let $f(p)=\sum\limits_{i=1}^{n-1}[p_i<p_{i+1}]$ .
Testcase 1:
$[2,1]$ is the only beautiful permutation. And $f([2,1])=0$ .
Testcase 2:
Beautiful permutations:
$[1,2,4,3]$ , $[1,3,4,2]$ , $[1,4,2,3]$ , $[2,1,3,4]$ , $[2,3,1,4]$ , $[3,1,2,4]$ , $[3,4,2,1]$ , $[4,2,3,1]$ , $[4,3,1,2]$ . The first six of them satisfy $f(p)=2$ , while others satisfy $f(p)=1$ .
Testcase 1:
$[2,1]$ is the only beautiful permutation. And $f([2,1])=0$ .
Testcase 2:
Beautiful permutations:
$[1,2,4,3]$ , $[1,3,4,2]$ , $[1,4,2,3]$ , $[2,1,3,4]$ , $[2,3,1,4]$ , $[3,1,2,4]$ , $[3,4,2,1]$ , $[4,2,3,1]$ , $[4,3,1,2]$ . The first six of them satisfy $f(p)=2$ , while others satisfy $f(p)=1$ .