题解 P5368 【[PKUSC2018]真实排名】

ModestCoder_ · 2019-12-08 15:57:59 · 题解

冷静分析了一下，貌似很可做的样子

数据范围告诉我要用一个O(nlogn)的做法

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

• a_i$不翻倍，$[\frac{a_i+1}{2},a_i-1]$也不能翻倍，剩下的数假设有$x$个，答案为$C_{x}^{k}
• a_i$翻倍，$[a_i,a_i*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;
}