～ MOD ～ チートシート

目次

割り算
コンビネーション（nCr）

割り算以外の四則演算
べき乗　pow(x,n,MOD)

はじめに

チートシートの扱いついてはここを読んでください

割り算

mod.py

MOD = 1000000007

def div(a, b):
  return ((a % MOD) * pow(b, MOD-2, MOD)) % MOD

自分で割り算用の関数を定義する
MODが素数の場合、Aの逆元はA**(MOD-2)となる（フェルマーの小定理を使うらしい）

mod.py

print(A * pow(B, -1, MOD) % MOD)

python3.8以降ならpow()でも簡単に逆元を求められる（pypyだとエラーを吐くので注意）

コンビネーション

mod.py

MOD = 1000000007

def div(a, b):
  return ((a % MOD) * pow(b, MOD-2, MOD)) % MOD

def Combination(n,r):
  bunnshi = 1
  bunnbo = 1
  for i in range(r):
    bunnshi = (bunnshi*(n-i))%MOD
    bunnbo = (bunnbo*(i+1))%MOD
  return div(bunnshi,bunnbo)

nCr = \frac{n!}{r!(n-r)!} = \frac{n(n-1)...(n-r+1)}{r(r-1)...1}\\

をMOD計算する
割り算ができれば簡単に実装できる

割り算以外の四則演算

mod.py

MOD = 1000000007

(a + b) % MOD
(a - b) % MOD
(a * b) % MOD

まあ自明
pythonは負の整数に対しても余りを計算できるので、引き算の時に(a - b + MOD) % MODとしなくても正しく計算できる

べき乗

mod.py

MOD = 1000000007

pow(x, n, MOD)

x ** n % MODを早く正確に計算できる
詳しくはこちら