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

Submission #8795799

Source Code Expand

Copy
```import sys

import numpy as np

A = AB[::2]
B = AB[1::2]

class NumberTheoreticTransformation():
# 2^n-th root of unity
ntt_prime_data = {
17: (3, 4),
998244353: (31, 23)
}

def __init__(self, ntt_len, MOD = 998244353):
"""
ntt_len：2べきが必要
MOD：準備してあるいくつか限定
"""
self.N = ntt_len
N = ntt_len
self.lgN = N.bit_length() - 1
self.bit_reverse_index = self.bit_reverse(self.lgN)
self.MOD = MOD
self.Ninv = pow(N, MOD - 2, MOD)
r, d = NumberTheoreticTransformation.ntt_prime_data[MOD]
assert d >= self.lgN
r = pow(r, 2 ** (d - self.lgN), MOD) # 1の原子 N 乗根
powr = self.make_zeta_power(r)
self.Zeta = [powr[N//2::N//(1<<(i+1))] for i in range(self.lgN)]
self.ZetaInv = [powr[N//2:0:-N//(1<<(i+1))] for i in range(self.lgN)]

def bit_reverse(self, lgN):
"""
N = 2 ** lgN までの lgN 桁bit反転
bit_reverse(3) = np.array([000,100,010,110,001,101,011,111]) = np.array([0,4,2,6,1,5,3,7])
"""
N = 1 << lgN
A = np.empty(N, np.int32)
A[0] = 0
for i in range(lgN):
x = 1 << i
A[:x] <<= 1
A[x:x+x] = A[:x] + 1
return A

def make_zeta_power(self, r):
MOD = self.MOD
x = np.empty(self.N, np.int64)
x[0] = 1; x[1] = r
for n in range(self.lgN):
x[1 << n: 1 << (n+1)] = x[:1 << n] * (r * x[(1 << n) - 1] % MOD) % MOD
return x

def ntt(self, A, inverse):
MOD = self.MOD
A = A[self.bit_reverse_index]
N = self.N; lgN = self.lgN
M = 1

Zeta = self.Zeta if not inverse else self.ZetaInv
for Z in Zeta:
A = A.reshape(-1,M+M)
u = A[:,:M]
t = A[:,M:]
t *= Z[None,:]
t += u
u <<= 1
u -= t
M <<= 1
A %= MOD
A = A.ravel()
if inverse:
A *= self.Ninv
A %= MOD
return A

def convolve(self, A, B):
MOD = self.MOD
LA = len(A); LB = len(B)
N = self.N
A = np.resize(A, N); A[LA:] = 0
B = np.resize(B, N); B[LB:] = 0
fA = self.ntt(A, inverse = False)
fB = self.ntt(B, inverse = False)
fA *= fB; fA %= MOD
return self.ntt(fA, inverse = True)

MOD = 998244353
ntt_len = 1 << (N + N).bit_length()
ntt = NumberTheoreticTransformation(ntt_len, MOD)
C = ntt.convolve(A,B)[:N + N - 1]

print(0)
print('\n'.join(map(str,C)))```

Submission Info

Submission Time 2019-12-05 15:03:51+0900 C - 高速フーリエ変換 maspy Python (3.4.3) 100 3007 Byte AC 969 ms 35016 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
 AC × 1
 AC × 33
Set Name Test Cases
Sample 00_sample_01
All 00_sample_01, 01_00_01, 01_01_19, 01_02_31, 01_03_22, 01_04_31, 01_05_40, 01_06_15, 01_07_39, 01_08_28, 01_09_30, 01_10_23, 01_11_33, 01_12_11, 01_13_28, 01_14_41, 01_15_26, 01_16_49, 01_17_34, 01_18_02, 01_19_33, 01_20_29, 02_00_51254, 02_01_82431, 02_02_17056, 02_03_34866, 02_04_6779, 02_05_65534, 02_06_65535, 02_07_65536, 02_08_65537, 02_09_65538, 02_10_100000
Case Name Status Exec Time Memory
00_sample_01 AC 342 ms 21732 KB
01_00_01 AC 150 ms 12508 KB
01_01_19 AC 149 ms 12208 KB
01_02_31 AC 151 ms 12508 KB
01_03_22 AC 151 ms 12208 KB
01_04_31 AC 151 ms 12508 KB
01_05_40 AC 152 ms 12508 KB
01_06_15 AC 150 ms 12208 KB
01_07_39 AC 152 ms 12208 KB
01_08_28 AC 154 ms 12208 KB
01_09_30 AC 149 ms 12208 KB
01_10_23 AC 148 ms 12208 KB
01_11_33 AC 149 ms 12508 KB
01_12_11 AC 152 ms 12208 KB
01_13_28 AC 150 ms 12208 KB
01_14_41 AC 150 ms 12208 KB
01_15_26 AC 151 ms 12208 KB
01_16_49 AC 149 ms 12508 KB
01_17_34 AC 150 ms 12508 KB
01_18_02 AC 149 ms 12208 KB
01_19_33 AC 149 ms 12508 KB
01_20_29 AC 149 ms 12208 KB
02_00_51254 AC 585 ms 23632 KB
02_01_82431 AC 909 ms 31732 KB
02_02_17056 AC 310 ms 16760 KB
02_03_34866 AC 489 ms 20688 KB
02_04_6779 AC 204 ms 14048 KB
02_05_65534 AC 659 ms 26896 KB
02_06_65535 AC 670 ms 26896 KB
02_07_65536 AC 820 ms 30464 KB
02_08_65537 AC 804 ms 30464 KB
02_09_65538 AC 820 ms 30472 KB
02_10_100000 AC 969 ms 35016 KB