309489: CF1687F. Koishi's Unconscious Permutation
Memory Limit：1024 MB
Time Limit：12 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Koishi's Unconscious Permutation
题意翻译
> 恋便闭上了能够读心的第三只眼。虽然因此而失去了读心的能力，但相对的却可以在无意识下进行行动了。就连她本人也不可能判断自己接下来会做什么。——《东方地灵殿》 古明地恋正在无意识地排列一个长度为 $n$ 的排列。 她认为，一个排列是美丽的，当且仅当 $s=\sum \limits_{i=1}^{n-1}[p_i+1=p_{i+1}]$，其中 $[x]=1$ 当且仅当 $x$ 成立。 对于 $\forall k \in [0,n-1]$，她希望知道有多少个美丽的长度为 $n$ 排列，满足 $k=\sum \limits_{i=1}^{n-1} [p_i<p_{i+1}]$。 **输入格式** 输入一行，两个正整数 $n,s(1 \leq n \leq 250000, 0 \leq s<n)$。 **输出格式** 输出一行，$n$ 个整数。第 $i$ 个整数表示 $k=i-1$ 时的答案，对 $998244353$ 取模。题目描述
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}] $ .输入输出格式
输入格式
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 $ .Input
题意翻译
> 恋便闭上了能够读心的第三只眼。虽然因此而失去了读心的能力，但相对的却可以在无意识下进行行动了。就连她本人也不可能判断自己接下来会做什么。——《东方地灵殿》 古明地恋正在无意识地排列一个长度为 $n$ 的排列。 她认为，一个排列是美丽的，当且仅当 $s=\sum \limits_{i=1}^{n-1}[p_i+1=p_{i+1}]$，其中 $[x]=1$ 当且仅当 $x$ 成立。 对于 $\forall k \in [0,n-1]$，她希望知道有多少个美丽的长度为 $n$ 排列，满足 $k=\sum \limits_{i=1}^{n-1} [p_i<p_{i+1}]$。 **输入格式** 输入一行，两个正整数 $n,s(1 \leq n \leq 250000, 0 \leq s<n)$。 **输出格式** 输出一行，$n$ 个整数。第 $i$ 个整数表示 $k=i-1$ 时的答案，对 $998244353$ 取模。Output
**题目大意**
古明地恋正在无意识地排列一个长度为 $ n $ 的排列。她认为一个排列是美丽的，当且仅当 $ s = \sum \limits_{i=1}^{n-1}[p_i+1=p_{i+1}] $，其中 $[x] = 1$ 当且仅当 $ x $ 成立。对于 $ \forall k \in [0,n-1] $，她希望知道有多少个美丽的长度为 $ n $ 排列，满足 $ k = \sum \limits_{i=1}^{n-1} [p_i < p_{i+1}] $。
**输入格式**
输入一行，包含两个正整数 $ n, s $（$ 1 \leq n \leq 250000, 0 \leq s < n $）。
**输出格式**
输出一行，$ n $ 个整数。第 $ i $ 个整数表示 $ k = i - 1 $ 时的答案，对 $ 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
```
**说明**
定义函数 $ f(p) = \sum \limits_{i=1}^{n-1} [p_i < p_{i+1}] $。
测试用例 1 中，$ [2,1] $ 是唯一的美丽排列。并且 $ f([2,1]) = 0 $。
测试用例 2 中，美丽排列有：
$ [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] $。其中前六个满足 $ f(p) = 2 $，其余满足 $ f(p) = 1 $。**题目大意** 古明地恋正在无意识地排列一个长度为 $ n $ 的排列。她认为一个排列是美丽的，当且仅当 $ s = \sum \limits_{i=1}^{n-1}[p_i+1=p_{i+1}] $，其中 $[x] = 1$ 当且仅当 $ x $ 成立。对于 $ \forall k \in [0,n-1] $，她希望知道有多少个美丽的长度为 $ n $ 排列，满足 $ k = \sum \limits_{i=1}^{n-1} [p_i < p_{i+1}] $。 **输入格式** 输入一行，包含两个正整数 $ n, s $（$ 1 \leq n \leq 250000, 0 \leq s < n $）。 **输出格式** 输出一行，$ n $ 个整数。第 $ i $ 个整数表示 $ k = i - 1 $ 时的答案，对 $ 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 ``` **说明** 定义函数 $ f(p) = \sum \limits_{i=1}^{n-1} [p_i < p_{i+1}] $。 测试用例 1 中，$ [2,1] $ 是唯一的美丽排列。并且 $ f([2,1]) = 0 $。 测试用例 2 中，美丽排列有： $ [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] $。其中前六个满足 $ f(p) = 2 $，其余满足 $ f(p) = 1 $。
古明地恋正在无意识地排列一个长度为 $ n $ 的排列。她认为一个排列是美丽的，当且仅当 $ s = \sum \limits_{i=1}^{n-1}[p_i+1=p_{i+1}] $，其中 $[x] = 1$ 当且仅当 $ x $ 成立。对于 $ \forall k \in [0,n-1] $，她希望知道有多少个美丽的长度为 $ n $ 排列，满足 $ k = \sum \limits_{i=1}^{n-1} [p_i < p_{i+1}] $。
**输入格式**
输入一行，包含两个正整数 $ n, s $（$ 1 \leq n \leq 250000, 0 \leq s < n $）。
**输出格式**
输出一行，$ n $ 个整数。第 $ i $ 个整数表示 $ k = i - 1 $ 时的答案，对 $ 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
```
**说明**
定义函数 $ f(p) = \sum \limits_{i=1}^{n-1} [p_i < p_{i+1}] $。
测试用例 1 中，$ [2,1] $ 是唯一的美丽排列。并且 $ f([2,1]) = 0 $。
测试用例 2 中，美丽排列有：
$ [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] $。其中前六个满足 $ f(p) = 2 $，其余满足 $ f(p) = 1 $。**题目大意** 古明地恋正在无意识地排列一个长度为 $ n $ 的排列。她认为一个排列是美丽的，当且仅当 $ s = \sum \limits_{i=1}^{n-1}[p_i+1=p_{i+1}] $，其中 $[x] = 1$ 当且仅当 $ x $ 成立。对于 $ \forall k \in [0,n-1] $，她希望知道有多少个美丽的长度为 $ n $ 排列，满足 $ k = \sum \limits_{i=1}^{n-1} [p_i < p_{i+1}] $。 **输入格式** 输入一行，包含两个正整数 $ n, s $（$ 1 \leq n \leq 250000, 0 \leq s < n $）。 **输出格式** 输出一行，$ n $ 个整数。第 $ i $ 个整数表示 $ k = i - 1 $ 时的答案，对 $ 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 ``` **说明** 定义函数 $ f(p) = \sum \limits_{i=1}^{n-1} [p_i < p_{i+1}] $。 测试用例 1 中，$ [2,1] $ 是唯一的美丽排列。并且 $ f([2,1]) = 0 $。 测试用例 2 中，美丽排列有： $ [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] $。其中前六个满足 $ f(p) = 2 $，其余满足 $ f(p) = 1 $。