BZOJ4710: [Jsoi2011]分特产 组合数学 容斥原理

• 题意：把M堆特产分给N个同学，要求每个同学至少分到一种特产，共有多少种分法？

• 把A个球分给B个人的分法种数：（插板法，假设A个球互不相同，依次插入，然后除以全排列去重）

C(A,B+A)

• 把M堆特产分给N个同学分法总数（考虑每堆特产拿出来单独分）

∏c(mi,n)

• 然后因为题目要求每个同学至少分到一种特产，所以用到容斥原理
• 每个同学至少分到一种特产分法总数  =   没有要求时的分法总数 - 至少有一个同学没有分到特产的分法总数  + 至少有两个同学没有分到特产的分法总数  ……
• 先预处理出可能用到的C(I,J)的值，然后就乱搞了
• 代码：

   #include <bits/stdc++.h>
  
   #define nmax 2200
  
   #define mod 1000000007
  
   using namespace std;
  
   typedef long long ll;
  
   int n,m,in;
  
   ll c[nmax][nmax]={};
  
   ll x[nmax]; //x[i]表示把这些特产只分给i个学生
  
   void pre(){  //a^b
  
       for (int i=; i<nmax; i++) c[i][]=;
  
       for (int i=; i<nmax; i++) {
  
               for (int j=; j<i; j++) c[i][j]=(c[i-][j]+c[i-][j-])%mod;
  
               c[i][i]=;
  
       }
  
   }
  
   int main(){
  
       pre();
  
       cin>>n>>m;
  
       for (int j=; j<=n; j++) x[j]=;
  
       for (int i=; i<m; i++) {
  
           scanf("%d",&in);
  
           for (int j=; j<=n; j++) {  //枚举学生
  
               x[j]*=c[in+j-][j-];
  
               x[j]%=mod;
  
           }
  
       }
  
       for (int j=; j<=n; j++) { x[j]*=c[n][n-j]; x[j]%=mod; }
  
       //容斥原理
  
       ll ans=;
  
       for (int i=n; i>=; i--) {
  
               if( (n-i)& ) ans-=x[i]; else ans+=x[i];
  
               ans+=mod;
  
               ans%=mod;
  
       }
  
       cout<<ans<<endl;
  
       return ;
  
   }