AtCoder ARC #151 : D - Binary Representations and Queries

手間取ったけどどうにか解けてよかったね。
https://atcoder.jp/contests/arc151/tasks/arc151_d

問題

長さ2^Nの整数列Aが与えられる。
以下のクエリを行った後、Aの各値を答えよ。

クエリは2値X,Yで与えられる。
j=0,...,(2^N-1)に対し、もしX bit目がYだった場合、X bit目がYと反転した値をj'とする。
その際A[j']にA[j]を加算する。

解法

Xの値毎に処理してよい。
X bit目が0または1だったところの値の何倍分が、最終的にAの各値に計上されるかを計算しよう。
その係数に応じAの値を更新する。

int N,Q;
vector<ll> A;
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;
}


int X[202020],Y[202020];
vector<int> S[18];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,1<<N) {
		cin>>x;
		A.push_back(x);
	}
	FOR(i,Q) {
		cin>>x>>y;
		S[x].push_back(y);
	}
	
	FOR(i,N) {
		ll dp[2][2]={{1,0},{0,1}};
		FORR(v,S[i]) {
			if(v==0) {
				(dp[1][0]+=dp[0][0])%=mo;
				(dp[1][1]+=dp[0][1])%=mo;
			}
			else {
				(dp[0][0]+=dp[1][0])%=mo;
				(dp[0][1]+=dp[1][1])%=mo;
			}
		}
		FOR(j,1<<N) if((j&(1<<i))==0) {
			k=j^(1<<i);
			ll a=A[j];
			ll b=A[k];
			A[j]=(dp[0][0]*a+dp[0][1]*b)%mo;
			A[k]=(dp[1][0]*a+dp[1][1]*b)%mo;
		}
		
	}
	FOR(i,1<<N) cout<<A[i]<<" ";
	cout<<endl;
	
}

まとめ

こういうのは思いついてしまうとコードが短くて良いね。