結果
問題 | No.503 配列コレクション |
ユーザー | maspy |
提出日時 | 2020-04-08 12:41:14 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 347 ms / 2,000 ms |
コード長 | 1,505 bytes |
コンパイル時間 | 215 ms |
コンパイル使用メモリ | 10,720 KB |
実行使用メモリ | 107,788 KB |
最終ジャッジ日時 | 2023-09-25 12:00:27 |
合計ジャッジ時間 | 11,240 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 345 ms
107,660 KB |
testcase_01 | AC | 342 ms
107,636 KB |
testcase_02 | AC | 343 ms
107,476 KB |
testcase_03 | AC | 341 ms
107,716 KB |
testcase_04 | AC | 136 ms
29,680 KB |
testcase_05 | AC | 347 ms
107,688 KB |
testcase_06 | AC | 339 ms
107,660 KB |
testcase_07 | AC | 344 ms
107,588 KB |
testcase_08 | AC | 343 ms
107,616 KB |
testcase_09 | AC | 347 ms
107,596 KB |
testcase_10 | AC | 342 ms
107,788 KB |
testcase_11 | AC | 339 ms
107,672 KB |
testcase_12 | AC | 342 ms
107,608 KB |
testcase_13 | AC | 340 ms
107,688 KB |
testcase_14 | AC | 337 ms
107,632 KB |
testcase_15 | AC | 341 ms
107,460 KB |
testcase_16 | AC | 344 ms
107,608 KB |
testcase_17 | AC | 347 ms
107,620 KB |
testcase_18 | AC | 341 ms
107,548 KB |
testcase_19 | AC | 136 ms
29,772 KB |
testcase_20 | AC | 339 ms
107,504 KB |
testcase_21 | AC | 136 ms
29,816 KB |
testcase_22 | AC | 338 ms
107,536 KB |
testcase_23 | AC | 135 ms
29,744 KB |
testcase_24 | AC | 134 ms
29,740 KB |
ソースコード
#!/usr/bin/ python3.8 import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import numpy as np MOD = 10 ** 9 + 7 N, K, D = map(int, read().split()) def cumprod(A, MOD=MOD): L = len(A) Lsq = int(L**.5 + 1) A = np.resize(A, Lsq**2).reshape(Lsq, Lsq) for n in range(1, Lsq): A[:, n] *= A[:, n - 1] A[:, n] %= MOD for n in range(1, Lsq): A[n] *= A[n - 1, -1] A[n] %= MOD return A.ravel()[:L] def make_fact(U, MOD=MOD): x = np.arange(U, dtype=np.int64) x[0] = 1 fact = cumprod(x, MOD) x = np.arange(U, 0, -1, dtype=np.int64) x[0] = pow(int(fact[-1]), MOD - 2, MOD) fact_inv = cumprod(x, MOD)[::-1] fact.flags.writeable = False fact_inv.flags.writeable = False return fact, fact_inv def make_power(a, L, MOD=MOD): B = L.bit_length() x = np.empty((1 << B), np.int64) x[0] = 1 for n in range(B): x[1 << n:1 << (n + 1)] = x[:1 << n] * a % MOD a *= a a %= MOD x = x[:L] x.flags.writeable = False return x L = N % (K - 1) if not L: L = K - 1 S = (N - L) // (K - 1) if L == 1: answer = pow(D, S, MOD) print(answer) exit() fact, fact_inv = make_fact(2 * 10 ** 6 + 10) power = make_power(D, S + 1) coef = fact[L - 2: L + S - 1][::-1] * fact_inv[0: S + 1][::-1] % MOD * fact_inv[L - 2] % MOD x = (coef * power % MOD).sum() % MOD answer = x * L % MOD if D == 1: answer = L print(answer)