結果

問題 No.1307 Rotate and Accumulate
ユーザー tpynerivertpyneriver
提出日時 2020-12-04 14:28:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 477 ms / 5,000 ms
コード長 3,784 bytes
コンパイル時間 374 ms
コンパイル使用メモリ 86,768 KB
実行使用メモリ 186,900 KB
最終ジャッジ日時 2023-10-13 03:07:38
合計ジャッジ時間 11,702 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 292 ms
149,396 KB
testcase_01 AC 292 ms
149,428 KB
testcase_02 AC 287 ms
149,192 KB
testcase_03 AC 289 ms
149,220 KB
testcase_04 AC 294 ms
149,408 KB
testcase_05 AC 295 ms
149,288 KB
testcase_06 AC 292 ms
149,136 KB
testcase_07 AC 290 ms
149,504 KB
testcase_08 AC 430 ms
168,124 KB
testcase_09 AC 445 ms
167,240 KB
testcase_10 AC 412 ms
179,352 KB
testcase_11 AC 385 ms
170,364 KB
testcase_12 AC 397 ms
164,984 KB
testcase_13 AC 339 ms
163,904 KB
testcase_14 AC 361 ms
169,092 KB
testcase_15 AC 472 ms
186,156 KB
testcase_16 AC 475 ms
186,156 KB
testcase_17 AC 470 ms
186,060 KB
testcase_18 AC 459 ms
184,032 KB
testcase_19 AC 477 ms
186,692 KB
testcase_20 AC 474 ms
186,900 KB
testcase_21 AC 288 ms
148,928 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
readline = sys.stdin.readline

import sys
readline = sys.stdin.readline

MOD = 998244353
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci
frac, fraci = frac(1341398)
MOD = 998244353
pr = 3
LS = 20
class NTT:
    def __init__(self):
        self.N0 = 1<<LS
        omega = pow(pr, (MOD-1)//self.N0, MOD)
        omegainv = pow(omega, MOD-2, MOD)
        self.w = [0]*(self.N0//2)
        self.winv = [0]*(self.N0//2)
        self.w[0] = 1
        self.winv[0] = 1
        for i in range(1, self.N0//2):
            self.w[i] = (self.w[i-1]*omega)%MOD
            self.winv[i] = (self.winv[i-1]*omegainv)%MOD
        used = set()
        for i in range(self.N0//2):
            if i in used:
                continue
            j = 0
            for k in range(LS-1):
                j |= (i>>k&1) << (LS-2-k)
            used.add(j)
            self.w[i], self.w[j] = self.w[j], self.w[i]
            self.winv[i], self.winv[j] = self.winv[j], self.winv[i]
        
    def _fft(self, A):
        M = len(A)
        bn = 1
        hbs = M>>1
        while hbs:
            for j in range(hbs):
                A[j], A[j+hbs] = A[j] + A[j+hbs], A[j] - A[j+hbs]
                if A[j] > MOD:
                    A[j] -= MOD
                if A[j+hbs] < 0:
                    A[j+hbs] += MOD
            for bi in range(1, bn):
                wi = self.w[bi]
                for j in range(bi*hbs*2, bi*hbs*2+hbs):
                    A[j], A[j+hbs] = (A[j] + wi*A[j+hbs])%MOD, (A[j] - wi*A[j+hbs])%MOD
            bn <<= 1
            hbs >>= 1

    def _ifft(self, A):
        M = len(A)
        bn = M>>1
        hbs = 1
        while bn:
            for j in range(hbs):
                A[j], A[j+hbs] = A[j] + A[j+hbs], A[j] - A[j+hbs]
                if A[j] > MOD:
                    A[j] -= MOD
                if A[j+hbs] < 0:
                    A[j+hbs] += MOD
            for bi in range(1, bn):
                winvi = self.winv[bi]
                for j in range(bi*hbs*2, bi*hbs*2+hbs):
                    A[j], A[j+hbs] = (A[j] + A[j+hbs])%MOD, winvi*(A[j] - A[j+hbs])%MOD
            bn >>= 1
            hbs <<= 1
    
    def convolve(self, A, B):
        LA = len(A)
        LB = len(B)
        LC = LA+LB-1
        M = 1<<(LC-1).bit_length()
        A += [0]*(M-LA)
        B += [0]*(M-LB)
        self._fft(A)
        self._fft(B)
        C = [0]*M
        for i in range(M):
            C[i] = A[i]*B[i]%MOD
        self._ifft(C)
        minv = pow(M, MOD-2, MOD)
        for i in range(LC):
            C[i] = C[i]*minv%MOD
        return C[:LC]
        
        return C
    
    def inverse(self, A):
        LA = len(A)
        dep = (LA-1).bit_length()
        M = 1<<dep
        A += [0]*(M-LA)
        
        g = [pow(A[0], MOD-2, MOD)]
        for n in range(dep):
            dl = 1<<(n+1)
            f = A[:dl]
            fg = self.convolve(f, g[:])[:dl]
            fgg = self.convolve(fg, g[:])[:dl]
            ng = [None]*dl
            for i in range(dl//2):
                ng[i] = (2*g[i]-fgg[i])%MOD
            for i in range(dl//2, dl):
                ng[i] = MOD-fgg[i]
            g = ng[:]
        return g[:LA]
    
    def integral(self, A):
        A = [1] + [A[i]*fraci[i+2]%MOD for i in range(len(A))]


N, Q = map(int, readline().split())
A = list(map(int, readline().split()))
R = list(map(int, readline().split()))

Nt = NTT()
table = [0]*N
for r in R:
    table[(N-r)%N] += 1

B = Nt.convolve(table, A)

ans = [0]*N
for i in range(len(B)):
    ans[i%N] += B[i]

print(*ans)
0