結果

問題 No.1559 Next Rational
ユーザー Kiri8128Kiri8128
提出日時 2021-06-26 00:23:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 43 ms / 2,000 ms
コード長 5,113 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 55,644 KB
最終ジャッジ日時 2024-06-25 09:01:01
合計ジャッジ時間 1,615 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
54,044 KB
testcase_01 AC 41 ms
54,684 KB
testcase_02 AC 40 ms
54,492 KB
testcase_03 AC 41 ms
55,212 KB
testcase_04 AC 41 ms
54,580 KB
testcase_05 AC 41 ms
54,904 KB
testcase_06 AC 40 ms
53,628 KB
testcase_07 AC 41 ms
54,404 KB
testcase_08 AC 41 ms
54,432 KB
testcase_09 AC 41 ms
54,652 KB
testcase_10 AC 43 ms
54,492 KB
testcase_11 AC 42 ms
54,168 KB
testcase_12 AC 41 ms
55,384 KB
testcase_13 AC 42 ms
55,644 KB
testcase_14 AC 41 ms
54,704 KB
testcase_15 AC 42 ms
54,928 KB
testcase_16 AC 42 ms
54,652 KB
testcase_17 AC 41 ms
55,596 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# エスパー
# 線形漸化式の補間
# maspyさん解法: https://atcoder.jp/contests/abc198/submissions/21664115
# Wikipedia: https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm

p1, g1, ig1 = 104857601, 3, 34952534
p2, g2, ig2 = 111149057, 3, 37049686
p3, g3, ig3 = 113246209, 7, 16178030
z1 = 439957480532171226961446
z2 = 879898597692195524486915
z3 = 8496366309945115353
ppp = p1 * p2 * p3
W1 = [pow(g1, (p1 - 1) >> i, p1) for i in range(22)]
W2 = [pow(g2, (p2 - 1) >> i, p2) for i in range(22)]
W3 = [pow(g3, (p3 - 1) >> i, p3) for i in range(22)]
iW1 = [pow(ig1, (p1 - 1) >> i, p1) for i in range(22)]
iW2 = [pow(ig2, (p2 - 1) >> i, p2) for i in range(22)]
iW3 = [pow(ig3, (p3 - 1) >> i, p3) for i in range(22)]

def fft1(k, f):
    for l in range(k, 0, -1):
        d = 1 << l - 1
        U = [1]
        for i in range(d):
            U.append(U[-1] * W1[l] % p1)
        
        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]) % p1, U[j] * (f[s] - f[s+d]) % p1
def fft2(k, f):
    for l in range(k, 0, -1):
        d = 1 << l - 1
        U = [1]
        for i in range(d):
            U.append(U[-1] * W2[l] % p2)
        
        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]) % p2, U[j] * (f[s] - f[s+d]) % p2
def fft3(k, f):
    for l in range(k, 0, -1):
        d = 1 << l - 1
        U = [1]
        for i in range(d):
            U.append(U[-1] * W3[l] % p3)
        
        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]) % p3, U[j] * (f[s] - f[s+d]) % p3

def ifft1(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]) % p1, (f[j] - f[j+d]) % p1
                u = u * iW1[l] % p1
def ifft2(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]) % p2, (f[j] - f[j+d]) % p2
                u = u * iW2[l] % p2
def ifft3(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]) % p3, (f[j] - f[j+d]) % p3
                u = u * iW3[l] % p3

def convolve(a, b):
    n0 = len(a) + len(b) - 1
    if len(a) < 50 or len(b) < 50:
        ret = [0] * n0
        if len(a) > len(b): a, b = b, a
        for i, aa in enumerate(a):
            for j, bb in enumerate(b):
                ret[i+j] = (ret[i+j] + aa * bb) % P
        return ret
    
    k = (n0).bit_length()
    n = 1 << k
    a = a + [0] * (n - len(a))
    b = b + [0] * (n - len(b))
    
    a1 = [x % p1 for x in a]
    a2 = [x % p2 for x in a]
    a3 = [x % p3 for x in a]
    b1 = [x % p1 for x in b]
    b2 = [x % p2 for x in b]
    b3 = [x % p3 for x in b]
    fft1(k, a1), fft1(k, b1)
    fft2(k, a2), fft2(k, b2)
    fft3(k, a3), fft3(k, b3)
    for i in range(n): a1[i] = a1[i] * b1[i] % p1
    for i in range(n): a2[i] = a2[i] * b2[i] % p2
    for i in range(n): a3[i] = a3[i] * b3[i] % p3
    ifft1(k, a1)
    ifft2(k, a2)
    ifft3(k, a3)
    invn1 = pow(n, p1 - 2, p1)
    invn2 = pow(n, p2 - 2, p2)
    invn3 = pow(n, p3 - 2, p3)
    for i in range(n0): a1[i] = a1[i] * invn1 % p1
    for i in range(n0): a2[i] = a2[i] * invn2 % p2
    for i in range(n0): a3[i] = a3[i] * invn3 % p3
    return [(x1 * z1 + x2 * z2 + x3 * z3) % ppp % P for x1, x2, x3 in zip(a1[:n0], a2[:n0], a3[:n0])]

def find_generating_function(A):
    N = len(A)
    B = [1]
    C = [1]
    l, m, b = 0, 1, 1
    for i in range(N):
        d = A[i]
        for j in range(1, l + 1):
            d = (d + C[j] * A[i-j]) % mod
        if d == 0:
            m += 1
            continue
        T = C[:]
        ibd = pow(b, mod - 2, mod) * d % mod
        C += [0] * (len(B) + m - len(C))
        for j in range(len(B)):
            C[j + m] = (C[j + m] - ibd * B[j]) % mod
        if l * 2 <= i:
            B = T
            l, m, b = i + 1 - l, 1, d
        else:
            m += 1
    g = C
    f = convolve(A[:len(g)], g)[:len(g) - 1]    
    return f, g

def coef_of_generating_function(f, g, n):
    assert g[0] == 1 and len(g) == len(f) + 1
 
    while n:
        gg = [mod - a if i & 1 else a for i, a in enumerate(g)]
        f = convolve(f, gg)[n&1::2]
        g = convolve(g, gg)[::2]
        n >>= 1
    return f[0]

P = 10 ** 9 + 7
mod = 10 ** 9 + 7
n, a, b, k = map(int, input().split())

A = [a, b]
for _ in range(30):
    A.append((A[-1] ** 2 + k) % P * pow(A[-2], P - 2, P) % P)

f, g = find_generating_function(A)

n = n - 1
print(coef_of_generating_function(f, g, n))
0