yukicoder : No.3366 Reversible Tile:Revival

なるほど。
https://yukicoder.me/problems/no/3366

問題

N個のタイルが並んでおり、初期状態ですべて表である。
M個のスイッチがあり、i番目のスイッチを押すと[L[i],R[i]]の範囲のタイルが表裏反転する。

M個のスイッチの押し分け方2^M通りに対し、それぞれ表のタイル数の二乗和を求めよ。

解法

各スイッチが1/2の確率で押されると考え、表のタイル数の二乗和の期待値を求めることを考える。

• 表のタイル数の二乗の期待値 E[S^2] = V[S] - E[S]^2となる。よってV[S]とE[S]を求めればよい。
• 表のタイル数の期待値 E[S] は、１個以上のスイッチの対象となるタイルは1/2、そうでない場合1となる。
  • 後者のタイル数をN0とすると、E[S]=(N-N0)/2+N0=(N+N0)/2となる。
• 表のタイル数の分散V[S]=(N-N0)/4 + P/2 となる。(Pは、異なる２枚のタイルが同じスイッチ群の対象になる組み合わせ)

Pは、Zobrist hash+イベント走査を行い、同じスイッチ群の対象になるタイル数をハッシュ値を使って数え上げよう。

ll N,M;
ll L,R;
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	map<ll,ll> ev;
	FOR(i,M) {
		cin>>L>>R;
		L--;
		ll hash=((rand()%(1LL<<30))<<30)+(rand()%(1<<30));
		ev[L]^=hash;
		ev[R]^=hash;
	}
	ll preh=ev[0];
	ll pre=0;
	ev[N]^=0;
	map<ll,ll> count;
	ll P=0;
	FORR2(a,b,ev) if(a) {
		ll num=a-pre;
		if(preh) {
			P+=1LL*(count[preh]%mo)*(num%mo)%mo;
			P+=1LL*(num%mo)*((num-1)%mo)%mo*((mo+1)/2)%mo;
		}
		count[preh]+=num;
		pre=a;
		preh^=b;
	}
	
	ll N0=count[0];
	ll ret=((N+N0)%mo*((N+N0)%mo)%mo+N%mo+mo-N0%mo+2*P)%mo;
	FOR(i,M-2) ret=2*ret%mo;
	cout<<ret<<endl;
	
}

まとめ

これ系のn乗和を求める問題、Codeforcesで多いイメージ。