結果

問題 No.1500 Super Knight
コンテスト
ユーザー convexineq
提出日時 2021-05-07 21:29:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 43 ms / 2,000 ms
コード長 591 bytes
コンパイル時間 446 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 60,680 KB
最終ジャッジ日時 2024-09-15 09:19:06
合計ジャッジ時間 3,154 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

def polymul(f,g):
    lf = len(f)
    lg = len(g)
    res = [0]*(lf+lg-1)
    for i in range(lf):
        for j in range(lg):
            res[i+j] += f[i]*g[j]
            res[i+j] %= MOD
    return res

def fps_nth_term(f,g,N):
    assert g[0] != 0
    while N:
        h = g[:]
        for i in range(1,len(g),2):
            h[i] = -h[i]
        f = polymul(f,h)[N%2:N+1:2]
        g = polymul(g,h)[:N+1:2]
        N //= 2
    return f[0]*pow(g[0],MOD-2,MOD)%MOD

n = int(input())
MOD = 10**9+7
print(fps_nth_term([1, 9, 32, 12, 999999971, 16], [1, 1000000004, 3, 1000000006, 0, 0, 0],n))
0