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;
}