結果

問題 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0