AtCoder Regular Contest 046 D: うさぎとマス目

問題

arc046.contest.atcoder.jp

解法

AtCoder Regular Contest 046 from AtCoder Inc.

www.slideshare.net

組み合わせを高速に求める数論ライブラリを手に入れた。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const int MAX = 1000000;

class Combination {
 private:
  vector<ll> inv, fact, invfact;
  Combination() {}

 public:
  Combination(int max) {
    inv.assign(max + 1, 0);
    fact.assign(max + 1, 0);
    invfact.assign(max + 1, 0);
    inv[1] = 1;
    for (int i = 2; i <= max; i++)
      inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
    fact[0] = invfact[0] = 1;
    for (int i = 1; i <= max; i++) fact[i] = fact[i - 1] * i % MOD;
    for (int i = 1; i <= max; i++) invfact[i] = invfact[i - 1] * inv[i] % MOD;
  }

  ll get(ll x, ll y) {
    return fact[x] * invfact[y] % MOD * invfact[x - y] % MOD;
  }
};

ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

int main() {
  ll H, W;
  cin >> H >> W;
  ll d = gcd(H, W);
  Combination c(d);

  ll ans = 0;
  ll cycle2 = H * W / d;
  for (ll i = 0; i <= d; ++i) {
    ll pattern = c.get(d, i);
    ll j = d - i;

    ll horizontal = W / gcd(W, i);
    ll vertical = H / gcd(H, j);
    ll cycle = lcm(vertical, horizontal);

    if (cycle == cycle2) {
      ans += pattern;
      while (ans > MOD) ans -= MOD;
    }
  }

  cout << ans << endl;
}