みんなのプロコン2018 予選 : D - XOR XorY

Cまでは順調だったので、Cまで解いてE行けばよかった。
https://beta.atcoder.jp/contests/yahoo-procon2018-qual/tasks/yahoo_procon2018_qual_d

問題

N個の整数が与えられる。
ここからK個の要素を用いて、K要素の数列a[i]を作ることを考えよう。

ここでK次正方行列Aと２値X,Yが与えられる。
(a[i] xor a[j] xor X)の値か(a[i] xor a[j] xor Y)のいずれかがA[i][j]と一致するようなaは何通りか。

解法

B[i][j] = min(A[i][j]^X,A[i][j]^Y)とする。
するとa[i] xor a[j]はB[i][j]かB[i][j]^Z (Z=X^Y)のいずれかと一致しなければならない。

先にBが条件を満たせるかチェックしておこう。
B[i][i]=0およびB[i][j]=B[j][i]でなければならない。
また、B[0][i] xor B[0][j]はB[i][j]かB[i][j]^Zのいずれかでなければならないのでこれもチェックしておく。

a[0]を固定すれば、a[0] xor a[i] = B[0][i]かB[0][i]^Zより、a[i]はB[0][i]かB[0][i]^Zのいずれかになる。
ここで重要なのは２値のどちらかで迷うとき、片方が決まればもう片方はそれにxor Z取ったものなので自明である。
a[i]のうち、pかp^Zいずれかになるものの数をf(p)と置こう。(pはp^Zより小さい場合だけ定義する。)

元々与えられたN個の整数中にpがx個、p^Zがy個あるなら、f(p)個の要素をこれらに配分することになる。
これは単純な組み合わせ計算で解ける。
一見O(N^3)に見えるが、x,y,f(p)の取りうる値の範囲はさほど広くないので、メモ化しよう。

あとはa[0]を総当たりしていけばよい。

int N,K,X,Y;
int A[1100][1100];
ll mo=1000000007;
int num[2049];

map<int,int> memo[2020][2020];

ll combi(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}


ll hoge(int a,int b,int c) {
	if(a>b+c) return 0;
	if(b==0 || c==0 || a==0) return 1;
	if(memo[b][c].count(a)) return memo[b][c][a];
	ll ret=0;
	int i;
	FOR(i,a+1) if(i<=b && a-i<=c) ret+=combi(a,i);
	
	return memo[b][c][a]=ret%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>X>>Y;
	FOR(i,N) cin>>x, num[x]++;
	
	FOR(y,K) FOR(x,K) {
		cin>>A[y][x];
		A[y][x]=min(A[y][x]^X,A[y][x]^Y);
	}
	X^=Y;
	
	FOR(y,K) {
		if(A[y][x]) return _P("0\n");
		FOR(x,K) {
			if(A[y][x]!=A[x][y]) return _P("0\n");
			if(((A[0][x]^A[0][y])!=A[x][y]) && ((A[0][x]^A[0][y]^X)!=A[x][y])) return _P("0\n");
		}
	}
	
	ll tot=0;
	FOR(i,2048) if(i<(i^X)) {
		int tmp[2048]={};
		tmp[i]++;
		for(j=1;j<K;j++) tmp[min(A[0][j]^i,A[0][j]^i^X)]++;
		ll ret=1;
		FOR(j,2048) if(j<(j^X)) (ret*=hoge(tmp[j],num[j],num[j^X]))%=mo;
		tot+=ret;
	}
	cout<<tot%mo<<endl;
}

まとめ

「２値のどちらかで迷うとき、片方が決まればもう片方はそれにxor Z取ったものなので自明である。」
と書いたけど、本番そこに考えが至らずACできなかった。