square869120Contest #3 : C - XORパズル / Solving XOR-Puzzles

解ける問題を愚直に解いたらまぁまぁの順位に落ち着いた。
http://s8pc-3.contest.atcoder.jp/tasks/s8pc_3_c

問題

N要素で同じ要素を複数持たない数列Aが与えられる。
以下の条件を満たす数列Bが何通りあるか答えよ。

• Bは同じ要素を複数持たない
• B中の要素はA中にも含まれている。
• Bの各要素をxorで集計した値はKである。

解法

Aの各要素について、以下をDPで求めていけばよい。
f(n,m,s) := 先頭n要素のうちm個選んだとき、xorのsumがsとなるような組み合わせの数。

Bの要素の並べ方は問わないので、sum(f(N,m,K)*m!)を答えればよい。

int N,K;
ll from[256][256];
ll to[256][256];
ll fact[300];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	fact[0]=1;
	FOR(i,256) fact[i+1]=fact[i]*(i+1)%mo;
	from[0][0]=to[0][0]=1;
	
	FOR(i,N) {
		cin>>x;
		
		FOR(j,255) FOR(y,256) (to[j+1][y^x] += from[j][y])%=mo;
		memmove(from,to,sizeof(from));
	}
	
	ll ret=0;
	FOR(x,256) ret+=from[x][K]*fact[x]%mo;
	cout<<ret%mo<<endl;
	
}

まとめ

最初並べ替えを別々で数えることに気づかず、サンプルが合わずに手間取った。