【AtCoder Regular Contest 061 F】Card Game for Three

mrsrz 2月 26, 2020

组合数学。

题目大意：

有 A，B，C 三个人在玩一个游戏，他们初始有 $a,b,c$ 张牌，按顺序叠放。每张牌上写着 A 或 B 或 C。一个人的回合，他要翻开他的牌堆顶的第一张牌，然后下一个回合由牌上写的人行动。当轮到某人行动时，若他没有牌了，则他胜出。

现在由 A 开始游戏，问有多少种不同的牌堆，使得最后 A 胜出。

题解：

我们考虑每个人进行回合的次数。为了方便，我们直接去掉 A 一开始进行的回合。那么，如果一个序列中，A 进行了恰好 $a-1$ 个回合，并且在这个序列的最后一个回合又轮到 A，那么 A 就赢了。剩下的牌显然可以随便排列。

我们枚举这个序列的长度 $n$，那么有 $a-1$ 个位置是要放 A 的，剩下 $n-a+1$ 个位置放 B 或 C。

由于 B 和 C 的个数不能超过 $b,c$，所以剩下的位置也不能任意放。假设 $ b\leq c$，选择 B 的下限和上限分别为 $l,r$，那么选数的方案数为：

$\sum_{i=l}^r\binom{n-a+1}{i}$

我们考虑使用组合数前缀和相减得到这个东西。定义函数 $F(n,m)$：

$F(n,m)=\sum_{i=0}^m\binom{n}{i}$

直接计算这个东西需要多项式科技而且复杂度不对。

我们发现，枚举的区间长度增加时，每次 $l,r$ 最多变化 $1$。

我们再对 $F(n,m)$ 进行转化：

$\begin{align} F(n,m)&=\sum_{i=0}^m\binom{n-1}{i-1}+\binom{n-1}{i}\\ &=\left(2\sum_{i=0}^m \binom{n-1}{i}\right)-\binom{n-1}{m}\\ &=2F(n-1,m)-\binom{n-1}{m} \end{align}$

也就是说这个是可以递推的。

由于 $l,r$ 每次变化不超过 $1$，所以可以从 $n-1$ 的状态递推而来。

对于剩下的牌，牌上写什么都无所谓，再乘 $3$ 的幂次即可。

时间复杂度 $O(a+b+c)$。

Code：

#include<cstdio>
typedef long long LL;
const int N=1e6+5,md=1e9+7;
int a,b,c,fac[N],iv[N],ans;
inline int pow(int a,int b){
    int ret=1;
    for(;b;b>>=1,a=(LL)a*a%md)if(b&1)ret=(LL)ret*a%md;
    return ret;
}
inline int C(int n,int m){return n>=m?(LL)fac[n]*iv[m]%md*iv[n-m]%md:0;}
int main(){
    scanf("%d%d%d",&a,&b,&c);
    if(!a--)return puts("1"),0;
    if(b>c)b^=c^=b^=c;
    for(int i=*fac=1;i<=1000000;++i)fac[i]=(LL)fac[i-1]*i%md;
    iv[1000000]=397802501;
    for(int i=1e6-1;~i;--i)iv[i]=(i+1LL)*iv[i+1]%md;
    int pL=0,pR=0;
    for(int i=0,x=1,y=pow(3,b+c);i<=b+c;++i){
        int nL=i<=c?0:(pL*2LL-C(i-1,i-c-2)+C(i,i-c-1)+md)%md;
        int nR=i<=b?x:(pR*2LL-C(i-1,b)+md)%md;
        pL=nL,pR=nR;
        ans=(ans+(LL)C(i+a,a)*(nR-nL+md)%md*y)%md;
        x=x*2%md,y=y*333333336LL%md;
    }
    printf("%d\n",ans);
    return 0;
}