ABC145

AtCoder Beginner Contest 145 - AtCoder は「D - Knight」が突破できず

最初は何も考えずメモ化再帰で解こうとしたけどメモ化はちっとも効果なし
図を描いてみたら単なるパスカルの三角形
じゃあnCk求めればいいんだもらったな
こう書いたら半分TLEになりました
999999 999999で1分以上かかってた

def comb(n, k):
    u = 1
    l = 1
    for i in range(min(k, n - k)):
        u *= n - i
        l *= i + 1
    return u // l

ここだけ復習

nCrを求めるにも技があるみたい

よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 - けんちょんの競プロ精進記録

のコードをPythonにしただけ
これでAC

MAX = 1000000
MOD = 1000000007

fac = [None] * MAX
finv = [None] * MAX
inv = [None] * MAX

def comb_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

def comb(n, k):
    if n < 0 or k < 0 or n < k:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

comb_init()
x, y = [int(x) for x in input().split()]

def solve(x, y):

    if (x + y) % 3 != 0:
        return 0

    n = (2 * y - x) // 3
    m = (2 * x - y) // 3
    if n < 0 or m < 0:
        return 0

    return comb(n + m, n)

print(solve(x, y))

掛け算は毎回modを取る
割り算は逆数を掛け算する

fac[k]がk!、
inv[k]がkの逆数
finv[k]がk!の逆数

fac[n] * (finv[k] * finv[n - k] % MOD) % MODは
nCk の n!/(k! * (n - k)!) そのもの

問題は逆数
kの逆数と言えば1/kで1未満の数になりそうだけど
kに何かを掛けたら1になる数、と考えると
modの世界では自然数でそういう数がありうる
求め方は賢すぎるのでちゃんとは理解していない