发布时间：2024-03-04

CF451E Devu and Flowers

题意：
有n个盒子，每个盒子Ai朵鲜花，相同盒子鲜花颜色相同，不同盒子颜色不同
问选m朵花有多少种方案

• n<=20,m<=1e14,s<=1e12

思路：

• 如果一个花瓶有无限个，相当于把M+N分成N个的方案，即隔板法C(M+N-1,N-1)
• 将n个限制转化为没有限制，容斥原理
  • $设S_1={x_1>A_1},S_2,...$
  • $方案数=C(M+N-1,N-1)-|任意一个花瓶不满足x_i<=A_i|=C(M+N-1,N-1)-|S_1∪S_2∪...|$
  • 很明显右边就是一个容斥原理
  • $对于S_1,先将A_1+1支话选出来，就变成了从M-(A_1+1)支花中选出N支$
  • $容斥原理，一共有2^n种方案，用二进制压缩来存，如果选了奇数个就减去，偶数则为加(因为当前是减去容斥原理的方案数)$

int qpow(int a,int b){
    int ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}
int down,A[25];
int C(int a,int b){
    if(a<b)return 0ll;
    int up=1;
    for(int i=a;i>a-b;i--)up=i%mod*up%mod;
    up=up*down%mod;
    return up;
}
void solve(){
    int n,m;
    cin>>n>>m;
    down=1;
    for(int i=1;i<=n-1;i++)down=down*i%mod;
    for(int i=0;i<n;i++)cin>>A[i];
    down=qpow(down,mod-2);
    int res=0;
    for(int i=0;i<1<<n;i++){
        int a=m+n-1,b=n-1;
        int sign=1;
        for(int j=0;j<n;j++){
            if(i>>j&1){
                sign*=-1;
                a-=A[j]+1;
            }
        }
        res=(res+sign*C(a,b))%mod;
    }
    cout<<(res+mod)%mod;
}

莫比乌斯函数Mobius

• $n=p_1^{\alpha _1}p_2^{ \alpha _2}...p_k^{ \alpha _k}$
• $Mobius(i)=0, 任意的 \alpha>1$
• $Mobius(i)=1,\alpha=1且k为偶数$
• $Mobius(i)=-1 \alpha =1且k为奇数$