poj 3046 Ant Counting 多項式乘法解可重組合數

poj 3046 Ant Counting 多項式乘法解可重組合數

題意：

裸的求可重組合數。

分析：

多項式乘法求系數的應用啊，不用dp。

代碼：

//poj 3046
//sep9
#include 
using namespace std;
const int maxN=1024;
const int maxL=100024;
const int mod=1000000;

int num[maxN];
int coef[maxL];
int tmp[maxL];
int l1;

void mul(int l2)
{
	for(int i=0;i<=l1+l2;++i)
		tmp[i]=0;
	for(int i=0;i<=l1;++i)	
		for(int j=0;j<=l2;++j)
			tmp[i+j]=(tmp[i+j]+coef[i])%mod;
	l1+=l2;
	for(int i=0;i<=l1;++i)
		coef[i]=tmp[i]; 
}

int main()
{
	int t,a,s,b;
	memset(num,0,sizeof(num));
	scanf("%d%d%d%d",&t,&a,&s,&b);
	while(a--){
		int x;
		scanf("%d",&x);
		++num[x];
	}
	memset(coef,0,sizeof(coef));
	coef[0]=1;
	l1=0;	
	for(int i=1;i<=t;++i)
		mul(num[i]);	
	int ans=0;
	for(int i=s;i<=b;++i)
		ans=(ans+coef[i])%mod;
	printf("%d\n",ans);	
	return 0;	
}