#50 Problem
** Thoughts ** Since the total of (x, y) coordinates increases by 3 in one move, it cannot arrive unless the total of (x + y) is a multiple of 3. Let the movement of (i + 1, j + 2) be s times and the movement of (i + 2, j + 1) be t times. Solving the simultaneous equations of $ s + 2t = x, 2s + t = y $ yields $ s + t = x + y $. Once you have calculated $ s, t $, all you have to do is calculate where to do $ s $. However, if I honestly calculate $ _ {s + t} C _s $, the number is too large to calculate. Therefore, we use the calculation using the inverse element. Detailed calculation article
x, y = map(int,input().split())
def comb(n,k,mod,fac,ifac):
k = min(k,n-k)
return fac[n] * ifac[k] * ifac[n-k] % mod
def make_tables(mod,n):
fac = [1,1]
ifac = [1,1]
inverse = [0,1]
for i in range(2,n+1):
fac.append((fac[-1]*i)%mod)
inverse.append((-inverse[mod%i]* (mod//i)) % mod)
ifac.append((ifac[-1]* inverse[-1])%mod)
return fac, ifac
if x > y:
x, y = y, x
d = x+y
if d % 3 != 0:
print(0)
else:
s = (x+y)//3
t = x - s
if y > 2 * x: #Cannot arrive if y is greater than 2x
print(0)
else:
mod = 10**9+7
fac, ifac = make_tables(mod,s)
ans = comb(s,t,mod,fac,ifac)
print(ans)
difficult. See you again, good night.
Recommended Posts