結果

問題 No.931 Multiplicative Convolution
ユーザー ygd.ygd.
提出日時 2022-03-05 17:33:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 668 ms / 2,000 ms
コード長 3,483 bytes
コンパイル時間 200 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 171,084 KB
最終ジャッジ日時 2024-07-19 23:18:53
合計ジャッジ時間 7,867 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
54,272 KB
testcase_01 AC 44 ms
54,656 KB
testcase_02 AC 44 ms
54,400 KB
testcase_03 AC 48 ms
54,784 KB
testcase_04 AC 47 ms
54,528 KB
testcase_05 AC 57 ms
62,592 KB
testcase_06 AC 83 ms
77,184 KB
testcase_07 AC 153 ms
84,096 KB
testcase_08 AC 652 ms
170,972 KB
testcase_09 AC 640 ms
167,104 KB
testcase_10 AC 653 ms
166,168 KB
testcase_11 AC 644 ms
168,032 KB
testcase_12 AC 658 ms
166,644 KB
testcase_13 AC 668 ms
170,212 KB
testcase_14 AC 663 ms
171,084 KB
testcase_15 AC 657 ms
171,040 KB
testcase_16 AC 648 ms
170,324 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
#input = sys.stdin.readline
input = sys.stdin.buffer.readline #文字列はダメ
#sys.setrecursionlimit(1000000)
#import bisect
#import itertools
#import random
#from heapq import heapify, heappop, heappush
#from collections import defaultdict 
#from collections import deque
#import copy
#import math
#from functools import lru_cache
#@lru_cache(maxsize=None)
#MOD = pow(10,9) + 7
MOD = 998244353
#dx = [1,0,-1,0]
#dy = [0,1,0,-1]


import random

def prime_factorize(n):
    ret = []
    #if n == 1:
    #    ret.append((1,1))
    #    return ret
    cnt = 0
    while n % 2 == 0:
        cnt += 1
        n //= 2
    if cnt > 0:
        ret.append((2,cnt))
    i = 3
    while i * i <= n:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n //= i
        else:
            if cnt != 0: #cnt==0の時は追加しない
                ret.append((i,cnt))
            i += 2
    if n != 1:
        ret.append((n,1))
    return ret #(素因数、何乗)

def get_root(p):
    #p-1の素因数
    L = prime_factorize(p-1)
    #p-1の素因数pi全てに対してa^((p-1)/pi) != 1であることを確かめる。
    while True:
        a = random.randint(2,p-1) #2 <= a <= p-1
        for pi, dummy in L:
            x = (p-1)//pi
            if pow(a,x,p) == 1:
                break
        else:
            return a


rt = 3
#原始根rtとしたときのn乗根.rt^MOD-1 = 1なので肩をnで割ればよい。
def pr(n):
    return pow(rt, (MOD-1)//n, MOD)

def convolution(a,b):
    #3は998244353の原始根. 3^998244352 = 1
    #998244352 = 2^23 * 7 * 17
    d = len(a) + len(b) - 1 #畳み込むうえで必要な長さ
    #2^nで始めてd以上となるn
    n = 1
    while (1<<n) < d:
        n += 1
    N = 1 << n
    w = pr(N)
    #配列a,bの長さを2のべき乗にする。
    a += [0] * (N - len(a))
    b += [0] * (N - len(b))
    A = FFT(a,w)
    B = FFT(b,w)
    #フーリエ変換した後は畳み込みが単なる掛け算になる。
    C = [A[i] * B[i] % MOD for i in range(N)]
    #print(w)
    winv = pow(w, MOD-2,MOD)
    c = FFT(C, winv) #フーリエ逆変換においてはwをwinvにすればよい
    Ninv = pow(N, MOD-2,MOD) #逆変換の時には1/Nをかける必要がある。
    for i in range(N):
        c[i] *= Ninv
        c[i] %= MOD
    
    return c

def FFT(a,w): #Σ(ai * w^(ik))
    #偶奇に分けて再帰的。各回でO(N)。再帰でO(logN)。
    N = len(a)
    if N == 1: return a
    even = a[::2]
    odd = a[1::2] #1から始まって2個ごと(1個おき)
    ww = w * w % MOD
    EVEN = FFT(even, ww%MOD)
    ODD = FFT(odd, ww%MOD)
    A = [0] * N
    wk = 1 #w^k
    for k in range(N):
        A[k] = (EVEN[k%(N//2)] + wk * ODD[k%(N//2)] %MOD) %MOD
        wk = wk * w %MOD
    
    return A


def main():
    P = int(input())
    A = [0] + list(map(int,input().split()))
    B = [0] + list(map(int,input().split()))
    if P == 2:
        ans = A[1]*B[1]%MOD
        print(ans);exit()

    #原始根g
    AN = [0]*P
    BN = [0]*P
    g = get_root(P)
    #print(g)
    v = 1
    for i in range(P-1): #g^i = vとなるものを求める。
        AN[i] = A[v]
        BN[i] = B[v]
        v *= g
        v %= P
    #print(AN,BN)
    CN = convolution(AN,BN)
    #print(CN)
    C = [0]*P
    v = 1
    for i in range(len(CN)):
        C[v] += CN[i]
        C[v] %= MOD
        v *= g
        v %= P
    print(*C[1:])
        
    
if __name__ == '__main__':
    main()
0