AtCoder ARC #133 : E - Cyclic Medians

これ系か…。
https://atcoder.jp/contests/arc133/tasks/arc133_e

問題

N要素の整数列XとM要素の整数列Yがあったとする。
各要素は1～Vの範囲の値を取る。

整数変数aの初期値をAとする。
この変数に対し、以下の処理を行う。

• i=0～(NM-1)の順に、aを(a,X[i%N],Y[i%M])の中央値で置き換える。

X,Yの取り方はV^(N+M)通りある。それぞれ、最終的なaの値の総和を求めよ。

解法

VとAを1つ小さくして、0～(V-1)の値域で考える。
中央値を考える定番として、0/1で考えよう。

• f(x) := aが最終的にx以上であるX,Yの組み合わせ

とすると、sum(f(x))が解となる。

以下、f(x)を考える。
A、X、Yについて、具体的な値でなく、x未満かx以上かの0/1だけ考えればよい。
この時、初期値Aが最後まで残るかどうかを考える。もしX[i%N]とY[i%M]が一致するiがあれば、その時点で中央値はそれらになるため、Aが何であろうと関係ない。

よってAが最後まで残るには、G=GCD(N,M)とするとi%Gが一致するiにおいて、X[i%N]とY[i%M]は片方が0、片方が1でなければならないので、となる。
じゃあAが最後まで残らない場合、0と1どちらが何通り残るかだが、実はこれを厳密に計算する必要はない。
あるxに対し0が残る組み合わせと、(V-x)に対し1が残る組み合わせは等しいはずなので、平均するとどちらも半分だけ1になると考えて差し支えない。
なので、通り。

よって、xを総当たりしつつ、

• Aの値によらずf(x)に寄与する分
• A≧xの場合、f(x)に寄与する分

の和を取るとよい。

const ll mo=998244353;
int N,M,A,V;

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>>V>>A;
	ll ret=0;
	int G=__gcd(N,M);
	for(i=0;i<=V;i++) {
		ll active=modpow(modpow(i,N/G)*modpow(V-i,M/G)+modpow(i,M/G)*modpow(V-i,N/G),G);
		ll inactive=(modpow(V,N+M)+mo-active)*modpow(2)%mo;
		ret+=inactive;
		if(A>i) ret+=active;
	}
	cout<<ret%mo<<endl;
	
}

まとめ

なんだかなぁ。