#50 Problème
** Pensées ** Puisque le total des coordonnées (x, y) augmente de 3 en un seul mouvement, il ne peut arriver que si le total de (x + y) est un multiple de 3. Soit (i + 1, j + 2) se déplacer s fois et (i + 2, j + 1) se déplacer t fois. La résolution des équations simultanées de $ s + 2t = x, 2s + t = y $ donne $ s + t = x + y $. Une fois que vous avez calculé $ s, t $, il ne vous reste plus qu'à calculer où faire $ s $. Cependant, si je calcule honnêtement $ _ {s + t} C _s $, le nombre est trop grand pour être calculé. Par conséquent, nous utilisons le calcul en utilisant l'élément inverse. Article de calcul détaillé
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: #Impossible d'arriver si y est supérieur à 2x
print(0)
else:
mod = 10**9+7
fac, ifac = make_tables(mod,s)
ans = comb(s,t,mod,fac,ifac)
print(ans)
difficile. A bientôt, bonne nuit.
Recommended Posts