Submission #15155062


Source Code Expand

Copy
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

def fft_convolve(f, g):
    """
    数列 (多項式) f, g の畳み込みの計算.上下 15 bitずつ分けて計算することで,
    30 bit以下の整数,長さ 250000 程度の数列での計算が正確に行える.
    """
    Lf, Lg = f.shape[-1], g.shape[-1]
    Lg = g.shape[-1]
    L = Lf + Lg - 1
    fft_len = 1 << L.bit_length()
    fh, fl = f >> 15, f & (1 << 15) - 1
    gh, gl = g >> 15, g & (1 << 15) - 1

    def conv(f, g):
        Ff = np.fft.rfft(f, fft_len)
        Fg = np.fft.rfft(g, fft_len)
        h = np.fft.irfft(Ff * Fg)
        return np.rint(h)[..., :L].astype(np.int64) % MOD

    x = conv(fl, gl)
    z = conv(fh, gh)
    y = conv(fl + fh, gl + gh) - x - z
    return (x + (y << 15) + (z << 30)) % MOD

def coef_of_generating_function(P, Q, N):
    """compute the coefficient [x^N] P/Q of rational power series.

    Parameters
    ----------
    P : np.ndarray
        numerator.
    Q : np.ndarray
        denominator
        Q[0] == 1 and len(Q) == len(P) + 1 is assumed.
    N : int
        The coefficient to compute.
    """
    assert Q[0] == 1 and len(Q) == len(P) + 1

    def convolve(f, g):
        return fft_convolve(f, g)

    while N:
        Q1 = np.empty_like(Q)
        Q1[::2] = Q[::2]
        Q1[1::2] = MOD - Q[1::2]
        P = convolve(P, Q1)[N & 1::2]
        Q = convolve(Q, Q1)[::2]
        N >>= 1
    return P[0]

den = np.array([1,-1], np.int64)
for _ in range(5):
    den = np.convolve(den, np.array([1,-2,0,2,-1]))

num = np.zeros_like(den)[:-1]
num[5] = 1

def f(N):
    return coef_of_generating_function(num, den, N)

T = int(readline())
nums = map(int, read().split())
for n in nums:
    print(f(n))

Submission Info

Submission Time
Task F - Two Snuke
User maspy
Language Python (3.8.2)
Score 600
Code Size 1907 Byte
Status
Exec Time 537 ms
Memory 27296 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt
All 600 / 600 random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, sample_01.txt
Case Name Status Exec Time Memory
random_01.txt 175 ms 26868 KB
random_02.txt 533 ms 27296 KB
random_03.txt 537 ms 26916 KB
random_04.txt 341 ms 26924 KB
random_05.txt 346 ms 27020 KB
random_06.txt 340 ms 27296 KB
random_07.txt 340 ms 27084 KB
random_08.txt 358 ms 27268 KB
random_09.txt 362 ms 27020 KB
random_10.txt 332 ms 27192 KB
random_11.txt 324 ms 27200 KB
random_12.txt 331 ms 27200 KB
random_13.txt 322 ms 27016 KB
random_14.txt 345 ms 26952 KB
random_15.txt 350 ms 27076 KB
sample_01.txt 117 ms 27004 KB