結果
問題 | No.2975 単調増加部分積 |
ユーザー |
![]() |
提出日時 | 2024-11-29 21:40:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 933 ms / 10,000 ms |
コード長 | 1,050 bytes |
コンパイル時間 | 154 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 93,568 KB |
最終ジャッジ日時 | 2024-11-29 21:40:12 |
合計ジャッジ時間 | 6,259 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
from collections import *N, M, P = map(int, input().split())def conv(a, b):res = [0] * (len(a) + len(b) - 1)for i in range(len(a)):for j in range(len(b)):res[i + j] = (res[i + j] + a[i] * b[j] % P) % Preturn resn = min(1000000, P - 1)fact = [1 for i in range(n + 1)]for i in range(1, n + 1):fact[i] = fact[i - 1] * i % Pfact_inv = [1 for i in range(n + 1)]fact_inv[-1] = pow(fact[-1], P - 2, P)for i in range(n, 0, -1):fact_inv[i - 1] = fact_inv[i] * i % Pdef binom(n, r):if n < r or n < 0 or r < 0:return 0res = fact_inv[n - r] * fact_inv[r] % Pres *= fact[n]res %= Preturn resF = deque([[1, i] for i in range(1, N + 1)])for i in range(N - 1):f = F.popleft()g = F.popleft()h = conv(f, g)while len(h) > M + 1:h.pop()F.append(h)f = F[0][:]ans = 0for i in range(1, M + 1):res = fact[M - i] * binom(M, i) % Pres = res * binom(N - i, M - i) % Pres = res * f[i] % Pans = (ans + res) % PX = fact[N] * fact_inv[N - M] % Pprint(ans * pow(X, P - 2, P) % P)