uoj#P593. 新年的军队

新年的军队

黑衣人 $04$ 是一个非常可怕的人,他有一支由 $n$ 个人构成的军队 in's army,而这只军队看守着神牪牪。

军队每个人有一个等级,每个人等级互不相同。庚子年即将过去,辛丑年即将到来,原来等级第 $i$ 高的人,新的一年等级会变成第 $p_i$ 高,可以发现 $p$ 是一个排列。

对于原来等级第 $i$ 高的人,若 $p_{i} > p_{i+1}$,即他等级没有原来比他菜的那个人高,他就会不高兴,特别的原来等级最低的人不会不高兴。

你有一个小弟,早早混入了黑衣人 $04$ 的军队,他在过去一年排名为 $k$。并且他打听到不高兴的人(包括他自己)个数为 $m$。

你现在想知道对于 $1\le l\le n$ 的每个 $l$,有多少种可能的排名使得小弟的新一年排名为 $l$,这样可以方便你之后的救援,方案数对 $998244353$ 取模。

输入格式

一行三个整数,输入 $n,m,k$。

输出格式

输出一行 $n$ 个整数,表示对于 $1\le l\le n$ 的每个 $l$,可能的排名数对 $998244353$ 取模后的结果。

4 2 1
1 2 4 4
5 0 2
0 1 0 0 0
11 2 4
14880 14160 12816 11640 11496 12480 13896 15093 15696 15600 14880

样例四

见下载文件中的 ex_army4.inex_army4.ans,该样例符合子任务 $3$ 的限制。

限制与约定

对于 $100\%$ 的数据,保证 $1\le n\le 5\times 10^5; 0\le m\le n-1; 1\le k\le n$。

子任务编号 特殊限制 分值
$1$ $n\le 10$ $5$
$2$ $n\le 300$ $15$
$3$ $n\le 3\times 10^3$ $15$
$4$ $n\le 10^5$ $35$
$5$ $k=1$ $15$
$6$ 无特殊限制 $15$

时间限制:$4\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载