bzoj2023【Usaco2005 Nov】Ant Counting 數螞蟻
Description
有一天，貝茜無聊地坐在螞蟻洞前看螞蟻們進進出出地搬運食物．很快貝茜發現有些螞蟻長得幾乎一模一樣，於是她認為那些螞蟻是兄弟，也就是說它們是同一個家族裡的成員．她也發現整個螞蟻群裡有時只有一只出來覓食，有時是幾只，有時干脆整個蟻群一起出來．這樣一來，螞蟻們出行覓食時的組隊方案就有很多種．作為一頭有數學頭腦的奶牛，貝茜注意到整個螞蟻群由T(1≤T≤1000)個家族組成，她將這些家族按1到T依次編號．編號為i的家族裡有Ni(1≤Ni≤100)只螞蟻．同一個家族裡的螞蟻可以認為是完全相同的．
如果一共有S，S+1…．，B(1≤S≤B≤A)只螞蟻一起出去覓食，它們一共能組成多少種不同的隊伍呢？注意：只要兩支隊伍中所包含某個家族的螞蟻數不同，我們就認為這兩支隊伍不同．由於貝茜無法分辨出同一家族的螞蟻，所以當兩支隊伍中所包含的所有家族的螞蟻數都相同時，即使有某個家族換了幾只螞蟻出來，貝茜也會因為看不出不同而把它們認為是同一支隊伍．比如說，有個由3個家族組成的螞蟻群裡一共有5只螞蟻，它們所屬的家族分別為1，1，2，2，3．於是出去覓食時它們有以下幾種組隊方案：
·1只螞蟻出去有三種組合：(1)(2)(3)
·2只螞蟻出去有五種組合：(1，1)(1，2)(1，3)(2，2)(2，3)
·3只螞蟻出去有五種組合：(1，1，2)(1，1，3)(1，2，2)(1，2，3)(2，2，3)
·4只螞蟻出去有三種組合：(1，2，2，3)(1，1，2，2)(1，1，2，3)
·5只螞蟻出去有一種組合：(1，1，2，2，3)
你的任務就是根據給出的數據，計算螞蟻們組隊方案的總數．
Input
第1行：4個用空格隔開的整數T，A，S，B.
第2到A+1行：每行是一個正整數，為某只螞蟻所在的家族的編號．
Output
輸出一個整數，表示當S到B（包括S和B）只螞蟻出去覓食時，不同的組隊方案數．
注意：組合是無序的，也就是說組合1，2和組合2，1是同一種組隊方式．最後的答案可能很大，你只需要輸出答案的最後6位數字．注意不要輸出前導0以及多余的空格．
Sample Input
5 2 3
Sample Output
10
樣例說明
2只螞蟻外出有5種組合，3只螞蟻外出有5種組合．共有10種組合
HINT
Source
Silver
動態規劃，滾動數組+前綴和優化。
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 1000005
#define mod 1000000
using namespace std;
int n,m,x,y,t,ans;
int f[2][maxn],g[2][maxn],a[maxn];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
n=read();m=read();x=read();y=read();
F(i,1,m) a[read()]++;
f[0][0]=f[1][0]=g[0][0]=g[1][0]=1;
F(i,1,y) g[0][i]=1;
t=0;
F(i,1,n)
{
t^=1;
F(j,1,y)
{
if (j>a[i]) f[t][j]=(g[t^1][j]-g[t^1][j-a[i]-1]+mod)%mod;
else f[t][j]=g[t^1][j]%mod;
(g[t][j]=g[t][j-1]+f[t][j])%mod;
}
}
ans=0;
F(i,x,y) (ans+=f[t][i])%=mod;
printf("%d\n",ans);
return 0;
}
