質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.91%

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

解決済

回答 2

投稿

  • 評価
  • クリップ 1
  • VIEW 3,064

score 12

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

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+1

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

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

参考: 数学的な性質 - yukicoder

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/08/05 16:50

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

    キャンセル

+1

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/08/05 16:51

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.91%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る