CODE THANKS FESTIVAL 2017 : F - Limited Xor Subset

しょうもないミスで1位を逃した。
https://code-thanks-festival-2017-open.contest.atcoder.jp/tasks/code_thanks_festival_2017_f

問題

N個の整数A[i]が与えられる。
このうちいくつかを選びそのxorを取ったとき、値がKとなるのは何通りか。
なお、sum(A)は10^5以下である。

解法

愚直にDPするとO(N*sum(A))かかりかねない。
そこで以下の２点に着目し、計算量を落とそう。

• 同じ値がAに複数あっても、結局解には奇数個とるか偶数個とるかしか影響しない。
• Aに異なる値は高々O(√sum(A))通り。

よって同じ値をまとめて扱うようにすれば、O(N+sum(A)^1.5)で済むようになる。
cnt(x) := A[i]=xであるようなiの数
とする。cnt(x)が1以上であるxに対し、奇数個とる場合と偶数個とる場合の現在値と組み合わせをDPで求めていけばよい。

int N,K;
int A[101010];
ll from[1<<17],to[1<<17];
int mo=1000000007;
int cnt[101010];
ll p2[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>A[i];
		cnt[A[i]]++;
	}
	
	p2[0]=1;
	FOR(i,101000) p2[i+1]=p2[i]*2%mo;
	
	int tot=0;
	from[0]=1;
	FOR(i,101010) if(cnt[i]) {
		ZERO(to);
		
		FOR(j,1<<17) {
			(to[j]+=p2[cnt[i]-1]*from[j])%=mo;
			(to[i^j]+=p2[cnt[i]-1]*from[j])%=mo;
		}
		
		swap(from,to);
	}
	cout<<from[K]<<endl;
	
}

まとめ

ちょっと手間取った。