目次

• 問題
• 解説
• 計算量
• 解答

# 問題

https://atcoder.jp/contests/abc145/tasks/abc145_d

整数$X$, $Y$が与えられる.
$(0, 0)$から出発し、$(+1, +2)$、または$(+2, +1)$の移動のみを繰り返し$(X, Y)$まで到着するのに何通りの道があるかを答える問題.
到着不可能の場合は0通り.

# 解説

$X$, $Y$の最大値が$10^6$なので、$O(n \log n)$以下の計算量ではければ間に合いません.
移動の仕方が2通りしかないので、深さ優先探索でマス目を移動していき到達するケースを数えていくという解が思いつきますが、計算量は$O(2^n)$で間に合いません.
そこで移動の制約に着目し、$(+1, +2)$、$(+2, +1)$の移動をする回数をそれぞれ$n$, $m$とおくと、以下の連立方程式が得られます.

• (1) 移動するごとにxとy合わせて3ずつ増加するので、$X + Y$は３の倍数であるはずです.
• (2) 移動回数なので0以上です.また、必ず1は移動するのでXの最大値$10^6$以下です。
• (3) (4) 移動量を回数分だけ繰り返すと$(X, Y)$に到着するという意味です.

$\begin{cases} X + Y \equiv 0 \pmod{3} - (1) \\ 0 \leq n, m \leq 10^6 - (2) \\ n + 2m = X - (3) \\ 2n + m = Y - (4) \end{cases}$

(3) (4) を$n$、$m$について変形して、

$\begin{cases} m = (2X - Y)/3 - (5) \\ n = (Y - m)/2 - (6) \end{cases}$

ここまでで$(+1, +2)$の移動を$n$回、$(+2, +1)$を$m$回するということが求まりました.

次にゴールまでの道順を求めますが、これは$n$個の$(+1, +2)$と$m$個の$(+2, +1)$の並べ方の数だけあることになります.
全移動は$m + n$回で、その中で$n$個の位置を決めていくので$_{m+n}C_{n}$の組み合わせです.
あとは、これを$(n \log n)$以下の計算量で求めるだけです.

$_{n}C_{k}$は高校数学でも出てくるように以下の式で計算できます.

$_{n}C_{k} = \frac{n!}{k!(n - k)!}$

例えば、$_{5}C_{2}$なら、

$_{5}C_{2} = \frac{5!}{2!(5 - 2)!} = \frac{5 \cdot 4}{2 \cdot 1} = 10$

ここで$_{n}C_{k}$は3つのファクトリアルから計算出来ることが分かります.
これらはすべてまとめてボトムアップ動的計画法で$O(\log n)$で計算出来ます.

$10^9 + 7$で割った答えを求めるので、割り算のところだけそのままでは計算
できないので、割り算の代わりに逆元との積に置き換える必要があります.

$_{n}C_{k} = n! \times (k!(n - k)!)^{-1} \pmod{10^9+7}$

逆元は拡張ユークリッドというアルゴリズムで$O(\log n)$で求める事ができます.

# 計算量

$O(n + m)$

# 解答

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

Int X_, Y_;
Int fac[MAX_M];

void input() {
  cin >> X_ >> Y_;
}

void buildFact() {
    fac[0] = fac[1] = 1;
    for (int i = 2; i < MAX_M; i++){
        fac[i] = fac[i - 1] * i % MOD;
    }
}

// Extended Euclid
Int modinv(Int a, Int p) {
  Int b = p, u = 1, v = 0;
  while (b) {
    Int t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= p;
  if (u < 0) u += p;
  return u;
}

Int nCk(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * modinv((fac[k] * fac[n - k] % MOD), MOD) % MOD;
}

void solve() {
  buildFact();
  if ((X_ + Y_) % 3 != 0) {
    cout << 0 << endl;
    return;
  }

  Int m = (2 * X_ - Y_) / 3;
  Int n = (Y_ - m)/2;
  if (m < 0 || n < 0) {
    cout << 0 << endl;
    return;
  }

  cout << nCk(m + n, n) << endl;
}

int main(void) {
  input();
  solve();
  return 0;
}