Pythonで、累算代入文とふつうの代入分とで処理時間が異なるのはなぜですか？（AtCoderの質問）

Question

AtCoder ABC 209のCについてのご質問です。
https://atcoder.jp/contests/abc209/tasks/abc209_c

n = int(input())
c = list(map(int, input().split()))
c = c.sorted()
ans = 1
for i in range(n):
    ans *= max(c[i]-i, 0) % 1000000007
print(ans)

というコードを書きましたがTLE（問題で指定された実行時間以内にプログラムが終了しない）になりました。

n = int(input())
c = list(map(int, input().split()))
c = c.sorted()
ans = 1
for i in range(n):
    ans = ans * max(c[i]-i, 0) % 1000000007
print(ans)

のように最後から2行目を書き換えると高速に動作し、AC（正答）になりました。

累算代入文とふつうの代入分とのちがいと認識していますが、なぜ処理時間が異なるのでしょうか？

https://docs.python.org/ja/3/reference/simple_stmts.html?highlight=%E4%BB%A3%E5%85%A5#augmented-assignment-statements

ドキュメントのここの部分は関係ありますか？
（読んでみましたがいまひとつよくわかりませんでした…）

Python 3.8.2です。

Answer 1

累算代入文は関係ありません。

Pythonの整数は無限桁が可能ですが、桁数が長くなると掛け算の時間がかかるためです。

以下と見て考えてください。

>>> c = [1000000006, 1000000005]
>>> ans = 1
>>> for i in range(len(c)):
...     ans *= max(c[i]-i, 0) % 1000000007
...
>>> print(ans)
1000000010000000024

と次は結果が違います。

>>> c = [1000000006, 1000000005]
>>> ans = 1
>>> for i in range(len(c)):
...     ans = ans * max(c[i]-i, 0) % 1000000007
...
>>> print(ans)
3

最初と同じ結果は以下です。

>>> c = [1000000006, 1000000005]
>>> ans = 1
>>> for i in range(len(c)):
...     ans = ans * (max(c[i]-i, 0) % 1000000007)
...
>>> print(ans)
1000000010000000024

Comments

[hacosato]

確認が大変遅くなり申し訳ありません。
理解しました。

最終行
print(ans)
を
print(ans % 1000000007)
に変えると結果は合うようでしたが、それだとサンプル作っていただいたように、c[i]が1000000007未満である限りansが大きくなり続けてしまいますね…。
わたしが提示した
ans *= max(c[i]-i, 0) % 1000000007
だと、かけるほうの数（max(c[i]-i, 0)）のみmodをとっていて、かけられる数（＝ans）のmodをとれていないのを見落としていました。

今回は乗算のたびにansのmodをとっていきたいので、最初にわたしが提示した通り、forの中を
ans = ans * max(c[i]-i, 0) % 1000000007
とする必要がありそうです。

ありがとうございました。