#6432. 「PKUSC2018」真实排名

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: l0nl1f3

题目描述

小 C 是某知名比赛的组织者,该比赛一共有 n 名选手参加,每个选手的成绩是一个非负整数,定义一个选手的排名是:成绩不小于他的选手的数量(包括他自己)。例如如果 3 位选手的成绩分别是 [1 , 2 ,2] ,那么他们的排名分别是 [3,2,2]

拥有上帝视角的你知道所有选手的实力,所以在考试前就精准地估计了每个人的成绩,设你估计的第 i 个选手的成绩为 A_i ,且由于你是上帝视角,所以如果不发生任何意外的话,你估计的成绩就是选手的最终成绩。

但是在比赛当天发生了不可抗的事故(例如遭受到了外星人的攻击),导致有一些选手的成绩变成了最终成绩的两倍,即便是有上帝视角的你也不知道具体是哪些选手的成绩翻倍了,唯一知道的信息是这样的选手恰好有 k 个。

现在你需要计算,经过了不可抗事故后,对于第 i 位选手,有多少种情况满足他的排名没有改变。

由于答案可能过大,所以你只需要输出答案对 998244353 取模的值即可。

输入格式

第一行两个正整数 n,k

第二行 n 个非负整数 A_1..A_n

输出格式

输出 n 行,第 i 行一个非负整数 ans_i ,表示经过不可抗事故后,第 i 位选手的排名没有发生改变的情况数。

样例

样例输入

3 2
1 2 3

样例输出

3
1
2

样例解释

一共有 3 种情况:(1 , 2 )翻倍,(1 , 3)翻倍,(2 , 3)翻倍。

对于第一个选手来说,他的成绩就算翻倍,其他人都不低于他,所以任意情况下他的排名都不会改变。

对于第二个选手来说,如果是 (1 , 2) 翻倍,成绩变成 (2 , 4 , 3),他的排名变成了第一;如果是 (1 , 3) 翻倍,则成绩变成 (2 , 2 , 6),他的排名变成了第三;如果是 (2 , 3) 翻倍,则成绩变成 (1 , 4 , 6),他的排名还是第二。所以只有一种情况。

对于第三个选手来说,如果是 (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