牛客小白賽 23 D.病毒傳染（條件機率，枚舉，容斥，二項式反演）

*

注意題目是條件機率，設 a n s [ i ] ans[i] ans[i] 表示一開始有 i i i 個人攜帶病毒，party 結束後有 k k k 個人得病的概

率，對于每一個 i i i，答案是 a n s [ i ] ∑ i = 1 k a n s [ i ] \displaystyle\frac{ans[i]}{\sum_{i = 1}^kans[i]} ∑i=1k​ans[i]ans[i]​

考慮如何求 a n s [ i ] ans[i] ans[i]： a n s [ i ] = C n i ∗ p i ∗ ( 1 − p ) n − i ∗ C n − i k − i ∗ f ( k − i ) C e m ans[i] = C_n^i*p^i*(1-p)^{n-i}*C_{n-i}^{k-i}*\frac{f(k-i)}{C_e^m} ans[i]=Cni​∗pi∗(1−p)n−i∗Cn−ik−i​∗Cem​f(k−i)​

其中 e e e = n ∗ ( n − 1 ) 2 \frac{n*(n-1)}{2} 2n∗(n−1)​

f ( k − i ) f(k-i) f(k−i) 表示指定的 k − i k - i k−i 個人被傳染的接觸方案數。

直接求 f ( x ) f(x) f(x) 不好求，定義 g ( x ) g(x) g(x) 表示指定的 x x x 個人中，最多 x x x 個人被傳染的方案數。

容易得出 g ( x ) = ( e − t ∗ ( n − t − x ) m ) g(x) = \binom{e - t*(n-t-x)}{m} g(x)=(me−t∗(n−t−x)​)， g ( x ) = ∑ i = 0 x C x i f ( x ) g(x) = \displaystyle\sum_{i = 0}^xC_x^if(x) g(x)=i=0∑x​Cxi​f(x)

通過二項式反演，可以得到 f ( x ) = ∑ i = 0 x ( − 1 ) x − i ∗ C x i ∗ g ( i ) f(x) = \displaystyle\sum_{i = 0}^x(-1)^{x-i}*C_x^i*g(i) f(x)=i=0∑x​(−1)x−i∗Cxi​∗g(i)

帶入得到 a n s [ i ] = C n i ∗ p i ∗ ( 1 − p ) n − i ∗ C n − i k − i ∗ ( C e m ) − 1 ∗ ∑ j = 0 k − i ( − 1 ) k − i − j ∗ C k − i j ∗ ( e − i ∗ ( n − i − j ) m ) ans[i] = C_n^i*p^i*(1-p)^{n-i}*C_{n-i}^{k-i}*(C_e^m)^{-1}*\displaystyle\sum_{j = 0}^{k-i}(-1)^{k-i-j}*C_{k-i}^j*\binom{e -i*(n-i-j)}{m} ans[i]=Cni​∗pi∗(1−p)n−i∗Cn−ik−i​∗(Cem​)−1∗j=0∑k−i​(−1)k−i−j∗Ck−ij​∗(me−i∗(n−i−j)​)

（二項式反演定義的是對指定的 x 個，恰好 x 個滿足條件和至多 x 個滿足條件的轉換）

代碼

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
ll fpow(ll a,ll b) {
    ll r = 1;
    while (b) {
        if (b & 1) r = 1ll * r * a % mod;
        b >>= 1;
        a = 1ll * a * a % mod;
    }
    return r;
}
ll n,m,k,p,fac[maxn],ifac[maxn],ans[maxn],sum;
ll C(int x,int y) {
    if (x < y || y < 0 || x < 0) return 0;
    return 1ll * fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
int main() {
    fac[0] = 1;
    for (int i = 1; i <= maxn - 10; i++)
        fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[maxn - 10] = fpow(fac[maxn - 10],mod - 2);
    for (int i = maxn - 10 - 1; i >= 0; i--)
        ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
    scanf("%lld%lld%lld%lld",&n,&m,&k,&p);
    ll q = 100 - p;
    ll t1 = 1ll * p * fpow(100,mod - 2) % mod, t2 = 1ll * q * fpow(100,mod - 2) % mod;
    ll siz = n * (n - 1) / 2;
    ll tot = C(n * (n - 1) / 2,m);                  //m對接觸的所有情況
    for (int i = 1; i <= k; i++) {                   //枚舉 i 個人帶病毒
        ans[i] = 1ll * C(n,i) * fpow(t1,i) % mod * fpow(t2,n - i) % mod * fpow(tot,mod - 2) % mod * C(n - i,k - i) % mod;
        ll cnt = 0; ll s = 1;
        for (int j = k - i; j >= 0; j--) {
        	cnt = (cnt + s * C(k - i,j) % mod * C(siz - i * (n - i - j),m) % mod) % mod;
        	if (cnt < 0) cnt += mod;
        	s *= -1;
		}
        ans[i] = 1ll * ans[i] * cnt % mod;
        sum = (sum + ans[i]) % mod;
    }
    for (int i = 1; i <= k; i++) {
        printf("%lld\n",ans[i] * fpow(sum,mod - 2) % mod);
    }
    return 0;
}