結果
問題 | No.931 Multiplicative Convolution |
ユーザー |
|
提出日時 | 2019-11-23 01:05:55 |
言語 | Java (openjdk 23) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,174 bytes |
コンパイル時間 | 2,792 ms |
コンパイル使用メモリ | 82,440 KB |
実行使用メモリ | 69,432 KB |
最終ジャッジ日時 | 2024-10-11 06:42:40 |
合計ジャッジ時間 | 25,814 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 TLE * 9 |
ソースコード
import java.math.*;import java.util.*;import java.io.*;class Main{public static void main(String[] args){new Main().run();}void run() {Scanner sc = new Scanner(System.in);long MODULO = 998244353;long ROOT = 3;long P = sc.nextLong();long[] A = new long[(int) P + 1];long[] B = new long[(int) P + 1];for (int i = 1; i < P; ++i) {A[i] = sc.nextLong();}for (int i = 1; i < P; ++i) {B[i] = sc.nextLong();}ArrayList<Long> div = new ArrayList<Long>();for (long i = 2; i * i <= P - 1; ++i) {if ((P - 1) % i == 0) div.add((P - 1) / i);}long root = -1;if (P == 2) root = 1;else if (P == 3) root = 2;out:for (long i = 2; root == -1 && i <= P - 1; ++i) {for (long d : div) {if (pow(i, d, P) == 1) {continue out;}}root = i;break;}long[] A2 = new long[(int) (2 * P)];long[] B2 = new long[(int) (2 * P)];for (int i = 1; i <= P - 1; ++i) {A2[i] = A[(int) pow(root, i, P)];B2[i] = B[(int) pow(root, i, P)];}long[] C2 = mul(A2, B2, MODULO, ROOT);long[] C = new long[(int) P];for (int i = 0; i < C2.length; ++i) {C[(int) pow(root, i, P)] += C2[i];}PrintWriter pw = new PrintWriter(System.out);for (int i = 1; i < C.length; ++i) {pw.print(C[i]%MODULO+(i==C.length-1?"\n":" "));}pw.close();}long[] mul(long[] a, long[] b, long MODULO, long root) {int n = Integer.highestOneBit(a.length + b.length) << 1;a = Arrays.copyOf(a, n);b = Arrays.copyOf(b, n);a = fft(a, false, MODULO, root);b = fft(b, false, MODULO, root);for (int i = 0; i < n; ++i)a[i] = a[i] * b[i] % MODULO;a = fft(a, true, MODULO, root);long inv = inv(n, MODULO);for (int i = 0; i < n; ++i) {a[i] = a[i] * inv % MODULO;}return a;}long[] fft(long[] a, boolean inv, long MODULO, long root) {int n = a.length;int c = 0;for (int i = 1; i < n; ++i) {for (int j = n >> 1; j > (c ^= j); j >>= 1);if (c > i) {long d = a[i];a[i] = a[c];a[c] = d;}}for (int i = 1; i < n; i *= 2) {long w = pow(root, (MODULO - 1) / (2 * i), MODULO);if (inv)w = inv(w, MODULO);for (int j = 0; j < n; j += 2 * i) {long wn = 1;for (int k = 0; k < i; ++k) {long u = a[j + k];long v = a[j + k + i] * wn % MODULO;a[j + k] = (u + v) % MODULO;a[j + k + i] = (u - v + MODULO) % MODULO;wn = wn * w % MODULO;}}}return a;}long pow(long a, long n, long MODULO) {long ret = 1;for (; n > 0; n >>= 1, a = a * a % MODULO) {if (n % 2 == 1)ret = ret * a % MODULO;}return ret;}long inv(long a, long MODULO) {return pow(a, MODULO - 2, MODULO);}void tr(Object...o){System.out.println(Arrays.deepToString(o));}}