容斥原理

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为奇数 $