大きいnに対してコンビネーションを求める
凄く大きいnに対してCombinationを求める時、例えばを求めようと思っても愚直に計算するにはプログラムで扱える桁数を超えてしまう。
そこで、mで割った余り(modular) を求めさせることがある。
pythonで書いたのでサンプルコードを載せておく。
ただし、これを使うにはmはnを超える素数でないといけない。
サンプルコード
再帰を使っている。
def mod_combination(n, k, mod): # nCk (mod m) def mod_permutation(n, k, mod): if n<=k: return 1 else: return (n * mod_permutation(n-1,k,mod))%mod def mod_inv_permutation(k, mod): k, mod = int(k), int(mod) if k<=1: return 1 else: return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod