結果

問題 No.931 Multiplicative Convolution
ユーザー 37zigen
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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));
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0