#50 Problem
** Gedanken ** Da sich die Summe der (x, y) -Koordinaten in einem Zug um 3 erhöht, kann sie nur dann eintreffen, wenn die Summe der (x + y) ein Vielfaches von 3 ist. Lassen Sie (i + 1, j + 2) s-mal und (i + 2, j + 1) t-mal bewegen. Das Lösen der simultanen Gleichungen von $ s + 2t = x, 2s + t = y $ ergibt $ s + t = x + y $. Sobald Sie $ s, t $ berechnet haben, müssen Sie nur noch berechnen, wo $ s $ zu tun ist. Wenn ich jedoch ehrlich $ _ {s + t} C _s $ berechne, ist die Zahl zu groß, um berechnet zu werden. Daher verwenden wir die Berechnung mit dem inversen Element. Detaillierter Berechnungsartikel
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: #Kann nicht ankommen, wenn y größer als 2x ist
print(0)
else:
mod = 10**9+7
fac, ifac = make_tables(mod,s)
ans = comb(s,t,mod,fac,ifac)
print(ans)
schwer. Wir sehen uns wieder, gute Nacht.
Recommended Posts