Pythonで毎日AtCoder #50

はじめに

前回
今日で#50。はやい。ABC164-Dを書く予定でしたが疑問が解決できてないので保留

#50

問題

考えたこと
一回の移動で(x,y)座標の合計は3増えるので(x+y)の合計が3の倍数でないなら到着できません。(i+1,j+2)の移動をs回、(i+2,j+1)の移動をt回とします。$s+2t=x,2s+t=y$の連立方程式を解くと、$s+t=x+y$となります。$s,t$が計算できたら、あとは$s$をどこで行うかを計算するだけです。しかし、愚直に$_{s+t} C _s$を計算すると数が大きすぎて計算できません。そこで、逆元を用いた計算を使います。詳しい計算の記事

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: #yが2xよりも大きいと到着できません
        print(0)
    else:
        mod = 10**9+7

        fac, ifac = make_tables(mod,s)
        ans = comb(s,t,mod,fac,ifac)
        print(ans)

まとめ

難しい。ではまた、おやすみなさい。