CF1687F.Koishi's Unconscious Permutation
NOI/NOI+/CTSC
通过率:0%
时间限制:12.00s
内存限制:1024MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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,…,n.
She thinks the permutation p is beautiful if s=i=1∑n−1[pi+1=pi+1]. [x] equals to 1 if x holds, or 0 otherwise.
For each k∈[0,n−1], she wants to know the number of beautiful permutations of length n satisfying k=i=1∑n−1[pi<pi+1].
当她闭上能读心的“觉之眼”后,小石获得了在无意识中生存的能力。甚至她自己也不知道自己正在做什么。
——《地灵殿》
小石正无意识地对 n 个数:1,2,…,n 进行排列。
她认为一个排列 p 是“优美的”,当且仅当 s=i=1∑n−1[pi+1=pi+1]。其中,[x] 在命题 x 为真时取值为 1,否则为 0。
对于每个 k∈[0,n−1],她想知道长度为 n 的优美排列中,满足 k=i=1∑n−1[pi<pi+1] 的排列个数。
输入格式
There is one line containing two intergers n (1≤n≤250000) and s (0≤s<n).
一行包含两个整数 n(1≤n≤250000)和 s(0≤s<n)。
输出格式
Print one line with n intergers. The i-th integers represents the answer of k=i−1, modulo 998244353.
输出一行,包含 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
说明/提示
Let f(p)=i=1∑n−1[pi<pi+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.
令 f(p)=i=1∑n−1[pi<pi+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。
输入解题思路,AI测评打分。不知道怎么写?