题面
注意排名的定义 , 分数不小于他的选手数量 !!!
题解
有点坑的细节题 ...
思路很简单 , 把每个数分两种情况讨论一下了 .
假设它为 \(x\) .
-
不对它进行翻倍操作 :
那么很容易发现 \(\displaystyle [\lceil \frac{x}{2}\rceil, x)\) 的数都不翻倍 . 其余部分任意 . 假设有 \(tot\) 个 .
那么这部分答案就是 \(\displaystyle \binom {n-tot - 1} {k}\) .
\(-1\) 因为它本身不能操作 .
-
对它进行翻倍操作 :
那么又是显然的 , \(\displaystyle [x,2x)\) 的所有数都需要翻倍 . 其余部分任意 . 假设这段有 \(tot\) 个 .
那么这部分答案就是 \(\displaystyle \binom {n - tot}{k - tot}\) .
然后当 \(x=0\) 的时候需要特殊判断 , 我们可以随意翻倍都不改变结果了 , 答案就是 \(\displaystyle \binom {n} {k}\) .
查询 \([l,r]\) 中数字的个数 , 有个巧妙的操作 . 此处 \(a\) 是排好序的
inline int Sum(int l, int r) {
if (l > r) return 0;
return upper_bound(a + 1, a + 1 + n, r) - lower_bound(a + 1, a + 1 + n, l);
}
以后做这种题一定不能偷懒 , 用脑子想 , 而是要用笔去写 , 把每种情况写清楚了 !!!
那样并不浪费时间 , 反而节省时间 !!
代码
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}
inline int read() {
int x = 0, fh = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * fh;
}
void File() {
#ifdef zjp_shadow
freopen ("6432.in", "r", stdin);
freopen ("6432.out", "w", stdout);
#endif
}
const int N = 1e5 + 1e3, Mod = 998244353;
int n, k, a[N], b[N];
typedef long long ll;
ll fac[N], ifac[N];
ll fpm(ll x, ll power) {
ll res = 1; x %= Mod;
for (; power; power >>= 1, (x *= x) %= Mod)
if (power & 1) (res *= x) %= Mod;
return res;
}
ll C(int n, int m) {
if (n < 0 || m < 0 || n < m) return 0;
return fac[n] * ifac[m] % Mod * ifac[n - m] % Mod;
}
void Init(int maxn) {
fac[0] = ifac[0] = 1;
For (i, 1, maxn) fac[i] = fac[i - 1] * i % Mod;
ifac[maxn] = fpm(fac[maxn], Mod - 2);
Fordown (i, maxn - 1, 1) ifac[i] = ifac[i + 1] * (i + 1) % Mod;
}
inline int Sum(int l, int r) {
if (l > r) return 0;
return upper_bound(a + 1, a + 1 + n, r) - lower_bound(a + 1, a + 1 + n, l);
}
int main () {
File(); Init(1e5);
n = read(); k = read();
For (i, 1, n) a[i] = b[i] = read();
sort(a + 1, a + 1 + n);
For (i, 1, n) {
if (!b[i]) { printf ("%lld\n", C(n, k)); continue ; }
ll res = C(n - Sum((b[i] + 1) / 2, b[i] - 1) - 1, k);
int tot = Sum(b[i], b[i] * 2 - 1);
(res += C(n - tot, k - tot)) %= Mod;
printf ("%lld\n", res);
}
return 0;
}