Codeforces #557 Div1 D. Palindrome XOR

これ落としたのもったいなかったなぁ。
https://codeforces.com/contest/1161/problem/D

問題

あるm桁の２進数の値Sが与えられる。
なお、一部の桁の値は不明である。

以下の値(a,b)の組は何通りあるか答えよ。

• 1≦a＜b＜2^m
• a,bはleading zeroが無い状態で、それぞれ２進数表記が回文
• a xor b = S

解法

bはm桁確定。
Sの最上位桁が1であることから、aは1～(m-1)桁である。
よってそれらを総当たりしよう。

aまたはbのある桁を0または1にしたとき、回文および両者のxorが与えられるという条件から、関連する変数の桁が連鎖的に確定していく。
よってそのような関係にあるもの同士、組み合わせが何通りか計算しよう。
大体xorの値が"?"指定されている場合に選択肢が倍々に増えていく。

int N;
string S;
ll mo=998244353;

int vis[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	reverse(ALL(S));
	N=S.size();
	
	if(S[0]=='1') return _P("0\n");
	S[0]='0';
	
	
	ll ret=0;
	
	for(i=1;i<N;i++) {
		ZERO(vis);
		int num=0;
		ll pat=1;
		for(x=N-1;x>=0;x--) if(vis[x]==0) {
			assert(x>=i);
			int mask=3;
			if(S[x]=='1') mask=2;
			if(S[x]=='0') mask=1;
			
			// par first
			y=x;
			while(1) {
				vis[y]=1;
				if(y==N-1-y) break;
				
				y=N-1-y;
				vis[y]=1;
				
				if(y>=i) {
					if(S[y]=='1') mask&=2;
					if(S[y]=='0') mask&=1;
					break;
				}
				
				if(S[y]=='1' && (mask==1||mask==2)) mask=3-mask;
				if(S[y]=='?') {
					pat=pat*__builtin_popcount(mask)%mo;
					mask=3;
				}
				
				
				if(y==i-1-y) break;
				
				y=i-1-y;
				if(S[y]=='1' && (mask==1||mask==2)) mask=3-mask;
				
				if(S[y]=='?') {
					pat=pat*__builtin_popcount(mask)%mo;
					mask=3;
				}
			}
			pat=pat*__builtin_popcount(mask)%mo;
		}
		ret+=pat;
	}
	cout<<ret%mo<<endl;
	
}

まとめ

Div1Dの割に簡単なんだけど、ミスして落としたのもったいない。