标签：tmp 机器 int long jcinv 生产 return mod
- 一个合法的序列可能有多种生成方式，因此我们考虑确定其中唯一的一种
- 从前往后匹配，只有当某种颜色的充能球的数量达到上限时才切换到下一小时
- 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;
}
标签：tmp,
机器,
int,
long,
jcinv,
生产,
return,
mod
From： https://www.cnblogs.com/watersail/p/18383444