組み合わせ数（nCr）の答えにmodを用いる際の関数のコピペ用

tl;dr

atcoder.jp

この問題で、nCrで10**9+7で割ったあまりを、求める部分で、 nCrの関数をこれにしたらうまく回ったよ、って話。

def nCr(n, r, MOD):
    if n < r:
        return 0
    if n-r < r:
        r = n-r
    comb = 1
    for x in range(n-r+1, n+1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, r+1):
        d = (d * x) % MOD
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

参考、というか関数丸パクリした提出がこちら。

atcoder.jp

場合の数 1―作業性の特訓 書き上げて解く順列 (思考力算数練習張シリーズ 23)

ことのはじまり

ABC145のD問題"Knight"で、

見覚えある数字の分布だなぁ、と気づいたのが11/16 22:00の時点。

これが、パスカルの三角形であり、パスカルの三角形はnCrと三角形の座標(N段目のM番目）を知ることができれば解けると知ったのが22:20の時点。

座標はX+=1,Y-=1し続けて（逆でもよい）、

2 * Y == Xとなった場所と、

その操作をした回数でN，Mを出せるのこともわかり、

残りはnCrだ・・・と思って、気合入れてググりまくり、

拾ってきたソースをちょっと改変して、出したのがこのソース

atcoder.jp

testcaseも全部時間内に通って、残り6分ちょっと、なんとかD突破・・・と思ったら、

1ケースでWAが出て通らなかったのが昨日のハイライト。

ぐぬぬ。

nCrの恐怖

組み合わせ数の計算で、nが100000とか超えてくると値が爆発します。

なので、出題者はだいたい10**9 + 7で割った余り、など言ってくることが多いです。

しかしnCrの場合は割り算があり、pythonは巨大数の割り算は精度が危ういため、

よく死ぬことがある。

んで、参考にしたnCr(mod対応版)を用いて、

そこだけ差し替えたら通ってしまったとさ・・・。

ぐぬぬ。