【生成函数】果苣拼盘

Description
果苣是一类高贵的水果的统称。

而果苣拼盘则是使用这些高贵的水果制成的拼盘。制作一份果苣拼盘,需要满足如下限制:
     1. 必须使用特定的n种果苣。
     2. 第i种果苣的数量不能少于li 份,也不能多于ri 份
     3. 果苣的总份数要恰好为m份

果苣想知道,一共有多少种不同的果苣拼盘的制作方案?

Input
多组数据

第一行有一个整数T(T<=20),代表数据组数。

对每组数据,第一行有两个由空格分隔的整数n和m(1<=n<=20, 1<=m<=100),表示果苣的种类和拼盘需要的果苣总份数。

接下来n行,每行有两个由空格分隔的整数li 和ri (0<= li <= ri <= 10),描述第i种果苣数量的限制。

Output
对每组数据,输出满足限制条件的方案数。

Sample Input
2
2 3
1 2
1 2
3 5
0 3
0 3
0 3
Sample Output
2
12
HINT
对于两种方案,当有任意一种水果的份数不同时,则两种方案不同。

每种水果无论取几个都只有一种取法。生成函数,最后\(x^n\)的系数就是答案,即多项式的乘法。

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
ll a[220][1100]={0};
ll t,n,m,l[220],r[220];
ll ans[1100],tmp[1100];
int main()
{
	scanf("%lld",&t);
	while(t--)
	{
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		memset(ans,0,sizeof(ans));
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=n;i++)
		{
			scanf("%lld%lld",&l[i],&r[i]);
			m-=l[i];
			r[i]-=l[i]; 
			for(ll j=0;j<=r[i];j++)
			{
				a[i][j]=1;
			}
		}
		for(ll i=0;i<=r[1];i++) ans[i]=a[1][i];
		for(ll i=2;i<=n;i++)
		{
			memset(tmp,0,sizeof(tmp));
			for(ll j=0;j<=m;j++)
			{
				for(ll k=0;k<=r[i];k++)
				{
					tmp[j+k]+=ans[j]*a[i][k];
				}
			}
			memcpy(ans,tmp,sizeof(tmp));
		}
		printf("%lld\n",ans[m]);
	}
}c

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注