abc 145 D - Knight (python)

abc で冷えた後なのでこういう問題は冷静に瞬殺できる。
明らかに全探索するわけがなく、数学的要素が強そうなので素晴らしい。
x,y に至るまで (+1,+2) を i 回、(+2,+1) を j 回したとすると、
x = i + 2*j, y = 2*i + j となって
答えが０でないためには
x + y = 3*( i+j ) から i+j が３の倍数であることが必要で、
i = (2*x - y)//3, j = (x - 2*y)//3 から
2*x >= y, 2*y >= x が必要で、
この時答えが n+m C n になると分かる。
nCr % mod はモジュラ係数を使う奴と、mod の逆元を使う奴の二種類をつかっている。
イメージだとモジュラの方が基本的には早く r == n//2 でも TLE しにくい。
abc 151 d とかはモジュラじゃないと TLE する

x,y = map(int,input().split())

if (x+y)%3 != 0:
  print(0)
  exit()
if 2*x < y:
  print(0)
  exit()
if 2*y < x:
  print(0)
  exit()
  
mod = 10**9+7
n = (2*x-y)//3
m = (2*y-x)//3

def make_array_for_comb(N, mod=10**9+7):
    fact = [1,1]
    fact_inv = [1,1]
    inv = [0,1]
    for i in range(2, N+1):
        fact.append((fact[-1]*i) % mod)
        inv.append((-inv[mod%i] * (mod//i)) % mod)
        fact_inv.append((fact_inv[-1]*inv[i]) % mod)
    return fact, fact_inv

def comb(n, r, mod=10**9+7):
  if (r < 0) or (n < r):
      return 0
  r = min(r, n - r)
  return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

fact, fact_inv = make_array_for_comb(n+m,mod)

print(comb(n+m,n,mod))