生产机器

watersail / 2024-08-28 / 原文

一个合法的序列可能有多种生成方式，因此我们考虑确定其中唯一的一种
从前往后匹配，只有当某种颜色的充能球的数量达到上限时才切换到下一小时
DP。f[i]表示考虑到第i小时，[j]表示这一小时的第一颗充能球的颜色，也是上一小时达到上限的充能球的颜色
朱世杰恒等式（取的数的多少不变）：$C_{m+n+1}^{n+1} =\sum_{i=0}^{m} C_{n+i}^{n} $ 可用二项式定理证
不要忘记利用组合递推式“点燃引线”的思想
l/f中至少有一个为0的情况看起来很难处理，但相信OI美学，不妨把别扭的特判注释掉，发现答案就对了

点击查看代码

#include <bits/stdc++.h>
using namespace std;
const int mod=1000000007;
long long jc[2000005],jcinv[2000005];
int w[100005][2];
long long f[100005][2],g[100005][2];
int power(int n,int p)
{
	if(p==0)
	{
		return 1;
	}
	long long tmp=power(n,p/2);
	if(p%2==1)
	{
		return tmp*tmp%mod*n%mod;
	}
	return tmp*tmp%mod;
}
void pre()
{
	jc[0]=1;
	for(int i=1;i<=2000000;i++)
	{
		jc[i]=jc[i-1]*i%mod;
	}
	jcinv[2000000]=power(jc[2000000],1000000005);
	for(int i=2000000-1;i>=0;i--)
	{
		jcinv[i]=jcinv[i+1]*(i+1)%mod;
	}
}
int c(int n,int m)
{
	return jc[n]*jcinv[m]%mod*jcinv[n-m]%mod;
}
int calc(int x,int y)
{
	if(x<0||y<0)
	{
	//	return 0;
	}
	return c(x+y+1,x+1);
}
//x+1
//x+y+1
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	pre();
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>w[i][0]>>w[i][1];
		}
		long long ans=1;
		f[1][0]=(w[1][0]>0);
		f[1][1]=(w[1][1]>0);
		g[1][0]=g[1][1]=1;
		for(int i=2;i<=n;i++)
		{
			f[i][0]=(g[i-1][0]*calc(w[i-1][0]-1,w[i-1][1])%mod+g[i-1][1]*calc(w[i-1][0],w[i-1][1]-1)%mod)%mod;
			g[i][0]=f[i][0];
			f[i][0]*=(w[i][0]>0);
			f[i][1]=(g[i-1][0]*calc(w[i-1][1],w[i-1][0]-1)%mod+g[i-1][1]*calc(w[i-1][1]-1,w[i-1][0])%mod)%mod;
			g[i][1]=f[i][1];
			f[i][1]*=(w[i][1]>0);
		}
		for(int i=1;i<=n;i++)
		{
			ans=(ans+f[i][0]*(c(w[i][0]-1+w[i][1]+2,w[i][0]-1+1)-1)%mod)%mod;
			ans=(ans+f[i][1]*(c(w[i][0]+w[i][1]-1+2,w[i][0]+1)-1)%mod)%mod;
		}
		cout<<ans<<endl;
	}
	return 0;
}