CSAcademy Round #74 : D. Minimum by Xor

Cの方がはるかに面倒。
https://csacademy.com/contest/round-74/task/minimum-by-xor/

問題

N要素の数列Vがある。
このうちNは与えられるがVの中身は与えられない。

ある変数Rの初期値を0とする。
Vの要素番号の部分集合を指定すると、そのうち最大値をMとしたとき、R = R xor MでRの値が更新される。
Vの値に関わらずRがVの最小値と等しくする手順のうち最小回数を達成するにはどのような指定の仕方をすればよいか。

解法

Nで何となく予想がつくが、空集合以外の部分集合を(2^N)-1通り試せばよい。
仮にVの値がdistinctな場合、MとしてVの各値が小さい順に1,2,4,...,2^(N-1)回ずつ選択されるので、RはVの最小値になる。
Vの一部が等しい値でも、結局奇数回Rの計算に反映されるのは最小値であるのに変わりはないので問題ない。

…これが最小回数との証明はしていないけど、これより削ってしまうと最小値が偶数回しか反映されない可能性が生じてしまうのかな。

int N,Q;
int pat[1<<17];
ll dp[1<<17];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,Q) {
		cin>>s;
		int p=0;
		FOR(j,N) if(s[j]=='1') p |= 1<<j;
		pat[p]^=1;
	}
	dp[0]=1;
	for(int mask=0;mask<(1<<N);mask++) {
		FOR(i,N) if((mask&(1<<i))==0) {
			int cmask=((1<<N)-1)^mask;
			int num=0;
			for(int sm=cmask; sm>=0; sm--) {
				sm&=cmask;
				if(sm&(1<<i)) num^=pat[sm];
			}
			
			if(num==((mask|(1<<i))==(1<<N)-1)) dp[mask|(1<<i)]+=dp[mask];
		}
	}
	cout<<dp[(1<<N)-1]<<endl;
	
}

まとめ

なんとなく勘で当たってしまうし、実装の面倒くささからしてCとD逆でもいいんじゃないの。