KUPC2014 : D - ハミング

まだまだすんなり。
http://kupc2014.contest.atcoder.jp/tasks/kupc2014_d

問題

N桁の２進数２つS1,S2が与えられる。
S1とのハミング距離がd1、S2とのハミング距離がd2の２進数Tが何個あるか答えよ。

解法

まず、S1とS2が同じ数値である桁の数Pと、異なる桁の数Qをカウントする。

前者の桁については、TとしてS1・S2と同じ数字を選ぶとどちらもハミング距離が増えず、S1・S2と異なる数字を選ぶとどちらもハミング距離が増える。
後者の桁は、TとしてS1とS2どちらと同じものを選ぶかによって、どちらか片方とのハミング距離が１増える。

P桁のうちS1・S2と異なる数字をz箇所、Q桁のうちS1と異なる数字をx箇所とするとすると、以下の数式が成り立つ。

• z + x = d1
• z + (Q-x) = d2

よって、x・zは以下のとおりである。

• x = (Q-(d2-d1))/2
• z = ((d2+d1)-Q)/2

x,yが負や非整数なら解はない。
それ以外の場合は、P個からz箇所S1・S2と異なる数字、Q個からx箇所S1と異なる数字を選べばいいので、を求めればよい。

string S1,S2;
int L,D1,D2;
int num[2];
ll mo=1000000007;

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

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>S1>>D1>>S2>>D2;
	L=S1.size();
	FOR(i,L) num[S1[i]!=S2[i]]++;
	ll ret=0;
	
	if((D1+D2)%2 != num[1]%2) return _P("0\n");
	x=(num[1]-(D2-D1))/2;
	y=num[1]-x;
	if(x<0 || x>num[1] || y<0 || y>num[1]) return _P("0\n");
	int z=D1-x;
	if(z<0 || z>num[0]) return _P("0\n");
	
	_P("%lld\n",combi(num[0],z)*combi(num[1],x)%mo);
}

まとめ

結局x,zの組み合わせは一通りに定まるのがコツ。