結果

問題 No.980 Fibonacci Convolution Hard
ユーザー 👑 rin204rin204
提出日時 2022-03-24 16:41:26
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,223 bytes
コンパイル時間 213 ms
コンパイル使用メモリ 82,208 KB
実行使用メモリ 545,444 KB
最終ジャッジ日時 2024-10-13 00:51:02
合計ジャッジ時間 7,211 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def convolve(a, b, MOD=998244353):
    def primitive_root_constexpr():
        if MOD == 998244353:
            return 3
        elif MOD == 2:
            return 1
        elif MOD == 200003:
            return 2
        elif MOD == 167772161:
            return 3
        elif MOD == 469762049:
            return 3
        elif MOD == 754974721:
            return 11
        divs = [0] * 20
        divs[0] = 2
        cnt = 1
        x = (MOD - 1) // 2
        while x % 2 == 0:
            x //= 2
        i = 3
        while i * i <= x:
            if x % i == 0:
                divs[cnt] = i
                cnt += 1
                while x % i == 0:
                    x //= i
            i += 2
        if x > 1:
            divs[cnt] = x
            cnt += 1
        g = 2
        while 1:
            ok = True
            for i in range(cnt):
                if pow(g, (MOD - 1) // divs[i], MOD) == 1:
                    ok = False
                    break
            if ok:
                return g
            g += 1
        

    g = primitive_root_constexpr()
    ig = pow(g, MOD - 2, MOD)
    W = [pow(g, (MOD - 1) >> i, MOD) for i in range(30)]
    iW = [pow(ig, (MOD - 1) >> i, MOD) for i in range(30)]
    def fft(k, f):
        for l in range(k, 0, -1):
            d = 1 << l - 1
            U = [1]
            for i in range(d):
                U.append(U[-1] * W[l] % MOD)
            
            for i in range(1 << k - l):
                for j in range(d):
                    s = i * 2 * d + j
                    f[s], f[s+d] = (f[s] + f[s+d]) % MOD, U[j] * (f[s] - f[s+d]) % MOD
    
    def ifft(k, f):
        for l in range(1, k + 1):
            d = 1 << l - 1
            for i in range(1 << k - l):
                u = 1
                for j in range(i * 2 * d, (i * 2 + 1) * d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % MOD, (f[j] - f[j+d]) % MOD
                    u = u * iW[l] % MOD
 
    n0 = len(a) + len(b) - 1
    k = (n0).bit_length()
    n = 1 << k
    a = a + [0] * (n - len(a))
    b = b + [0] * (n - len(b))
    fft(k, a)
    fft(k, b)
    for i in range(n):
        a[i] = a[i] * b[i] % MOD
    ifft(k, a)
    invn = pow(n, MOD - 2, MOD)
    for i in range(n0):
        a[i] = a[i] * invn % MOD
    del a[n0:]
    return a

def modinv(a, MOD):
    b = MOD
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        u -= t * v
        a, b = b, a
        u, v = v, u
    u %= MOD
    if u < 0:
        u += m
    return u

def Garner(M, R):
    m_prod = M[0]
    C = R[0]
    for m, r in zip(M[1:], R[1:]):
        t = (r - C) * modinv(m_prod, m) % m
        C += t * m_prod
        m_prod *= m
    return C


MOD = 10 ** 9 + 7

p = int(input())
Q = int(input())
Q = [int(input()) for _ in range(Q)]
n = max(Q)
dp = [0, 1]
for _ in range(n - 2):
    x = p * dp[-1] + dp[-2]
    dp.append(x % MOD)
    

MOD_ = [998244353, 469762049, 754974721]
lst = [[] for _ in range(2 * n - 1)]
for mod in MOD_:
    C = convolve(dp, dp, mod)
    for i in range(2 * n - 1):
        lst[i].append(C[i])

ans = [0] * n
for i in range(n):
    ans[i] = Garner(MOD_, lst[i]) % MOD
for q in Q:
    print(ans[q - 2])
0