XCPC Notes

Appearance

发布时间：2024-11-19

min_max容斥 ​

结论 ​

  • max⁡(S)=∑T⊆S(−1)∣T∣+1min⁡(T)\max (S)= \sum_{T \subseteq S}(-1)^{|T|+1} \min (T)
  • E(max⁡(S))∑T⊆S(−1)∣T∣+1E(min⁡(T))E ( \max (S)) \sum_{T \subseteq S}(-1)^{|T|+1} E(\min (T))

推导 ​

  1. kMax(S)=∑T⊆S(−1)∣T∣−kC∣T∣−1k−1Min(T)kMax(S)= \sum_{T \subseteq S}(-1)^{|T|-k}C_{|T|-1}^{k-1}Min(T)
  2. lcm(S)=∏gcd(T)(−1)∣T∣+1lcm(S)=\prod gcd(T)^{(-1)^{|T|+1}}

证明 ​

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

解决都出现的期望时间 ​

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

[hdu4336]Card Collector ​

题意：

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

思路：

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

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

cpp
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种原料生成的概率为 pim\frac{p_i}{m},求收集到任意k种的时间

  • 1≤k≤n≤1000,1≤m≤100001 \leq k \leq n \leq 1000,1 \leq m \leq 10000

思路：

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

Wenwei Lin · 2022 — 2025