KUPC 2014 D - ハミング

問題

0, 1のみからなる長さの同じ二つの文字列s, tが与えられる。
s, tに長さが等しく、sからのハミング距離がd1で、tからのハミング距離がd2であるような文字列はいくつあるか。
mod 10^9 + 7で求めよ。

制約条件

s

≦10^5

方針

同じ位置にある文字によって場合わけ。
s[i] == t[i]の場合、d1, d2を共に増やすか、共に増やさないか選べる。
s[i] != t[i]の場合、d1, d2のどちらか片方を増やして、もう片方をそのままにするか選べる。

s[i] == t[i]の個数をa個として、このうちx個でd1を増やす、
s[i] != t[i]の個数をb個として、このうちy個でd1を増やすとすると、

d1 = x + y
d2 = x + b - y
となる。xを決めるとyは一意に定まるので、xを全通り試せばよい。
yの範囲がマイナスになったりしたらそのxはダメ。

で、xが決まったら具体的にどこを選ぶのかがaCx通り, yの選び方がbCy通りなのでそれを掛ければよい。

ソースコード

const int mod = inf + 7;
string s, t;
int d, e;

inline ll inv(ll a)
{
	ll b = mod, x = 1, y = 0;
	while(b){
		ll t = a / b;
		a -= t * b;
		swap(a, b);
		x -= t * y;
		swap(x, y);
	}
	return (mod + x % mod) % mod;
}
ll f[100010];
ll C(int n, int k){
	return f[n] * inv(f[k]) % mod * inv(f[n - k]) % mod;
}

int main(){
	f[0] = 1;
	rep(i, 100010) f[i + 1] = f[i] * (i + 1) % mod;
	
	
	cin >> s >> d >> t >> e;
	ll ans = 0;
	
	int n = s.size();
	int a = 0, b = 0;
	
	rep(i, n){
		if(s[i] == t[i]) a++;
		else b++;
	}
	
	for(int i = 0; i <= a; i++){
		int j = d - i;
		if(e != i + b - j) continue;
		if(j < 0 || b - j < 0) continue;
		
		ans += C(a, i) * C(b, j) % mod;
		ans %= mod;
	}
	cout << ans << endl;
	
	return 0;
}