yukicoder : No.2113 Distance Sequence 1.5

この問題名は何だろうな。
https://yukicoder.me/problems/no/2113

問題

2N要素の整数列Aを用いて2人でゲームを行う。
それぞれ交互にターンが回ってくるので、各自自分のターンではAの要素を1つ選び、抜き出して他の数列Bの末尾に付け加えるということをする。
もし隣接要素の差の絶対値がK以上の箇所があれば後手の勝ち、なければ先手の勝ちとする。

Aの各値が1～Mを取るとき、AはM^(2N)通りが考えられるが、うち先手が勝つのは何通りか。

解法

max(A)-min(A)≧Kなら後手必勝である。max(A)かmin(A)のどちらかを先手が使うまで待ち、後手はその直後その反対を取ればいいからである。

あとはmax(A)-min(A)＜Kとなるケースを数え上げよう。

min(A)=xかつx+K-1≦Mであるケースを数えることを考える。
Aの各値がx～(x+K-1)の範囲に入るケースは、K^(2N)通りである。
ここから、min(A)=xとならないケースは、各値が(x+1)～(x+K-1)の範囲にあるケース(K-1)^(2N)通りなのでそれを引けばよい。

上記をx=1～M-(K-1)の範囲で足せばよい。
ただし、x=M-(K-1)以上のケースは、x=M-(K-1)の時の前者の値だけで数え上げきれるので、後者の引き算は不要。

ll N,M,K;
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	K=min(K,M);
	ll ret=0;
	ret+=(M-K+1)%mo*modpow(K,2*N)%mo;
	ret-=(M-K)%mo*modpow(K-1,2*N);
	cout<<(ret%mo+mo)%mo<<endl;
}

まとめ

勝利条件に気付けばすぐ。