結果
問題 | No.931 Multiplicative Convolution |
ユーザー |
![]() |
提出日時 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
import sys#input = sys.stdin.readlineinput = 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) + 7MOD = 998244353#dx = [1,0,-1,0]#dy = [0,1,0,-1]import randomdef prime_factorize(n):ret = []#if n == 1:# ret.append((1,1))# return retcnt = 0while n % 2 == 0:cnt += 1n //= 2if cnt > 0:ret.append((2,cnt))i = 3while i * i <= n:cnt = 0while n % i == 0:cnt += 1n //= ielse:if cnt != 0: #cnt==0の時は追加しないret.append((i,cnt))i += 2if 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-1for pi, dummy in L:x = (p-1)//piif pow(a,x,p) == 1:breakelse:return art = 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 * 17d = len(a) + len(b) - 1 #畳み込むうえで必要な長さ#2^nで始めてd以上となるnn = 1while (1<<n) < d:n += 1N = 1 << nw = 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] *= Ninvc[i] %= MODreturn cdef FFT(a,w): #Σ(ai * w^(ik))#偶奇に分けて再帰的。各回でO(N)。再帰でO(logN)。N = len(a)if N == 1: return aeven = a[::2]odd = a[1::2] #1から始まって2個ごと(1個おき)ww = w * w % MODEVEN = FFT(even, ww%MOD)ODD = FFT(odd, ww%MOD)A = [0] * Nwk = 1 #w^kfor k in range(N):A[k] = (EVEN[k%(N//2)] + wk * ODD[k%(N//2)] %MOD) %MODwk = wk * w %MODreturn Adef 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]%MODprint(ans);exit()#原始根gAN = [0]*PBN = [0]*Pg = get_root(P)#print(g)v = 1for i in range(P-1): #g^i = vとなるものを求める。AN[i] = A[v]BN[i] = B[v]v *= gv %= P#print(AN,BN)CN = convolution(AN,BN)#print(CN)C = [0]*Pv = 1for i in range(len(CN)):C[v] += CN[i]C[v] %= MODv *= gv %= Pprint(*C[1:])if __name__ == '__main__':main()