[PKUSC2018] 真实排名
题目描述
小 C 是某知名比赛的组织者,该比赛一共有 $n$ 名选手参加,每个选手的成绩是一个非负整数,定义一个选手的排名是:成绩不小于他的选手的数量(包括他自己)。例如如果 $3$ 位选手的成绩分别是 $[1 , 2 ,2]$ ,那么他们的排名分别是 $[3,2,2]$ 。
拥有上帝视角的你知道所有选手的实力,所以在考试前就精准地估计了每个人的成绩,设你估计的第 $i$ 个选手的成绩为$A_i$,且由于你是上帝视角,所以如果不发生任何意外的话,你估计的成绩就是选手的最终成绩。
但是在比赛当天发生了不可抗的事故(例如遭受到了外星人的攻击),导致有一些选手的成绩变成了最终成绩的两倍,即便是有上帝视角的你也不知道具体是哪些选手的成绩翻倍了,唯一知道的信息是这样的选手恰好有 $k$ 个。
现在你需要计算,经过了不可抗事故后,对于第 $i$ 位选手,有多少种情况满足他的排名没有改变。
由于答案可能过大,所以你只需要输出答案对 $998244353$ 取模的值即可。
输入输出格式
输入格式
第一行两个正整数 $n,k$。
第二行 $n$ 个非负整数 $A_1, A _ 2, \cdots, A_n$。
输出格式
输出 $n$ 行,第 $i$ 行一个非负整数 $ans_i$,表示经过不可抗事故后,第 $i$ 位选手的排名没有发生改变的情况数。
输入输出样例
输入样例 #1
3 2
1 2 3
输出样例 #1
3
1
2
说明
- 对于 $10\%$ 的数据,有 $1\leq n\leq 15$;
- 对于 $35\%$ 的数据,有 $1\leq n\leq 10^3$;
- 另有 $10\%$ 的数据,满足每个人的成绩都互不相同;
- 另有 $10\%$ 的数据,满足 $0\leq A_i\leq 10^5$;
- 另有 $10\%$ 的数据,满足 $k=85$,$0\leq A_i\leq 600$;
- 对于$100\%$的数据,有$1\leq k < n\leq 10^5$,$0\leq A_i\leq 10^9$。