Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #15155062

Source Code Expand

Copy
```import sys
import numpy as np

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)

for n in nums:
print(f(n))```

#### Submission Info

Submission Time 2020-07-11 21:10:24+0900 F - Two Snuke maspy Python (3.8.2) 600 1907 Byte AC 537 ms 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