結果

問題 No.42 貯金箱の溜息
コンテスト
ユーザー onakasuitacity
提出日時 2020-11-08 13:29:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,322 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 144,000 KB
最終ジャッジ日時 2024-07-22 15:06:46
合計ジャッジ時間 12,753 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
INF = 1 << 60
MOD = 10**9 + 9
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
    if inverse:
        N_inv = pow(N, prime - 2, prime)
        f = [a * N_inv % prime for a in f]
    return f

def convolve(f, g, MOD):
    N = 1 << (len(f) + len(g) - 2).bit_length()
    primes = [167772161, 469762049, 1224736769]
    Ffs, Fgs = [_fmt([a % MOD for a in f] + [0] * (N - len(f)), p) for p in primes], [_fmt([b % MOD for b in g] + [0] * (N - len(g)), p) for p in primes]
    fgs = [_fmt([a * b % p for a, b in zip(Ff, Fg)], p, inverse = True) for Ff, Fg, p in zip(Ffs, Fgs, primes)]
    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 dfs(n, P, Q):
    if n == 0:
        return P[0]
    Q_neg = [v * (1 - 2 * (i&1)) for i, v in enumerate(Q)]
    return dfs(n >> 1, convolve(P, Q_neg, MOD)[n&1::2], convolve(Q, Q_neg, MOD)[::2])

def resolve():
    P = [1]
    Q = [0] * (667)
    Q[0] = 1
    for k in (1, 5, 10, 50, 100, 500):
        for i in range(len(Q) - k - 1, -1, -1):
            Q[i + k] -= Q[i]

    for _ in range(int(input())):
        print(dfs(int(input()), P, Q))
resolve()
0