题解：CF1942E Farm Game

· · 题解

考虑先手什么时候必胜。不妨设先手的第一头牛永远在最小处，这样答案最后乘以二就可以。考虑先手和后手分别仅有一头牛的情况，发现显然先手赢，并且先手会和后手的牛贴在数轴最右边。那么多只牛的情况也必然是先手的牛把对手的牛按在最右侧，考虑多只牛，我们每回只动那些我们的和对手的对应的牛距离为奇数的牛们。这样那些牛我们能够贴住对手步步紧逼，其他没有动的牛，如果对手下一步敢动，那么就变成了奇数步，我们就必胜了。因此发现我们会输当且仅当把我们和对手的牛按相邻两两分对，如果每对之间牛的距离都是偶数，那么我们就输了。可以先求所有放牛的方式，即 l\choose 2\times n。然后再求放牛使得都是偶数的方式，我们可以枚举每对牛之间隔的距离加起来是多少，这个值必然是偶数，为了方便直接枚举这个数的一半 i。那么可得方案数为 {i+n-1\choose n-1}\times{l-2\times i-n\choose n}，前者是插板法考虑把间隔分配给每对的方案数，后者考虑把每对放进数轴的方案数。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,mod=998244353;
int T,l,n,fac[N],inv[N],ans,sum;
int C(int a,int b)
{
    return fac[a]*inv[a-b]%mod*inv[b]%mod;
}
void sol()
{
    cin>>l>>n;
    ans=C(l,n*2),sum=0;
    for(int i=0;i*2+n*2<=l;i++) sum=(sum+C(l-i*2-n,n)*C(i+n-1,n-1)%mod)%mod;
    cout<<(ans+mod-sum)%mod*2%mod<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>T;
    fac[0]=1,inv[0]=1,inv[1]=1;
    for(int i=1;i<=N-5;i++) fac[i]=fac[i-1]*i%mod;
    for(int i=2;i<=N-5;i++) inv[i]=(mod-mod/i*inv[mod%i]%mod)%mod;
    for(int i=2;i<=N-5;i++) inv[i]=inv[i]*inv[i-1]%mod;
    while(T--) sol();
    return 0;
}