【题解】LuoGu5368： [PKUSC2018]真实排名

原题传送门
冷静分析了一下，貌似很可做的样子
数据范围告诉我要用一个$O(nlogn)$的做法

对于每个数$a_i$，可以分类讨论，是否把这个数翻倍

• $a_i$不翻倍，$[\frac{a_i+1}{2},a_i-1]$也不能翻倍，剩下的数假设有$x$个，答案为$C_x^k$
• $a_i$翻倍，$[a_i,a_i\ast 2-1]$都必须翻倍，设都要翻倍的数有$x$个，答案为$C_{n-x}^{k-x}$

如何求上面的$x$？用二分就好了

Code：

#include <bits/stdc++.h>
#define maxn 100010
#define LL long long
using namespace std;
const LL qy = 998244353;
LL fac[maxn], inv[maxn], ans[maxn], a[maxn], b[maxn];
int n, k;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

LL C(int n, int m){ return m > n ? 0 : fac[n] * inv[n - m] % qy * inv[m] % qy; }

LL pow(LL n, LL k){
	if (!k) return 1;
	LL sum = pow(n, k >> 1);
	sum = sum * sum % qy;
	if (k & 1) sum = sum * n % qy;
	return sum;
}

int find1(int x){
	int l = 1, r = n, ans = 0;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (b[mid] >= x) ans = mid, r = mid - 1; else l = mid + 1;
	}
	return ans ? ans : n;
}

int find2(int x){
	int l = 1, r = n, ans = 0;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (b[mid] <= x) ans = mid, l = mid + 1; else r = mid - 1;
	}
	return ans ? ans : 0;
}

int main(){
	n = read(), k = read();
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % qy;
	inv[n] = pow(fac[n], qy - 2);
	for (int i = n - 1; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % qy;
	for (int i = 1; i <= n; ++i) a[i] = b[i] = read();
	sort(b + 1, b + 1 + n);
	for (int i = 1; i <= n; ++i){
		if (!a[i]){ ans[i] = C(n, k); continue;	}
		int l = find2(a[i] % 2 == 0 ? a[i] / 2 - 1 : a[i] / 2), r = find1(a[i]), x = n - (r - l);
		ans[i] = C(x, k);
		l = find1(a[i]), r = find2(2 * a[i] - 1), x = r - l + 1;
		if (k >= x) (ans[i] += C(n - x, k - x)) %= qy;
	}
	for (int i = 1; i <= n; ++i) printf("%lld\n", ans[i]);
	return 0;
}