Table of contents

• Problem
• Explanation
• Time complexity
• Solution

# Problem

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

Given integers $X$, $Y$, report the number of ways from $(0, 0)$ to $(X, Y)$.
You can move to only either $(+1, +2)$ or $(+2, +1)$.
If impossible, report 0.

# Explanation

$\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}$

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

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

For instance, _{5}C_

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

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

Inverse is computed with Extended Euclidean algorithm in $O(\log n)$.

# Time complexity

$O(n + m)$

# Solution

// 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;
}