結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | maspy |
提出日時 | 2020-03-28 16:08:29 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 389 ms / 5,000 ms |
コード長 | 2,306 bytes |
コンパイル時間 | 135 ms |
コンパイル使用メモリ | 11,112 KB |
実行使用メモリ | 68,808 KB |
最終ジャッジ日時 | 2023-08-30 17:56:00 |
合計ジャッジ時間 | 10,077 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 124 ms
29,860 KB |
testcase_01 | AC | 124 ms
29,916 KB |
testcase_02 | AC | 137 ms
29,860 KB |
testcase_03 | AC | 136 ms
29,748 KB |
testcase_04 | AC | 147 ms
29,788 KB |
testcase_05 | AC | 147 ms
29,864 KB |
testcase_06 | AC | 145 ms
29,864 KB |
testcase_07 | AC | 147 ms
29,828 KB |
testcase_08 | AC | 145 ms
29,856 KB |
testcase_09 | AC | 145 ms
29,804 KB |
testcase_10 | AC | 141 ms
29,836 KB |
testcase_11 | AC | 138 ms
29,748 KB |
testcase_12 | AC | 139 ms
29,728 KB |
testcase_13 | AC | 137 ms
29,676 KB |
testcase_14 | AC | 136 ms
29,844 KB |
testcase_15 | AC | 139 ms
29,772 KB |
testcase_16 | AC | 146 ms
29,960 KB |
testcase_17 | AC | 138 ms
29,664 KB |
testcase_18 | AC | 140 ms
29,884 KB |
testcase_19 | AC | 143 ms
29,892 KB |
testcase_20 | AC | 133 ms
29,788 KB |
testcase_21 | AC | 389 ms
68,808 KB |
testcase_22 | AC | 131 ms
29,768 KB |
testcase_23 | AC | 137 ms
31,120 KB |
testcase_24 | AC | 249 ms
48,064 KB |
testcase_25 | AC | 240 ms
46,428 KB |
testcase_26 | AC | 235 ms
45,960 KB |
testcase_27 | AC | 269 ms
50,712 KB |
testcase_28 | AC | 157 ms
34,104 KB |
testcase_29 | AC | 368 ms
65,448 KB |
testcase_30 | AC | 138 ms
29,844 KB |
testcase_31 | AC | 131 ms
29,704 KB |
testcase_32 | AC | 139 ms
29,748 KB |
testcase_33 | AC | 137 ms
29,836 KB |
testcase_34 | AC | 138 ms
29,684 KB |
testcase_35 | AC | 139 ms
29,828 KB |
testcase_36 | AC | 138 ms
29,664 KB |
testcase_37 | AC | 137 ms
29,764 KB |
testcase_38 | AC | 138 ms
29,852 KB |
testcase_39 | AC | 140 ms
29,724 KB |
ソースコード
#!/usr/bin/ python3.8 import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines MOD = 10 ** 9 + 7 import numpy as np def fft_convolve(f, g, MOD=MOD): """ 数列 (多項式) f, g の畳み込みの計算.上下 15 bitずつ分けて計算することで, 30 bit以下の整数,長さ 250000 程度の数列での計算が正確に行える. """ fft = np.fft.rfft ifft = np.fft.irfft Lf = len(f) Lg = len(g) L = Lf + Lg - 1 fft_len = 1 << L.bit_length() fl = f & (1 << 15) - 1 fh = f >> 15 gl = g & (1 << 15) - 1 gh = g >> 15 def conv(f, g): return ifft(fft(f, fft_len) * fft(g, fft_len))[:L] x = conv(fl, gl) % MOD y = conv(fl + fh, gl + gh) % MOD z = conv(fh, gh) % MOD a, b, c = map(lambda x: (x + .5).astype(np.int64), [x, y, z]) return (a + ((b - a - c) << 15) + (c << 30)) % MOD def coef_of_generating_function(P, Q, N): """compute the coefficient [x^N] P/Q of rational power series. Parameters ---------- P : np.ndarray numerator. Q : np.ndarray denominator Q[0] == 1 and len(Q) == len(P) + 1 is assumed. N : int The coefficient to compute. """ def convolve(f, g): return fft_convolve(f, g, MOD) while N: Q1 = Q.copy() Q1[1::2] = np.negative(Q1[1::2]) if N & 1: P = convolve(P, Q1)[1::2] else: P = convolve(P, Q1)[::2] Q = convolve(Q, Q1)[::2] N >>= 1 return P[0] def solve_1(N, K, A): S = [0] * (K + 1) for i, x in enumerate(A, 1): S[i] = S[i - 1] + x for n in range(N + 1, K + 1): S[n] = 2 * S[n - 1] - S[n - N - 1] S[n] %= MOD return (S[K] - S[K - 1]) % MOD, S[K] def solve_2(N, K, A): S = [0] * (N + 1) for i, x in enumerate(A, 1): S[i] = S[i - 1] + x S = np.array(S[:N + 1], np.int64) Q = np.zeros(N + 2, np.int64) Q[0] = 1 Q[1] = -2 Q[N + 1] = 1 P = np.convolve(S, Q)[:N + 1] x = coef_of_generating_function(P, Q, K) y = coef_of_generating_function(P, Q, K - 1) return (x - y) % MOD, x N, K, *A = map(int, read().split()) solve = solve_2 if N <= 30 else solve_1 print(*solve(N, K, A))