組み合わせ計算とLucasの定理

先日必要となった、パスカルの三角形を短時間で生成するために利用した計算方法をまとめる。

コード

# Lucasの定理 mCn % p
def lucas(m,n,p):
    # 素数pなのに0や1が入ってしまったときの回避
    if p < 2:
        return combi(m,n)
    # 各数の商と余りを計算
    dm1, dm2 = divmod(m, p)
    dn1, dn2 = divmod(n, p)
    # 2C3のような組み合わせを求めようとしたら0を返す
    if dm2 < dn2 or dm1 < dn1:
        return 0
    # 定理に従って計算
    return combi(dm1, dn1)*combi(dm2, dn2)%p

# 二項係数 nCk の計算
def combi(n, k):
    if n < k:
        return 0
    k = min(k, n-k)
    if k==0:
        val = 1
    else:
        val = combi(n-1, k-1)*n/k
    return val