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 nn numbers: 1,2,…,n1, 2, \ldots, n.

She thinks the permutation pp is beautiful if s=∑i=1n−1[pi+1=pi+1]s=\sum\limits_{i=1}^{n-1} [p_i+1=p_{i+1}]. [x][x] equals to 11 if xx holds, or 00 otherwise.

For each k∈[0,n−1]k\in[0,n-1], she wants to know the number of beautiful permutations of length nn satisfying k=∑i=1n−1[pi<pi+1]k=\sum\limits_{i=1}^{n-1}[p_i \lt p_{i+1}].

当她闭上能读心的“觉之眼”后,小石获得了在无意识中生存的能力。甚至她自己也不知道自己正在做什么。

——《地灵殿》

小石正无意识地对 nn 个数:1,2,…,n1, 2, \ldots, n 进行排列。

她认为一个排列 pp 是“优美的”,当且仅当 s=∑i=1n−1[pi+1=pi+1]s=\sum\limits_{i=1}^{n-1} [p_i+1=p_{i+1}]。其中,[x][x] 在命题 xx 为真时取值为 11,否则为 00。

对于每个 k∈[0,n−1]k\in[0,n-1],她想知道长度为 nn 的优美排列中,满足 k=∑i=1n−1[pi<pi+1]k=\sum\limits_{i=1}^{n-1}[p_i \lt p_{i+1}] 的排列个数。

输入格式

There is one line containing two intergers nn (1≤n≤250 0001 \leq n \leq 250\,000) and ss (0≤s<n0 \leq s \lt n).

一行包含两个整数 nn(1≤n≤250 0001 \leq n \leq 250\,000)和 ss(0≤s<n0 \leq s \lt n)。

输出格式

Print one line with nn intergers. The ii-th integers represents the answer of k=i−1k=i-1, modulo 998244353998244353.

输出一行,包含 nn 个整数。其中第 ii 个整数表示 k=i−1k=i-1 时的答案,对 998244353998244353 取模。

输入输出样例

  • 输入#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=1n−1[pi<pi+1]f(p)=\sum\limits_{i=1}^{n-1}[p_i \lt p_{i+1}].

Testcase 1:

[2,1][2,1] is the only beautiful permutation. And f([2,1])=0f([2,1])=0.

Testcase 2:

Beautiful permutations:

[1,2,4,3][1,2,4,3], [1,3,4,2][1,3,4,2], [1,4,2,3][1,4,2,3], [2,1,3,4][2,1,3,4], [2,3,1,4][2,3,1,4], [3,1,2,4][3,1,2,4], [3,4,2,1][3,4,2,1], [4,2,3,1][4,2,3,1], [4,3,1,2][4,3,1,2]. The first six of them satisfy f(p)=2f(p)=2, while others satisfy f(p)=1f(p)=1.

令 f(p)=∑i=1n−1[pi<pi+1]f(p)=\sum\limits_{i=1}^{n-1}[p_i \lt p_{i+1}]。

测试用例 1:

[2,1][2,1] 是唯一的优美排列,且 f([2,1])=0f([2,1])=0。

测试用例 2:

优美排列有:

[1,2,4,3][1,2,4,3]、[1,3,4,2][1,3,4,2]、[1,4,2,3][1,4,2,3]、[2,1,3,4][2,1,3,4]、[2,3,1,4][2,3,1,4]、[3,1,2,4][3,1,2,4]、[3,4,2,1][3,4,2,1]、[4,2,3,1][4,2,3,1]、[4,3,1,2][4,3,1,2]。其中前六个排列满足 f(p)=2f(p)=2,其余满足 f(p)=1f(p)=1。

输入解题思路,AI测评打分。不知道怎么写?

首页