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

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

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

             C(A,B+A)

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

         ∏c(mi,n)

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

   1 #include <bits/stdc++.h>
   2 #define nmax 2200
   3 #define mod 1000000007
   4  
   5 using namespace std;
   6 typedef long long ll;
   7 int n,m,in;
   8 ll c[nmax][nmax]={0};
   9 ll x[nmax]; //x[i]表示把这些特产只分给i个学生
  10  
  11 void pre(){  //a^b
  12     for (int i=0; i<nmax; i++) c[i][0]=1;
  13     for (int i=1; i<nmax; i++) {
  14             for (int j=1; j<i; j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
  15             c[i][i]=1;
  16     }
  17 }
  18  
  19 int main(){
  20     pre();
  21     cin>>n>>m;
  22     for (int j=1; j<=n; j++) x[j]=1;
  23     for (int i=0; i<m; i++) {
  24         scanf("%d",&in);
  25         for (int j=2; j<=n; j++) {  //枚举学生
  26             x[j]*=c[in+j-1][j-1];
  27             x[j]%=mod;
  28         }
  29     }
  30     for (int j=1; j<=n; j++) { x[j]*=c[n][n-j]; x[j]%=mod; }
  31     //容斥原理
  32     ll ans=0;
  33     for (int i=n; i>=1; i--) {
  34             if( (n-i)&1 ) ans-=x[i]; else ans+=x[i];
  35             ans+=mod;
  36             ans%=mod;
  37     }
  38     cout<<ans<<endl;
  39     return 0;
  40 }

   

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

原文：https://www.cnblogs.com/jiecaoer/p/11474015.html