Submission #8795799


Source Code Expand

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

import numpy as np

N = int(readline())
AB = np.array(read().split(),np.int64)
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
Task C - 高速フーリエ変換
User maspy
Language Python (3.4.3)
Score 100
Code Size 3007 Byte
Status AC
Exec Time 969 ms
Memory 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