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.in
与 ex_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}$