結果
問題 | No.931 Multiplicative Convolution |
ユーザー | ygd. |
提出日時 | 2022-03-05 17:32:17 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,483 bytes |
コンパイル時間 | 276 ms |
コンパイル使用メモリ | 82,632 KB |
実行使用メモリ | 171,304 KB |
最終ジャッジ日時 | 2024-07-19 23:16:13 |
合計ジャッジ時間 | 9,027 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 42 ms
54,656 KB |
testcase_01 | AC | 43 ms
54,912 KB |
testcase_02 | WA | - |
testcase_03 | AC | 42 ms
54,528 KB |
testcase_04 | AC | 42 ms
54,656 KB |
testcase_05 | AC | 50 ms
62,848 KB |
testcase_06 | AC | 78 ms
77,400 KB |
testcase_07 | AC | 159 ms
84,480 KB |
testcase_08 | AC | 705 ms
171,304 KB |
testcase_09 | AC | 689 ms
167,560 KB |
testcase_10 | AC | 709 ms
166,792 KB |
testcase_11 | AC | 720 ms
168,124 KB |
testcase_12 | AC | 693 ms
166,520 KB |
testcase_13 | AC | 712 ms
170,336 KB |
testcase_14 | AC | 717 ms
171,164 KB |
testcase_15 | AC | 714 ms
171,248 KB |
testcase_16 | AC | 710 ms
170,456 KB |
ソースコード
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[0]*B[0]%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()