【BZOJ4710】分特产（容斥原理，组合计数）

题意：有m种特产，第i种有a[i]个

有n个同学分特产，要求：

1.恰好分完

2.每个人至少要分到一个

求方案数模10^9+7

n,m,a[i]<=1000

思路：WYZ作业

首先考虑对于每一种特产，a[i]个特产分给n个人而且每人都分到的方案数是C(n+a[i]-1,n-1)*c(n,n)

对于m种特产，所有人分的方案数就是它们的乘积

考虑有些人没分到，设现在只有n-i个人可能分到，另外i人什么都没有

方案数是c(n-i+a[i]-1,n-i-1)*c(n,n-i)

显然容斥，枚举有几人取到，对于每一种方案数相乘再加（减）即可

 const mo=;

 var c:array[..,..]of longint;

     a:array[..]of longint;

     n,m,i,j,v:longint;

     sun,ans:int64;

 begin

  readln(n,m);

  for i:= to m do read(a[i]);

  c[,]:=; c[,]:=;

  for i:= to  do

  begin

   c[i,]:=;

   for j:= to  do c[i,j]:=(c[i-,j-]+c[i-,j]) mod mo;

  end;

  v:=-; sun:=;

  for i:=n downto  do

  begin

   v:=-v; ans:=c[n,i];

   for j:= to m do

   begin

    ans:=ans*c[i+a[j]-,i-];

    if ans>=mo then ans:=ans mod mo;

   end;

   sun:=(sun+ans*v) mod mo;

   sun:=(sun+mo) mod mo;

  end;

  writeln(sun);

 end.

巴特西

【BZOJ4710】分特产（容斥原理，组合计数）

最新文章

热门文章