Python3で桁あふれするような計算(数万の階乗)が終了しない ABC042 D問題

Question

Atcoderというサイトのいろはちゃんとマス目 / Iroha and a Grid
という問題をpython3で実装しました。
http://abc042.contest.atcoder.jp/tasks/arc058_b

基本的な解法は合っていると思うのですが、計算する値の桁数がとてつもなく多くなってしまうような場合、いつまで経ってもプログラムの処理が終わりません。
何が原因か、教えていただけないでしょうか。

実装したコードはこちらです。

H,W,A,B = [int(n) for n in input().split(" ")]
answers = []
for total in range(B,W):
    disp = 1
    for n in range(1,total+(H-A)):
        disp *= n
    for m in range(1,H-A ):
        disp //= m
    for t in range(1,total + 1):
        disp //= t
    answers.append(disp%( 10 ** 9 + 7))

for cnt,total in enumerate(range(B,W)):
    disp = 1
    for n in range(1,(W - total - 1) + (H - (H - A))):
        disp  *= n
    for m in range(1,H- (H - A)):
        disp //= m
    for t in range(1,W-total):
        disp //= t
    answers[cnt] *= disp%( 10 ** 9 + 7)
print(sum(answers) %( 10 ** 9 + 7))

処理が終わらなくなってしまう入力値はこちらです。

100000 100000 44444 55555

想定出力値はこちらです。

738162020

どうぞ、よろしくお願い致します。

Answer 1

多倍長整数は便利ですがとても遅いです。数十回程度の演算なら気にならない程度ですが、大きな桁数を何万回と計算場合はとてつもない時間とメモリを消費します。このような場合は内部で多倍長整数に切り替わらないようにする必要があります。全体の考え方はあっていると思いますので、毎回10^9+7の余りをもとめて計算するようにしてみてください。以下、注意事項です。

• 剰余の加法・減法・乗法はそのままできます。10^9+7の余り同士を加算・減算・乗算してたものに10^9+7の余りを求めれば、元の値を加算・減算・乗算したもの10^9+7の余りと同じになると言うことです。
• 剰余の除法だけが特別です。10^9+7が素数であることを利用します。説明すると長くなりますので、これは調べてみてください。
• この問題の2秒はスクリプト言語では割とシビアです。単純に毎回求めると全然間に合いません。各階乗の剰余などと言った必要になるものはあらかじめ求めて配列等に入れておくなどの工夫をしてください。(遅いRubyでも解けましたのでPythonでも大丈夫だと思います。ただ、Pythonで解けた人はまだいないようです)

参考: 数学的な性質 - yukicoder

Comments

[tomatosan]

ありがとうございました。非常に勉強になります。
剰余の除法については、フェルマーの小定理と二分累乗法を用いればよろしいのでしょうか。

Answer 2

modinvで検索してみてください。
これを使えば素数Mを法としたときの逆数を求めることができるので、Mの余りを取りながら割り算をすることができるようになります。
ただし、modinv自体も計算量があるので、予め計算するなどの工夫が必要になることが多いです。

Comments

[tomatosan]

ありがとうございます。数学的知識も必要なのですね。
勉強になりました。