yukicoder : No.2265 Xor Range Substring Sum Query

これ系は結構すき。
https://yukicoder.me/problems/no/2265

問題

2^N文字の数字からなる文字列Sが与えられる。
以下のクエリに順次答えよ。

• 1文字更新する。
• 区間[L,R]と整数Xが指定される。S[L^X], S[(L+1)^X], S[(L+2)^X]....S[R^X]を連結した文字列について、部分列全通りについて10進数とみなしたときの値を答えよ。

解法

後者のクエリの解をf(L,R,X)とすると、途中で分割した場合、f(L,M,X)*11^(R-X)+f(M+1,R,X)*2^(M-L+1)と分割した結果をマージすることができる。

Nが最大18と小さいことから、平方分割で解く。
Sを2^9要素ごとに分割し、Xの下9bitのパターンにおける値をあらかじめ計算しておこう。

• 前者のクエリに対しては、1つの分割に対しXの下9bitのパターンにおける値を更新すればよい。
• 後者のクエリに対しては、区間を下9bit分ずつに分割し、計算済みの値を、上記の式を用いてマージしていけばよい。

int N;
int S[1<<18];
ll dp[1<<9][1<<9];
ll p2[2<<18];
ll p11[2<<18];
const ll mo=998244353;

void update(int n) {
	n=(n>>9)<<9;
	ll from[1<<9],to[1<<9];
	int mask;
	FOR(mask,1<<9) from[mask]=S[n+mask];
	int i;
	FOR(i,9) {
		FOR(mask,1<<9) {
			to[mask]=(from[mask]*p11[1<<i]+from[mask^(1<<i)]*p2[1<<i])%mo;
		}
		swap(from,to);
	}
	FOR(mask,1<<9) dp[n>>9][mask]=from[mask];
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=p11[0]=1;
	FOR(i,(1<<18)+(1<<17)) {
		p2[i+1]=p2[i]*2%mo;
		p11[i+1]=p11[i]*11%mo;
	}
	cin>>N>>s;
	FOR(i,1<<N) S[i]=s[i]-'0';
	FOR(i,1<<9) update(i<<9);
	
	int Q;
	cin>>Q;
	while(Q--) {
		cin>>i;
		if(i==1) {
			cin>>x>>y;
			S[x]=y;
			update(x);
		}
		else {
			int L,R,X;
			cin>>L>>R>>X;
			R++;
			int len=0;
			ll ret=0;
			while((L&((1<<9)-1))&&L<R) {
				ret=(ret*11+S[L^X]*p2[len])%mo;
				L++;
				len++;
			}
			while(L+(1<<9)<=R) {
				ret=(ret*p11[1<<9]+dp[(L^X)>>9][X&((1<<9)-1)]*p2[len])%mo;
				L+=1<<9;
				len+=1<<9;
			}
			while(L<R) {
				ret=(ret*11+S[L^X]*p2[len])%mo;
				L++;
				len++;
			}
			cout<<ret<<endl;
		}
		
	}
	
}

まとめ

N=16ならともかくN=18は結構重いと思ったけど普通に通るんだな。