G34 普通生成函数

scy的教学代码：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=1100,M=2100;
int n,m,L[N],R[N];
ULL C[M],D[M],ans[M];
void calc()
{
	memset(C,0,sizeof(C));for(int i=L[1];i<=R[1];i++)C[i]=1;
	for(int k=2;k<=n;k++)
	{
		memset(ans,0,sizeof(ans));
        memset(D,0,sizeof(D));for(int i=L[k];i<=R[k];i++)D[i]=1;

		for(int i=0;i<=m;i++)
			for(int j=L[k];j<=R[k] && i+j<=m ;j++) 
				ans[i+j]+=C[i]*D[j];

		memcpy(C,ans,sizeof(ans));
	}
	printf("%llu\n",C[m]);
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=1;i<=n;i++) scanf("%d%d",&L[i],&R[i]),R[i]=min(R[i],m);
		calc();
	}
	return 0;
}

标程：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=1100,M=2100;
int n,m,L[N],R[N];
ULL C[M],ans[M];
void calc()
{
	memset(C,0,sizeof(C));for(int i=L[1];i<=R[1];i++)C[i]=1;
	for(int k=2;k<=n;k++)
	{
		memset(ans,0,sizeof(ans));
		for(int i=0;i<=m;i++)
			for(int j=L[k];j<=R[k] && i+j<=m ;j++) 
				ans[i+j]+=C[i];

		memcpy(C,ans,sizeof(ans));
	}
	printf("%llu\n",C[m]);
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=1;i<=n;i++) scanf("%d%d",&L[i],&R[i]),R[i]=min(R[i],m);
		calc();
	}
	return 0;
}