Pの競プロ記

競技プログラミングに関することを書きます。

KUPC 2014 D ハミング

概要


問題文はこちら
http://kupc2014.contest.atcoder.jp/tasks/kupc2014_d

解法


数学できないマンだったので、しめじたんの記事を参考にさせていただきました。(分かりやすい、神)
http://d.hatena.ne.jp/simezi_tan/20140710/1404932438

文字列s1とs2が与えられたときs1[i]とs2[i]を比較し、一致する箇所、しない箇所をカウントしておく。(今回はsameとdiffとした)

sameの場合、d1とd2のどちらとも+1するorしない…①
diffの場合、d1とd2のどちらかを+1する…②
ことができる。

そこでsame個のあるうちのx個でd1を増やし、diff個のあるうちy個でd1を増やすとすると、①、②から
d1 = x + y, d2 = x + diff - y となることが分かる。

xが分かればyも分かるのでxに関してループを回していけば良い。


ソースコード

#include <bits/stdc++.h>

#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long int lli;

const lli mod = 1e9 + 7;
lli inv[100000 + 1];

lli nCr(int n, int r) {
  lli res = 1;
  REP(i, 1, r + 1) {
    res = (res * (n - i + 1)) % mod;
    res = res * inv[i] % mod;
  }
  return res;
}

int main() {
  inv[1] = 1;
  REP(i, 2, 100000 + 1) {
    inv[i] = inv[mod % i] * (mod - mod / i) % mod;
  }
  
  string s1, s2;
  int d1, d2;
  
  cin >> s1 >> d1 >> s2 >> d2;
  
  int same = 0;
  int diff = 0;
  
  rep(i, s1.size()) {
    if(s1[i] == s2[i]) same++;
    else diff++;
  }

  lli ans = 0;

  rep(i, same + 1) {
    int x = i;
    int y = d1 - i;
    if(d2 != x + diff - y) continue;
    if(y < 0 || diff < y) continue;

    ans = (ans +  nCr(same, x) * nCr(diff, y) % mod) % mod;
  }

  cout << ans << endl;

  return 0;
}