「日常训练」取数问题

    「日常训练」取数问题

    给出一个长度为 nn 的序列 aa,有 mm 次询问:

    1. 首先,在区间 [1,r−l+1][1, r - l + 1] 中随机选取一个数 KK。
    2. 然后,在区间 [l,r][l, r] 中随机选择一个大小为 KK 的下标集合,你需要求出选出的所有下标对应的 aia_i 都大于等于 xx 的概率。答案对 998244353998244353 取模。

    数据范围:1≤n,m≤1061 \leq n, m \leq 10^6,1≤ai,x≤1051 \leq a_i, x \leq 10^5。

    时空限制:11s / 512512MiB。

    Solution

    对于任意一组询问 (l,r,x)(l, r, x),我们记区间长度为 LL,区间中大于等于 xx 的数有 HH 个。

    那么答案为:

    1L∑i=1H(Hi)(Li)\frac{1}{L}\sum\limits_{i = 1}\limits^{H} \frac{\tbinom{H}{i}}{\tbinom{L}{i}}

    将组合数拆开,化简,再配成组合数:

    1L∑i=1H(Hi)(Li)=1L∑i=1HH!i!(H−i)!L!i!(L−i)!=1L∑i=1HH!(L−i)!(H−i)!L!=H!L⋅L!∑i=1H(L−i)!(H−i)!=H!(L−H)!L⋅L!∑i=1H(L−i)!(H−i)!(L−H)!=H!(L−H)!L⋅L!∑i=1H(L−iH−i)\begin{aligned}\frac{1}{L}\sum\limits_{i = 1}^{H} \frac{\binom{H}{i}}{\tbinom{L}{i}}& = \frac{1}{L}\sum\limits_{i = 1}^H \frac{\frac{H!}{i!(H-i)!}}{\frac{L!}{i!(L-i)!}} \\& = \frac{1}{L}\sum\limits_{i = 1}^H \frac{H!(L-i)!}{(H - i)!L!} \\& = \frac{H!}{L \cdot L!}\sum\limits_{i = 1}^H \frac{(L - i)!}{(H - i)!} \\& = \frac{H!(L - H)!}{L \cdot L!} \sum\limits_{i = 1}^{H}\frac{(L - i)!}{(H - i)!(L - H)!} \\& = \frac{H!(L - H)!}{L \cdot L!} \sum\limits_{i = 1}^{H} \dbinom{L - i}{H - i}\end{aligned}

    重点在于后半段,把它写开就是:

    (L−H0)+(L−H+11)+(L−H+22)+⋯+(L−1H−1)\dbinom{L - H}{0} + \dbinom{L - H + 1}{1} + \dbinom{L - H + 2}{2} + \cdots + \dbinom{L - 1}{H - 1}

    观察到第一项组合数的下指标为 00,那么可以把上指标调成 L−H+1L - H + 1,答案就可以变化为:

    (L−H+10)+(L−H+11)+(L−H+22)+⋯+(L−1H−1)\dbinom{L - H + 1}{0} + \dbinom{L - H + 1}{1} + \dbinom{L - H + 2}{2} + \cdots + \dbinom{L - 1}{H - 1}

    然后,由大家都知道的 (nm)=(n−1m)+(n−1m−1)\tbinom{n}{m} = \tbinom{n - 1}{m} + \tbinom{n - 1}{m - 1},答案就可以变化为:

    (L−H+21)+(L−H+22)+⋯+(L−1H−1)\dbinom{L - H + 2}{1} + \dbinom{L - H + 2}{2} + \cdots + \dbinom{L - 1}{H - 1}

    然后继续:

    (L−H+32)+⋯+(L−1H−1)\dbinom{L - H + 3}{2} + \cdots + \dbinom{L - 1}{H - 1}

    继续继续继续继续继续 ……,最后得到:

    (LH−1)\dbinom{L}{H - 1}

    然后原式就变化为:

    H!(L−H)!L⋅L!(LH−1)=H!(L−H)!L⋅L!L!(H−1)!(L−H+1)!=HL(L−H+1)\begin{aligned}\frac{H!(L - H)!}{L \cdot L!}\dbinom{L}{H - 1}& = \frac{H!(L - H)!}{L \cdot L!}\frac{L!}{(H - 1)!(L - H + 1)!} \\& = \frac{H}{L(L - H + 1)}\end{aligned}

    先预处理出 1∼n1 \sim n 在模 998244353998244353 意义下的逆元。如果知道了 LL 和 HH 就可以 O(1)\mathcal{O}(1) 算出答案。

    于是,对于每一组询问 (l,r,x)(l, r, x),就是要求出区间 [l,r][l, r] 内有多少个数大于等于 xx。

    在线的话就直接主席树;离线的话就直接从大到小加数,用 BIT 维护。

    时间复杂度 O((n+m)log⁡n)\mathcal{O}((n + m) \log n),非常的优秀。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    inline int read() {
        int x = 0, f = 1; char s = getchar();
        while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
        while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
        return x * f;
    }
    
    int power(int a, int b, int p) {
        int ans = 1;
        for (; b; b >>= 1) {
            if (b & 1) ans = 1ll * ans * a % p;
            a = 1ll * a * a % p;
        }
        return ans;
    }
    
    const int N = 1000100;
    const int SIZE = 100100;
    const int mod = 998244353;
    
    int n, m;
    
    int a[N];
    int inv[N];
    
    struct range {
        int l, r, id;
    
        range() {}
        range(int A, int B, int C) : l(A), r(B), id(C) {}
    };
    
    vector<int> H[SIZE];
    vector<range> attend[SIZE];
    
    int c[N];
    
    void add(int x, int val) {
        for (; x <= n; x += x & -x) c[x] += val;
    }
    
    int ask(int x) {
        int ans = 0;
        for (; x; x -= x & -x) ans += c[x];
        return ans;
    }
    
    int cur[N];
    
    int main() {
        n = read(), m = read();
    
        for (int i = 1; i <= n; i ++)
            inv[i] = power(i, mod - 2, mod);
    
        for (int i = 1; i <= n; i ++)
            a[i] = read();
    
        for (int i = 1; i <= n; i ++)
            H[a[i]].push_back(i);
    
        for (int i = 1; i <= m; i ++) {
            int l = read(), r = read(), x = read();
            attend[x].push_back((range) { l, r, i });
        }
    
        for (int x = 100000; x >= 1; x --) {
            for (int i = 0; i < (int)H[x].size(); i ++) {
                int pos = H[x][i];
                add(pos, 1);
            }
    
            for (int i = 0; i < (int)attend[x].size(); i ++) {
                range G = attend[x][i];
    
                int l = G.l, r = G.r;
    
                int cnt = ask(r) - ask(l - 1),
                    len = r - l + 1;
    
                int val = cnt;
                val = 1ll * val * inv[len] % mod;
                val = 1ll * val * inv[len - cnt + 1] % mod;
    
                cur[G.id] = val;
            }
        }
    
        for (int i = 1; i <= m; i ++)
            printf("%d\n", cur[i]);
    
        return 0;
    }