[Easy-Medium] CF1948F Rare Coins

简要题意

有 $n$ 个口袋，第 $i$ 个口袋里有 $a_i$ 个金币和 $b_i$ 个银币。

一枚金币的价值为 $1$；一枚银币有 $50\%$ 的概率价值为 $1$，$50\%$ 的概率价值为 $0$。

有 $q$ 次询问，每次询问给出区间 $[l,r]$，你需要输出区间中的所有口袋的所有钱币的价值总和，大于区间外所有口袋的钱币价值总和的概率。答案对 $998,244,353$ 取模。

$1\leq n,q\leq 3\times 10^5,0\leq \sum a_i,\sum b_i\leq 10^6$。

思路

大力推式子，考虑每次询问，区间内有 $G$ 个金币 $S$ 个银币，区间外有 $g$ 个金币和 $s$ 个银币，则答案为：

$$\frac{1}{2^{S+s}}\sum_{i=0}^{S}\sum_{j=0}^{s} [G+i>g+j] \binom{S}{i}\binom{s}{j}$$

注意到 $G+i>g+j$ 等价于 $i-j>g-G$ 即 $i-j\geq g-G+1$，于是改为枚举差值，得到：

$$\frac{1}{2^{S+s}}\sum_{d=g-G+1}^{\infty} \sum_{j=0}^{s} \binom{S}{j+d}\binom{s}{j}$$

这样我们就消去了不等式的限制，对于后面的形式，稍加变形，再应用范德蒙德卷积公式，得到：

$$\frac{1}{2^{S+s}}\sum_{d=g-G+1}^{\infty} \sum_{j=0}^{s} \binom{S}{j+d}\binom{s}{s-j} = \frac{1}{2^{S+s}}\sum_{d=g-G+1}^{\infty}\binom{S+s}{d+s}$$

令 $k=d+s$ 得到：

$$\frac{1}{2^{S+s}}\sum_{k=g-G+1+s}^{S+s} \binom{S+s}{k}$$

由于 $S+s$ 为所有口袋的银币总数 $\sum b_i$，是定值，于是可以预处理 $S+s$ 为上指标的组合数后缀和，来做到预处理 $O(n+\sum b_i)$，单次 $O(1)$。

代码

实现忘记保存 $\frac{1}{2^{S+s}}$ 的值了，退化为单次 $O(\log \sum b_i)$。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

constexpr int mod = 998244353;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }

int fastpow(int x, int y){
    int ret = 1;
    for(;y;y>>=1,x=Mul(x, x)){ if(y & 1) ret = Mul(ret, x); }
    return ret;
}

int n, q, a[N], b[N], fact[N], inv[N], f[N];

int binom(int n, int m){ return n < m ? 0 : Mul(fact[n], Mul(inv[m], inv[n - m])); }

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> a[i], a[i] += a[i - 1];
    for(int i=1;i<=n;i++) cin >> b[i], b[i] += b[i - 1];
    fact[0] = inv[0] = fact[1] = inv[1] = 1;
    for(int i=2;i<=b[n];i++){
        fact[i] = Mul(fact[i - 1], i);
        inv[i] = Mul(inv[mod % i], mod - mod / i);
    }
    for(int i=2;i<=b[n];i++) inv[i] = Mul(inv[i - 1], inv[i]);
    for(int i=b[n];~i;i--) f[i] = Add(f[i + 1], binom(b[n], i));
    while(q--){
        int l, r; cin >> l >> r;
        int A = a[r] - a[l - 1], B = b[r] - b[l - 1], C = a[n] - A, D = b[n] - B;
        int tmp = min(max(C - A + D + 1, 0), b[n] + 1);
        cout << Mul(fastpow(2, mod - 1 - b[n]), f[tmp]) << ' ';
    }
    cout << '\n';
    return 0;
}

// Written by xiezheyuan