本番これはすんなり解いてる。
https://codeforces.com/contest/1942/problem/E
問題
正整数L,Nが与えられる。
L個の区画が並んでおり、うち2N頭の牛がいる。1つの区画に最大1頭の牛が入れる。
2人でゲームを行うことを考える。
N頭は先手の、もうN頭は後手の牛であり、同じ人の牛は隣接し得ない。
以下のゲームを行うとき、先手が必勝となる牛の配置は何通りか。
- 各自の手番では、自身の牛を1頭以上選び、右または左隣の区画に移動する。
- 移動できない場合負けとなる。
解法
一番左にいる牛が先手の牛である場合を考える。
先手が左に牛を動かすと、後手は右にいる牛を左に動かせてしまい良くない。
左にいる先手の牛と、右にいる後手の牛を考える。
相手の手番に、両者の間の空きマスを常に偶数に保つようにすればよい。
逆に、初期状態で両者の間の空きマスが偶数であると負けとなる。
そこで、そのような両者の間の空きマス数を総当たりし、その組み合わせを求めよう。
int T,L,N; const ll mo=998244353; ll comb(ll N_, ll C_) { const int NUM_=2400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; if (fact[0]==0) { inv[1]=fact[0]=factr[0]=1; for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo; for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo; } if(C_<0 || C_>N_) return 0; return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo; } ll hcomb(ll P_,ll Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);} void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>L>>N; ll ret=0; for(i=0;i*2+2*N<=L;i++) { (ret+=hcomb(N,i)*hcomb(N+1,L-(i*2+2*N)))%=mo; } ret=comb(L,2*N)+mo-ret; ret=ret*2; cout<<ret%mo<<endl; } }
まとめ
すんなり思いつけて良かった。