发布时间：2024-07-31

min-max容斥

结论

• $ \max (S)= \sum_{T \subseteq S}(-1)^{|T|+1} \min (T) $
• $ E ( \max (S)) \sum_{T \subseteq S}(-1)^{|T|+1} E(\min (T))$

推导

1. $ kMax(S)= \sum_{T \subseteq S}(-1)^{|T|-k}C_{|T|-1}^{k-1}Min(T) $
2. $ lcm(S)=\prod gcd(T)^{(-1)^{|T|+1}} $

证明

• S={x1,x2,x3,...}从大到小排序
• i=1，x1贡献为1
• i!=1，xi有选和不选两种方案，这两种方案一一对应系数相反，贡献为0
• Max(S)=x1

解决都出现的期望时间

$ 记t_i表示第i个元素出现时间 $ $ Max(S)=\sum Min(T) $

[hdu4336]Card Collector

题意：

n张卡牌每张出现概率为pi，求所有卡牌都出完的期望次数

思路：

min很好求， $ Min(T)=\frac{1}{\sum p_i} $

答案为 $ \sum Min(T) ，复杂度 O(n 2^n) $\

double p[25];
void solve(){
    int n;
    while(cin>>n){
        for(int i=0;i<n;i++)cin>>p[i];
        double ans=0;
        for(int i=1;i<1<<n;i++){
            double tmp=0;
            int cnt=0;
            for(int j=0;j<n;j++){
                if(i>>j&1){
                    cnt++;
                    tmp+=p[j];
                }
            }
            ans+=(cnt%2?1:-1)/tmp;
        }
        cout<<fixed<<setprecision(5)<<ans<<'\n';
    }
}

P4707 重返现世

题意：

有i种原料，第i种原料生成的概率为 $ \frac{p_i}{m} $,求收集到任意k种的时间

• $ 1 \leq k \leq n \leq 1000,1 \leq m \leq 10000$

思路：

• 获得任意k种相当于获得n-k+1大的物质
• $ 设f_{k,i,j}确定了式子的k值，当前是第i种原料，\sum p=j时的\sum(-1)^{|T|-k}C_{|T|-1}^{k-1}的值的方案数 $
• $ 对于第i种，不选，f_{k,i,j}=f_{k,i-1,j} $
• $ 选，那么(i,j)状态从(i-1,j-p_i)转移过来，注意到C_{|T|-1}^{k-1}=C_{|T|-2}^{k-2}+C_{|T|-2}^{k-1},前者的系数为1，后者系数-1 $
• $ f_{k,i,j}=f_{k,i,j}+f_{k-1,i-1,j-p_i}-f_{k,i-1,j-p_i} $
• $ 初始化：f_{0,0,0}=0,f_{k,0,0}=-1 $

int f[20][10010],inv[10010],n,k,m,p[1010];
void solve(){
    cin>>n>>k>>m;
    k=n-k+1;
    for(int i=1;i<=n;i++)cin>>p[i];
    for(int i=(inv[1]=1)+1;i<=m;++i)inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    for(int i=1;i<=k;i++)f[i][0]=-1;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=p[i];j--){
            for(int kk=k;kk>=0;kk--){
                f[kk][j]-=f[kk][j-p[i]];
                if(kk)f[kk][j]+=f[kk-1][j-p[i]];
                f[kk][j]%=mod;
                f[kk][j]=(f[kk][j]+mod)%mod;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++)ans+=f[k][i]*m%mod*inv[i]%mod,ans%=mod;
    cout<<ans<<"\n";
}