描述
http://poj.org/problem?id=3046
n种蚂蚁,第i种有ai个,不同种类的蚂蚁可以相互区分,但同一种类的蚂蚁不能相互区分,从这些蚂蚁中取出s,s+1,s+2,...,b-1,b个,问每种取的方式的取法数之和.
原型:多重集组合数:
n种物品,第i种有ai个.不同种类的物品可以相互区分,但同一种类的物品不能相互区分.从这些物品中取出m个,有多少种取法?
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 4358 | Accepted: 1689 |
Description
Being a bit mathematical, Bessie started wondering. Bessie noted
that the hive has T (1 <= T <= 1,000) families of ants which she
labeled 1..T (A ants altogether). Each family had some number Ni (1
<= Ni <= 100) of ants.
How many groups of sizes S, S+1, ..., B (1 <= S <= B <= A) can be formed?
While observing one group, the set of three ant families was seen as
{1, 1, 2, 2, 3}, though rarely in that order. The possible sets of
marching ants were:
3 sets with 1 ant: {1} {2} {3}
5 sets with 2 ants: {1,1} {1,2} {1,3} {2,2} {2,3}
5 sets with 3 ants: {1,1,2} {1,1,3} {1,2,2} {1,2,3} {2,2,3}
3 sets with 4 ants: {1,2,2,3} {1,1,2,2} {1,1,2,3}
1 set with 5 ants: {1,1,2,2,3}
Your job is to count the number of possible sets of ants given the data above.
Input
* Lines 2..A+1: Each line contains a single integer that is an ant type present in the hive
Output
Line 1: The number of sets of size S..B (inclusive) that can be
created. A set like {1,2} is the same as the set {2,1} and should not be
double-counted. Print only the LAST SIX DIGITS of this number, with no
leading zeroes or spaces.
Sample Input
3 5 2 3
1
2
2
1
3
Sample Output
10
Hint
Three types of ants (1..3); 5 ants altogether. How many sets of size 2 or size 3 can be made?
OUTPUT DETAILS:
5 sets of ants with two members; 5 more sets of ants with three members
Source
分析
一.原型算法:
用dp[i][j]表示在前i种物品中取出j个的组合数.
那么可以从前(i-1)个中取(j-k)个,再从第i个中取k个,则有:
dp[i][j]=Σdp[i-1][j-k](0<=k<=min(a[i],j)).枚举i,j,k,这样的算法是O(n*m^2)的.
优化:
对Σdp[i-1][j-k](0<=k<=min(a[i],j))进行变形:
讨论a[i]与j的关系:
1.a[i]<j即min(a[i],j)=a[i]
则有:Σdp[i-1][j-k](0<=k<=min(a[i],j))=Σdp[i-1][j-1-k](0<=k<=min(a[i],j-1))+dp[i-1][j]-dp[i][j-1-a[i]].
即:dp[i][j]=dp[i-1][j]+dp[i][j-1]+dp[i-1][j-1-a[i]];
2.a[i]>=j即min(a[i],j)=j
则有:Σdp[i-1][j-k](0<=k<=min(a[i],j))=Σdp[i-1][(j-1)-k](0<=k<=min(a[i],j-1))+dp[i-1][j].
即:dp[i][j]=dp[i-1][j]+dp[i][j-1].
综上:
if(j--a[i])>= dp[i][j]=dp[i-][j]+dp[i][j-]-dp[i-][j--a[i]]; else dp[i][j]=dp[i-][j]+dp[i][j-];
继续优化,在空间上,dp只用到了i和i-1,可以考虑用滚动数组重复利用空间.
二.该题:
在原型的基础上最后进行一次统计,计算ans=Σ(dp[n][i])(s<=i<=t)即可.
#include<cstdio>
#include<algorithm>
using namespace std; const int maxn=,maxm=*+,mod=1e6;
int n,m,s,b;
int a[maxn];
int dp[][maxm]; void solve()
{
dp[][]=dp[][]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(j--a[i]>=)
{
dp[i&][j]=(dp[i&][j-]+dp[(i-)&][j]-dp[(i-)&][j--a[i]]+mod)%mod;
}
else
{
dp[i&][j]=(dp[i&][j-]+dp[(i-)&][j])%mod;
}
}
}
int ans=;
for(int i=s;i<=b;i++)
{
ans=(ans+dp[n&][i])%mod;
}
printf("%d\n",ans);
} void init()
{
scanf("%d%d%d%d",&n,&m,&s,&b);
for(int i=;i<=m;i++)
{
int now;
scanf("%d",&now);
a[now]++;
}
} int main()
{
#ifndef ONLINE_JUDGE
freopen("ant.in","r",stdin);
freopen("ant.out","w",stdout);
#endif
init();
solve();
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("ant.out");
#endif
return ;
}