题解：CF1942E Farm Game

· · 题解

我们先默认第一头牛是 John 的，另一种情况本质相同，最后答案乘上 2 就可以了。

先说结论：我们将相邻两头牛配对，那么最终答案即满足至少一对牛间隔了奇数个空位的方案数。证明很简单，分 3 种情况讨论：

  1. 每对牛间都间隔了奇数个空位。那么 John 开始时让所有牛往右行动，在 Nhoj 行动后，John 只需要保证 Nhoj 行动的牛对应的 John 那头牛也行动，方向向右，这样就能保证轮到 John 时每队牛都间隔奇数个空位，并且不会出现游戏无法终止的情况。然后最后当每对牛都间隔为 0 时，轮到 Nhoj 行动，John 胜。
  2. 有些对牛间隔了奇数个空位，还有些隔了偶数个空位。那么 John 开始时选取所有奇数个空位的牛对里的牛行动，这样，如果 Nhoj 移动了奇数个空位的牛对里的牛，同第一种情况，如果移动了隔了偶数个空位牛对里的牛，John 不对对应的牛做任何操作，这样下一轮到他的时候就会变成第一种情况。
  3. 每对牛间都间隔了偶数个空位。John 先手必须行动，那么就会转化为上面的两种情况，Nhoj 必胜。

算答案我们考虑容斥，用总方案减去每对牛间都间隔了偶数个空位的方案，前者即为 \binom{l}{2n}，后者枚举所有牛对间一共隔了 i 个空位，简单组合计数得到 \binom{l-i-n}{n}\binom{i/2+n-1}{n-1}。

#include<cstdio>
#include<algorithm>
#include<cmath>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long LL;
typedef pair<LL,int>pli;
const int N=2e6+10,MOD=998244353;
LL fac[N],ifac[N];
int qpow(int a,int b)
{
    int res=1;
    for(;b;b>>=1)
    {
        if(b&1)res=1ll*res*a%MOD;
        a=1ll*a*a%MOD;
    }
    return res;
}
void pw(int n)
{
    fac[0]=ifac[0]=1;rep(i,1,n)fac[i]=fac[i-1]*i%MOD;
    ifac[n]=qpow(fac[n],MOD-2);per(i,n-1,1)ifac[i]=ifac[i+1]*(i+1)%MOD; 
}
LL C(int n,int m){return n>=m?fac[n]*ifac[m]%MOD*ifac[n-m]%MOD:0;}
int n,k;
int main()
{
    int TOT;scanf("%d",&TOT);
    while(TOT--)
    {
        scanf("%d%d",&n,&k);
        pw(2*n+5);
        LL ans=C(n,k*2);
        for(int i=0;i<=n;i+=2)
        {
            LL val=C(n-i-k,k)*C(i/2+k-1,k-1)%MOD;
            (ans-=val)%=MOD;
        }
        (ans+=MOD)%=MOD;
        printf("%lld\n",ans*2%MOD);
    }
    return 0;
}