●BZOJ 4710 [Jsoi2011]分特产

题链：

http://www.lydsy.com/JudgeOnline/problem.php?id=4710

题解：

容斥，组合
先看看这个方案数的计算:
把 M 个相同的东西分给 N 个人，每个人可以一个都分不到
即把 M 个小球放入 N 个盒子，盒子可以为空。
方案数为 ${C}_{N+M-1}^{N-1}$。
怎么理解如下：
如果现在有 N+m-1 个位置，我们可以在 N-1 个位置放隔板，
并且令相邻的两个隔板(把首尾也看作另外2个隔板)中间的空余位置放小球。
(相邻的两个隔板之间共有 N 个间隙，所以可以把每个间隙依次看做一个盒子。)
则任意一种插隔板的方法都对应一种把小球放入盒子的方法。
所以,方案数为 ${C}_{N+M-1}^{N-1}$

考虑 f[i] 表示有至少有 i 个人一个特产都没分到的方案数。
令 B[j] 表示 j 号特产的个数,共M种特产,n=N-i个人去分特产。
则 ${f[i]}=\prod_{j=1}^{M} {C}_{n+B[j]-1}^{n-1}$。
然后容斥即为：
${ANS} = {f[0]}-{C}_{N}^{1}\times{f[1]}+{C}_{N}^{2}\times{f[2]} –\cdots+\cdots$
那个组合数表示：选出那 i 个一定分不到特产的人的方法数。

代码：

#include<cstdio>#include<cstring>#include<iostream>#define _ % P #define MAXN 2005#define filein(x) freopen(#x".in","r",stdin);#define fileout(x) freopen(#x".out","w",stdout);using namespace std;const int P=1000000007;int B[MAXN],C[MAXN][MAXN];int N,M,ANS;int main(){scanf("%d%d",&N,&M);for(int i=1;i<=M;i++) scanf("%d",&B[i]);for(int i=0;i<=2000;i++){C[i][0]=1;for(int j=1;j<=i;j++) C[i][j]=(1ll*C[i-1][j-1]+C[i-1][j])_;}for(int i=0,n,tmp;i<=N;i++){n=N-i; tmp=1;for(int j=1;j<=M;j++) tmp=(1ll*tmp*C[n+B[j]-1][n-1])_;tmp=(1ll*tmp*C[N][i])_;if(i&1) tmp=(-1ll*tmp+P)_;ANS=(1ll*ANS+tmp)_;}printf("%d",ANS);return 0;}