题目大意
【[arc061F] Card Game for Three】A,B,C三个人玩游戏，最初每个人分别有n,m,k张牌，每张牌上有字母a,b,c之一，但是不知道每张牌具体是什么。由A先操作，每轮操作者翻出自己牌堆顶的一张牌并弃置，下一轮的操作者是该牌上字母对应的人。不能操作的人赢。问有多少种初始牌的情况能使A胜利。答案模1,000,000,007
1≤n,m,K≤300,000
分析
考虑枚举翻牌序列有x个b，有y个c，那么序列长度应该是n+x+y。由于最后一位一定是a，我们可以不管最后一位。
接下来是n-1个a，x个b，y个c任意排列，两个组合数相乘再乘上3的次幂即可。
这样只能拿部分分，考虑枚举i=x+y，那么：
Ans=∑m+ki=0Cn?1n?1+x+y3m+k?x?y∑0≤x≤m,0≤y≤k[x+y=i]Cxi
考虑后面的求和部分。它显然分成三段。形式分别是 ∑Mi=0CiM ； ∑ki=0CkM ； ∑ki=tCkM
如果我们知道M=i-1时的总和，要推到M=i时的总和。根据杨辉三角公式，第一种情况直接乘2，第二种是乘2再减掉 Cki?1 ，第三种是乘2减掉 Cki?1 和 Ct?1i?1
复杂度是线性的
#include
#include
#include using namespace std;
const int N=9e5+5,mo=1e9+7;
typedef long long LL;
int n,m,K,ans,Fac[N],Inv[N],p[N];
int C(int n,int m)
{
return (LL)Fac[n]*Inv[m]%mo*Inv[n-m]%mo;
}int main()
{
p[0]=Fac[0]=Inv[0]=Fac[1]=Inv[1]=1;
p[1]=3;
for (int i=2;
i=m) j=(j*2ll-C(i,K)-C(i,i-m))%mo;
else j=(j*2ll-C(i,K))%mo;
}
if (ans<0) ans+=mo;
printf("%d\n",ans);
return 0;
} 
