QOJ.ac

QOJ

Límite de tiempo: 12 s Límite de memoria: 1024 MB Puntuación total: 100

#1930. 恋恋的无意识排列

Estadísticas

当她闭上那只能够读心的“觉”之眼后,恋(Koishi)获得了在无意识中生活的能力。连她自己都不知道自己在做什么。 — 地灵殿

恋正在无意识地排列 $1, 2, \ldots, n$ 这 $n$ 个数字。

她认为一个排列 $p$ 是美丽的,如果 $s=\sum\limits_{i=1}^{n-1} [p_i+1=p_{i+1}]$。其中 $[x]$ 在 $x$ 为真时等于 $1$,否则等于 $0$。

对于每个 $k\in[0,n-1]$,她想知道满足 $k=\sum\limits_{i=1}^{n-1}[p_i< p_{i+1}]$ 的长度为 $n$ 的美丽排列的数量。

输入格式

一行,包含两个整数 $n$ ($1 \leq n \leq 250\,000$) 和 $s$ ($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:

当 $n=4, s=1$ 时,美丽排列包括:

$[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)=1$ 的排列有 3 个,满足 $f(p)=2$ 的排列有 6 个。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.