atcoder

# # Problem

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

Int X_, Y_;
Int fac[MAX_M];

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

void buildFact() {
fac = fac = 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;
} Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!