結果
問題 |
No.829 成長関数インフレ中
|
ユーザー |
![]() |
提出日時 | 2020-05-03 17:51:45 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 489 ms / 2,000 ms |
コード長 | 712 bytes |
コンパイル時間 | 292 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 27,464 KB |
最終ジャッジ日時 | 2024-06-13 01:49:26 |
合計ジャッジ時間 | 4,552 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines MOD = 10**9 + 7 N, B, *S = map(int, read().split()) counter = [0] * N for x in S: counter[x] += 1 powB = [1] * N for n in range(1, N): powB[n] = powB[n - 1] * B % MOD used = 0 f = 1 df = 0 for n in counter[::-1]: if not n: continue total = 1 stay = 1 for i in range(1, n + 1): total *= used + i stay *= used + i - 1 total %= MOD stay %= MOD a = stay b = total - stay # a + bx をかける g = a + b * B dg = b f, df = f * g, f * dg + df * g f %= MOD df %= MOD used += n print(df * B % MOD)