Contest Duration: - (local time) (120 minutes) Back to Home

Submission #9424214

Source Code Expand

Copy
import sys

import numpy as np

MOD = 10 ** 9 + 7

def cumprod(A, MOD = MOD):
L = len(A); Lsq = int(L**.5+1)
A = np.resize(A, Lsq**2).reshape(Lsq,Lsq)
for n in range(1,Lsq):
A[:,n] *= A[:,n-1]; A[:,n] %= MOD
for n in range(1,Lsq):
A[n] *= A[n-1,-1]; A[n] %= MOD
return A.ravel()[:L]
def make_fact(U, MOD = MOD):
x = np.arange(U, dtype = np.int64); x[0] = 1
fact = cumprod(x, MOD)
x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
fact_inv = cumprod(x, MOD)[::-1]
return fact,fact_inv

def convolve(f, g, MOD=MOD):
"""
数列 (多項式) f, g の畳み込みの計算．上下 15 bitずつ分けて計算することで，
30 bit以下の整数，長さ 250000 程度の数列での計算が正確に行える．
"""
Lf = len(f); Lg = len(g); L = Lf + Lg - 1
fl = f & (1 << 15) - 1; fh = f >> 15
gl = g & (1 << 15) - 1; gh = g >> 15
if L < (1<<8):
conv = lambda f,g: \
np.convolve(f,g) % MOD
else:
fft = np.fft.rfft; ifft = np.fft.irfft; fft_len = 1 << L.bit_length()
conv = lambda f,g: \
np.rint(ifft(fft(f,fft_len) * fft(g,fft_len))[:L]).astype(np.int64) % MOD
x = conv(fl, gl)
z = conv(fh, gh)
y = conv(fl+fh, gl+gh)
return (x + ((y - x - z) << 15) + (z << 30)) % MOD

fact, fact_inv = make_fact(10 ** 5)

f = np.zeros(N+1,np.int64)
f[0] = 1
for a in A:
g = fact[N-a:N+1] * fact_inv[0:a+1] % MOD * fact_inv[N-a] % MOD
g = g[::-1]
g *= fact_inv[:len(g)]; g %= MOD
f = convolve(f,g)[:N+1]

f *= fact[:N+1]; f %= MOD

#### Submission Info

Submission Time 2020-01-11 21:24:02+0900 C - Cookie Distribution maspy Python (3.4.3) 800 1843 Byte AC 342 ms 25456 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
 AC × 2
 AC × 32
Set Name Test Cases
Sample sample_01, sample_02
All max_01, max_02, max_03, max_04, max_05, max_06, max_07, max_08, max_09, max_10, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, random_small_01, random_small_02, random_small_03, random_small_04, random_small_05, random_small_06, random_small_07, random_small_08, random_small_09, random_small_10, sample_01, sample_02
Case Name Status Exec Time Memory
max_01 AC 342 ms 25456 KB
max_02 AC 178 ms 16308 KB
max_03 AC 178 ms 16308 KB
max_04 AC 178 ms 16308 KB
max_05 AC 178 ms 16308 KB
max_06 AC 180 ms 16308 KB
max_07 AC 179 ms 16308 KB
max_08 AC 178 ms 16308 KB
max_09 AC 177 ms 16308 KB
max_10 AC 178 ms 16308 KB
random_01 AC 167 ms 16308 KB
random_02 AC 166 ms 16308 KB
random_03 AC 171 ms 16308 KB
random_04 AC 169 ms 16308 KB
random_05 AC 166 ms 16308 KB
random_06 AC 165 ms 16308 KB
random_07 AC 174 ms 16308 KB
random_08 AC 169 ms 16308 KB
random_09 AC 173 ms 16308 KB
random_10 AC 172 ms 16308 KB
random_small_01 AC 165 ms 16308 KB
random_small_02 AC 166 ms 16308 KB
random_small_03 AC 165 ms 16308 KB
random_small_04 AC 165 ms 16308 KB
random_small_05 AC 167 ms 16308 KB
random_small_06 AC 164 ms 16292 KB
random_small_07 AC 165 ms 16308 KB
random_small_08 AC 165 ms 16308 KB
random_small_09 AC 166 ms 16308 KB
random_small_10 AC 164 ms 16308 KB
sample_01 AC 165 ms 16308 KB
sample_02 AC 174 ms 16308 KB