CSAcademy Round #74 : E. Good Permutations

直前に前回のARCのF解いてたしね。
https://csacademy.com/contest/round-74/task/good-permurations/

問題

1,2,...,2^(N-1)のN値のPermutation P N!通りを考える。
初期値0の変数Rに対し以下のクエリをQ個順に行ったとき、R=1となるようなPは何通りあるか。

• 各クエリはPの要素番号の部分集合からなる。その要素番号群のうち、数列中の値の最大値がxのとき、R = R xor xで更新する。

解法

各クエリは実行順は関係しないので、まず各部分集合の登場回数を数え上げよう。
Permutation Pを考えたとき、各クエリを適用した結果xとして選択されるのが1は奇数回、2以上の値は偶数回であるようにしたい。

Pのうち大きい順に位置を定めること考え、すでに値が確定した箇所をbitmaskで管理しよう。
f(mask) := Pのうち上位bitcount(mask)個の位置がmaskのいずれかの場所に来るようにし、かつそれらがxとしてRの更新処理に登場する回数が偶数回(ただしx==1のときのみ奇数回)である組み合わせ数
f(0)=1から初めて、f( (2^N)-1)が解となる。

f(mask)の値からf(mask | (2^i))を更新する場合を考える。
Q個のクエリ中、Pのうちbitcount(mask)+1個目の値が最大値として選択される回数は何回あるかを考える。
これはクエリを表す部分集合のうち、maskとの共通部分を持たず、(2^i)のビットに相当する要素を持つものである。
この処理はbitmaskの部分集合列挙テクを用いれば全部でO(3^N)で列挙でき、クエリ中の登場回数の偶奇を数え上げることができる。

以下のコードは全体でO(N*3^N)でTL割とギリギリだった。

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^(1<<i);
			int num=0;
			for(int sm=cmask; sm>=0; sm--) {
				sm&=cmask;
				num^=pat[sm|(1<<i)];
			}
			
			if(num==((mask|(1<<i))==(1<<N)-1)) dp[mask|(1<<i)]+=dp[mask];
		}
	}
	cout<<dp[(1<<N)-1]<<endl;
	
}

まとめ

コードは短いのよね。