組み合わせの数, nCr, binomial(n, r)

n から r を取り出す取り出し方，すなわち nCr ではあるが，n, r によってはとんでもなく大きな数になる。

そもそも，そんな数が必要なことは普通はない。競技プログラミング（略して，競プロ）の世界では，それでは困るので（？），「1000000007 で割った余り（つまり剰余だね）」を答えさせる。そこでテクニックとして，いろいろあるが，以下のような Python プログラムを書くことができる。

from functools import reduce

# フェルマーの小定理を応用した(組み合わせの数 % mod)
def comb(n, r, mod=10 ** 9 + 7):
    numerator = reduce(lambda x, y: x * y % mod, range(n-r+1, n+1))
    denominator = reduce(lambda x, y: x * y % mod, range(1, r+1))
    return numerator * pow(denominator, mod - 2, mod) % mod

comb(2021, 37) # 717019240
comb(2021, 37, 4) # 0　この解は誤り

Julia だと

function comb(n, r, mod=10^9 + 7)
    red(x, y) = x * y % mod
    numerator = reduce(red, n-r+1:n)
    denominator = reduce(red, 1:r)
    numerator * powermod(denominator, mod - 2, mod) % mod
end

comb(2021, 37) # 717019240
comb(2021, 37, 4) # 0　この解は誤り

2021C37 mod 4 は

binomial(big(2021), 37) % 4 # 3 正しい答え

でなければならない。

ちなみに，

binomial(big(2021), 37) % (10^9 + 7) # 717019240

なので，正しい。

要するに，このプログラムは mod が素数であるときのみ正しい答えを返す。

素数でないときは，不正な値をしれっと返す。