結果
問題 | No.980 Fibonacci Convolution Hard |
ユーザー | onakasuitacity |
提出日時 | 2020-10-26 22:32:09 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,140 bytes |
コンパイル時間 | 163 ms |
コンパイル使用メモリ | 82,164 KB |
実行使用メモリ | 435,076 KB |
最終ジャッジ日時 | 2024-07-21 21:44:11 |
合計ジャッジ時間 | 8,318 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
ソースコード
import sys INF = 1 << 60 MOD = 10**9 + 7 # 998244353 sys.setrecursionlimit(2147483647) input = lambda:sys.stdin.readline().rstrip() def _fmt(f, prime, root = 3, inverse = False): N = len(f) logN = (N - 1).bit_length() base = pow(root, (prime - 1) // N * (1 - 2 * inverse) % (prime - 1), prime) step = N for k in range(logN): step >>= 1 w = pow(base, step, prime) wj = 1 nf = [0] * N for j in range(1 << k): for i in range(1 << logN - k - 1): s, t = i + 2 * j * step, i + (2 * j + 1) * step ns, nt = i + j * step, i + j * step + (N >> 1) nf[ns], nf[nt] = (f[s] + f[t] * wj) % prime, (f[s] - f[t] * wj) % prime wj = (wj * w) % prime f = nf return f def convolution(f, g, MOD): N = 1 << (len(f) + len(g) - 2).bit_length() primes = [167772161, 469762049, 1224736769] N_invs = (pow(N, p - 2, p) for p in primes) Ffs, Fgs = [_fmt(f + [0] * (N - len(f)), p) for p in primes], [_fmt(g + [0] * (N - len(g)), p) for p in primes] fgs = [_fmt([a * b % p * N_inv % p for a, b in zip(Ff, Fg)], p, inverse = True) for Ff, Fg, p, N_inv in zip(Ffs, Fgs, primes, N_invs)] fg = [] primes.append(MOD) for R in zip(*fgs): coeffs, consts = [1] * 4, [0] * 4 for i in range(3): a, b, u, v = coeffs[i], primes[i], 1, 0 while b: a, b, u, v = b, a - a // b * b, v, u - a // b * v t = (R[i] - consts[i]) * (u % primes[i]) % primes[i] for j in range(i + 1, 4): consts[j] = (consts[j] + t * coeffs[j]) % primes[j] coeffs[j] = coeffs[j] * primes[i] % primes[j] fg.append(consts[-1]) if len(fg) == len(f) + len(g) - 1: return fg def resolve(): p = int(input()) queries = [int(input()) - 2 for _ in range(int(input()))] k = max(queries) f = [0] * (k + 1) f[1] = 1 for i in range(2, k + 1): f[i] = (p * f[i - 1] + f[i - 2]) % MOD f2 = convolution(f, f, MOD) print(*(f2[i] for i in queries), sep = '\n') resolve()