復習 4/18,4/19

O(n)で前計算することで、各nCrをO(1)で求められるようにする。

mod = 10**9+7
MAX = 10**5+1 #nは10**5までを想定
fact = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact[i] = (fact[i-1]*i)%mod
inv = [1]*(MAX+1)
for i in range(2, MAX+1):
    inv[i] = inv[mod%i]*(mod-mod//i)%mod
fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1]*inv[i]%mod
def comb(n, r):
    if n < r:
        return 0
    return fact[n]*fact_inv[n-r]*fact_inv[r] % mod

atcoder.jp
例えば(10**5)**(10**5)を10**9+7で割りたい、みたいな気持ちになった時に、for文で10**5を10**5回回してるとどエライ事になってしまう。a**bをmで割った余りは、pow(a,b,m)で高速に求められる。

atcoder.jp
ナップサックはi番目のものまで見たときに使う、使わないのふた通りの場合分けをちゃんと行うこと。サボるとどっかでミスる。