Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 1954 | Accepted: 822 |
Description
a few, and sometimes all of them. This made for a large number of different sets of ants!
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
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
#include<cstdio> #include<iostream> #include<map> #include<vector> #include<algorithm> #include<set> #include<cstring> using namespace std; typedef pair<int,int> P; typedef long long LL; const int maxn = 1000 + 5; const int maxm = 100000 + 5; const int INF = 1000000000; const int Mod = 1000000; int t,a,s,b; int dp[2][maxm]; int sum[maxn]; void solve(){ int ans = 0; for(int i = 0;i < maxm;i++) dp[0][i] = 0; dp[0][0] = dp[1][0] = 1; for(int i = 1;i <= t;i++){ for(int j = 1;j < maxm;j++){ if(j-sum[i]-1 >= 0){ dp[i&1][j] = dp[(i-1)&1][j] + dp[i&1][j-1] - dp[(i-1)&1][j-sum[i]-1] + Mod; while(dp[i&1][j] >= Mod) dp[i&1][j] -= Mod; } else { dp[i&1][j] = dp[(i-1)&1][j] + dp[i&1][j-1]; while(dp[i&1][j] >= Mod) dp[i&1][j] -= Mod; } } } for(int i = s;i <= b;i++){ ans = ans + dp[t&1][i]; while(ans >= Mod) ans -= Mod; } printf("%d\n",ans); } int main(){ while(scanf("%d%d%d%d",&t,&a,&s,&b) != EOF){ memset(sum,0,sizeof(sum)); for(int i = 0;i < a;i++){ int x;scanf("%d",&x); sum[x]++; } solve(); } return 0; }