首页 > 代码库 > 【BZOJ4710】分特产（容斥原理，组合计数）

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

2024-09-10 17:44:56   213人阅读

题意：有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-1-1)*c(n,n-i)

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

 1 const mo=1000000007;
 2 var c:array[0..2000,0..1000]of longint;
 3     a:array[1..1000]of longint;
 4     n,m,i,j,v:longint;
 5     sun,ans:int64;
 6  
 7 begin
 8  
 9  readln(n,m);
10  for i:=1 to m do read(a[i]);
11  c[1,0]:=1; c[1,1]:=1;
12  for i:=2 to 2000 do
13  begin
14   c[i,0]:=1;
15   for j:=1 to 1000 do c[i,j]:=(c[i-1,j-1]+c[i-1,j]) mod mo;
16  end;
17  v:=-1; sun:=0;
18  for i:=n downto 1 do
19  begin
20   v:=-v; ans:=c[n,i];
21   for j:=1 to m do
22   begin
23    ans:=ans*c[i+a[j]-1,i-1];
24    if ans>=mo then ans:=ans mod mo;
25   end;
26   sun:=(sun+ans*v) mod mo;
27   sun:=(sun+mo) mod mo;
28  end;
29  writeln(sun);
30  
31 end.

 

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


联系
我们