Submit Info #27517

Problem Lang User Status Time Memory
Polynomial Interpolation java dalt AC 5422 ms 161.23 MiB

ケース詳細
Name Status Time Memory
example_00 AC 78 ms 10.11 MiB
example_01 AC 74 ms 10.29 MiB
max_random_00 AC 5366 ms 161.23 MiB
max_random_01 AC 5422 ms 160.85 MiB
random_00 AC 5181 ms 150.66 MiB
random_01 AC 4086 ms 133.21 MiB
random_02 AC 2762 ms 83.70 MiB

import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.Collection; import java.io.IOException; import java.util.Deque; import java.util.function.Supplier; import java.util.function.Consumer; import java.util.ArrayDeque; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top */ public class Main { public static void main(String[] args) throws Exception { Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29); thread.start(); thread.join(); } static class TaskAdapter implements Runnable { @Override public void run() { InputStream inputStream = System.in; OutputStream outputStream = System.out; FastInput in = new FastInput(inputStream); PrintWriter out = new PrintWriter(outputStream); PolynomialInterpolation solver = new PolynomialInterpolation(); solver.solve(1, in, out); out.close(); } } static class PolynomialInterpolation { public void solve(int testNumber, FastInput in, PrintWriter out) { int mod = 998244353; int n = in.readInt(); int[] x = new int[n]; int[] y = new int[n]; in.populate(x); in.populate(y); IntPoly poly = new IntPolyFFT(mod); int[] ans = poly.interpolate(x, y, n); assert poly.rankOf(ans) <= n - 1; for (int i = 0; i < n; i++) { out.print(ans[i]); out.append(' '); } } } static class SequenceUtils { public static void swap(int[] data, int i, int j) { int tmp = data[i]; data[i] = data[j]; data[j] = tmp; } public static void swap(double[] data, int i, int j) { double tmp = data[i]; data[i] = data[j]; data[j] = tmp; } public static void reverse(int[] data, int l, int r) { while (l < r) { swap(data, l, r); l++; r--; } } } static class ExtGCD { public static int extGCD(int a, int b, int[] xy) { if (a >= b) { return extGCD0(a, b, xy); } int ans = extGCD0(b, a, xy); SequenceUtils.swap(xy, 0, 1); return ans; } private static int extGCD0(int a, int b, int[] xy) { if (b == 0) { xy[0] = 1; xy[1] = 0; return a; } int ans = extGCD0(b, a % b, xy); int x = xy[0]; int y = xy[1]; xy[0] = y; xy[1] = x - a / b * y; return ans; } } static class DigitUtils { private DigitUtils() { } public static int mod(long x, int mod) { if (x < -mod || x >= mod) { x %= mod; } if (x < 0) { x += mod; } return (int) x; } public static int mod(int x, int mod) { if (x < -mod || x >= mod) { x %= mod; } if (x < 0) { x += mod; } return x; } public static int negate(int x, int mod) { return x == 0 ? 0 : mod - x; } public static int modsub(int a, int b, int mod) { int ans = a - b; if (ans < 0) { ans += mod; } return ans; } public static int modplus(int a, int b, int mod) { int ans = a + b; if (ans >= mod) { ans -= mod; } return ans; } public static int floorAverage(int x, int y) { return (x & y) + ((x ^ y) >> 1); } } static class PrimitiveBuffers { public static Buffer<int[]>[] intPow2Bufs = new Buffer[30]; public static Buffer<double[]>[] doublePow2Bufs = new Buffer[30]; static { for (int i = 0; i < 30; i++) { int finalI = i; intPow2Bufs[i] = new Buffer<>(() -> new int[1 << finalI], x -> Arrays.fill(x, 0)); doublePow2Bufs[i] = new Buffer<>(() -> new double[1 << finalI], x -> Arrays.fill(x, 0)); } } public static int[] allocIntPow2(int n) { return intPow2Bufs[Log2.ceilLog(n)].alloc(); } public static int[] resize(int[] data, int want) { int log = Log2.ceilLog(want); if (data.length == 1 << log) { return data; } return replace(allocIntPow2(data, want), data); } public static int[] allocIntPow2(int[] data, int newLen) { int[] ans = allocIntPow2(newLen); System.arraycopy(data, 0, ans, 0, Math.min(data.length, newLen)); return ans; } public static int[] allocIntPow2(int[] data, int prefix, int newLen) { int[] ans = allocIntPow2(newLen); System.arraycopy(data, 0, ans, 0, Math.min(data.length, prefix)); return ans; } public static void release(int[] data) { intPow2Bufs[Log2.ceilLog(data.length)].release(data); } public static double[] allocDoublePow2(int n) { return doublePow2Bufs[Log2.ceilLog(n)].alloc(); } public static double[] allocDoublePow2(double[] data, int newLen) { double[] ans = allocDoublePow2(newLen); System.arraycopy(data, 0, ans, 0, Math.min(data.length, newLen)); return ans; } public static void release(double[] data) { doublePow2Bufs[Log2.ceilLog(data.length)].release(data); } public static void release(double[]... data) { for (double[] x : data) { release(x); } } public static int[] replace(int[] a, int[] b) { release(b); return a; } public static int[] replace(int[] a, int[]... b) { for (int[] x : b) { release(x); } return a; } public static int[] replace(int[] a, int[] b0, int[] b1) { release(b0); replace(b1); return a; } } static class Polynomials { public static int rankOf(int[] p) { int r = p.length - 1; while (r >= 0 && p[r] == 0) { r--; } return Math.max(0, r); } public static int[] normalizeAndReplace(int[] p) { int r = rankOf(p); return PrimitiveBuffers.resize(p, r + 1); } } static class FastFourierTransform { private static double[][] realLevels = new double[30][]; private static double[][] imgLevels = new double[30][]; private static void prepareLevel(int i) { if (realLevels[i] == null) { realLevels[i] = new double[1 << i]; imgLevels[i] = new double[1 << i]; for (int j = 0, s = 1 << i; j < s; j++) { realLevels[i][j] = Math.cos(Math.PI / s * j); imgLevels[i][j] = Math.sin(Math.PI / s * j); } } } public static void fft(double[][] p, boolean inv) { int m = Log2.ceilLog(p[0].length); int n = 1 << m; int shift = 32 - Integer.numberOfTrailingZeros(n); for (int i = 1; i < n; i++) { int j = Integer.reverse(i << shift); if (i < j) { SequenceUtils.swap(p[0], i, j); SequenceUtils.swap(p[1], i, j); } } double[][] t = new double[2][1]; for (int d = 0; d < m; d++) { int s = 1 << d; int s2 = s << 1; prepareLevel(d); for (int i = 0; i < n; i += s2) { for (int j = 0; j < s; j++) { int a = i + j; int b = a + s; mul(realLevels[d][j], imgLevels[d][j], p[0][b], p[1][b], t, 0); sub(p[0][a], p[1][a], t[0][0], t[1][0], p, b); add(p[0][a], p[1][a], t[0][0], t[1][0], p, a); } } } if (inv) { for (int i = 0, j = 0; i <= j; i++, j = n - i) { double a = p[0][j]; double b = p[1][j]; div(p[0][i], p[1][i], n, p, j); if (i != j) { div(a, b, n, p, i); } } } } public static void add(double r1, double i1, double r2, double i2, double[][] r, int i) { r[0][i] = r1 + r2; r[1][i] = i1 + i2; } public static void sub(double r1, double i1, double r2, double i2, double[][] r, int i) { r[0][i] = r1 - r2; r[1][i] = i1 - i2; } public static void mul(double r1, double i1, double r2, double i2, double[][] r, int i) { r[0][i] = r1 * r2 - i1 * i2; r[1][i] = r1 * i2 + i1 * r2; } public static void div(double r1, double i1, double r2, double[][] r, int i) { r[0][i] = r1 / r2; r[1][i] = i1 / r2; } } static class FastInput { private final InputStream is; private byte[] buf = new byte[1 << 13]; private int bufLen; private int bufOffset; private int next; public FastInput(InputStream is) { this.is = is; } public void populate(int[] data) { for (int i = 0; i < data.length; i++) { data[i] = readInt(); } } private int read() { while (bufLen == bufOffset) { bufOffset = 0; try { bufLen = is.read(buf); } catch (IOException e) { bufLen = -1; } if (bufLen == -1) { return -1; } } return buf[bufOffset++]; } public void skipBlank() { while (next >= 0 && next <= 32) { next = read(); } } public int readInt() { int sign = 1; skipBlank(); if (next == '+' || next == '-') { sign = next == '+' ? 1 : -1; next = read(); } int val = 0; if (sign == 1) { while (next >= '0' && next <= '9') { val = val * 10 + next - '0'; next = read(); } } else { while (next >= '0' && next <= '9') { val = val * 10 - next + '0'; next = read(); } } return val; } } static class IntPoly { protected int mod; protected Power power; private static final int MULTI_APPLY_THRESHOLD = 128; public IntPoly(int mod) { this.mod = mod; this.power = new Power(mod); } public int[] convolution(int[] a, int[] b) { return mulBF(a, b); } public int[] divide(int[] a, int[] b) { int rankA = rankOf(a); int rankB = rankOf(b); int rankC = rankA - rankB; if (rankC < 0) { return PrimitiveBuffers.allocIntPow2(1); } //mod x^{rankC+1} int[] aa = PrimitiveBuffers.allocIntPow2(rankC + rankC + 1); int[] bb = PrimitiveBuffers.allocIntPow2(rankC + rankC + 1); for (int i = 0; i <= rankA && i < aa.length; i++) { aa[i] = a[rankA - i]; } for (int i = 0; i <= rankB && i < bb.length; i++) { bb[i] = b[rankB - i]; } int[] cc = PrimitiveBuffers.replace(inverse(bb, rankC + 1), bb); cc = PrimitiveBuffers.replace(PrimitiveBuffers.allocIntPow2(cc, rankC + rankC + 1), cc); int[] dm = PrimitiveBuffers.replace(convolution(aa, cc), aa, cc); for (int i = rankC + 1; i < dm.length; i++) { dm[i] = 0; } SequenceUtils.reverse(dm, 0, rankC); return Polynomials.normalizeAndReplace(dm); } public int[] module(int[] p, int n) { int rp = rankOf(p); int[] ans = PrimitiveBuffers.allocIntPow2(Math.min(rp + 1, n)); for (int i = 0; i < n && i <= rp; i++) { ans[i] = p[i]; } return ans; } public int[] differential(int[] p) { int rp = rankOf(p); int[] ans = PrimitiveBuffers.allocIntPow2(rp); for (int i = 1; i <= rp; i++) { ans[i - 1] = (int) ((long) p[i] * i % mod); } return ans; } public int rankOf(int[] p) { int r = p.length - 1; while (r >= 0 && p[r] == 0) { r--; } return Math.max(0, r); } public int[] mulBF(int[] a, int[] b) { int rA = rankOf(a); int rB = rankOf(b); if (rA > rB) { { int tmp = rA; rA = rB; rB = tmp; } { int[] tmp = a; a = b; b = tmp; } } int[] c = PrimitiveBuffers.allocIntPow2(rA + rB + 1); for (int i = 0; i <= rA; i++) { for (int j = 0; j <= rB; j++) { c[i + j] = (int) ((c[i + j] + (long) a[i] * b[j]) % mod); } } return c; } public int[] plus(int[] a, int[] b) { int rA = rankOf(a); int rB = rankOf(b); int[] ans = PrimitiveBuffers.allocIntPow2(Math.max(rA, rB) + 1); for (int i = 0; i <= rA; i++) { ans[i] = a[i]; } for (int i = 0; i <= rB; i++) { ans[i] = DigitUtils.modplus(ans[i], b[i], mod); } return ans; } public int[] subtract(int[] a, int[] b) { int rA = rankOf(a); int rB = rankOf(b); int[] ans = PrimitiveBuffers.allocIntPow2(Math.max(rA, rB) + 1); for (int i = 0; i <= rA; i++) { ans[i] = a[i]; } for (int i = 0; i <= rB; i++) { ans[i] = DigitUtils.modsub(ans[i], b[i], mod); } return ans; } public int[] modmul(int[] a, int[] b, int n) { int[] c = convolution(a, b); return PrimitiveBuffers.replace(module(c, n), c); } public int apply(int[] p, int x) { long y = 0; for (int i = p.length - 1; i >= 0; i--) { y = (y * x + p[i]) % mod; } return (int) y; } protected void multiApply(int[] p, int[] x, int[] y, int l, int r, IntPoly.PolynomialTree tree) { if (r - l + 1 <= MULTI_APPLY_THRESHOLD) { for (int i = l; i <= r; i++) { y[i] = apply(p, x[i]); } return; } int[][] qd = divideAndRemainder(p, tree.p); int[] remainder = qd[1]; PrimitiveBuffers.release(qd[0]); int m = DigitUtils.floorAverage(l, r); multiApply(remainder, x, y, l, m, tree.left); multiApply(remainder, x, y, m + 1, r, tree.right); PrimitiveBuffers.release(remainder); } protected IntPoly.PolynomialTree build(int[] x, int l, int r) { IntPoly.PolynomialTree tree = new IntPoly.PolynomialTree(); if (l == r) { tree.p = PrimitiveBuffers.allocIntPow2(2); tree.p[0] = DigitUtils.negate(x[l], mod); tree.p[1] = DigitUtils.mod(1, mod); } else { int m = DigitUtils.floorAverage(l, r); tree.left = build(x, l, m); tree.right = build(x, m + 1, r); tree.p = convolution(tree.left.p, tree.right.p); } return tree; } protected void releaseTree(IntPoly.PolynomialTree tree, int l, int r) { PrimitiveBuffers.release(tree.p); if (l == r) { return; } int m = DigitUtils.floorAverage(l, r); releaseTree(tree.left, l, m); releaseTree(tree.right, m + 1, r); } public int[][] divideAndRemainder(int[] a, int[] b) { int rA = rankOf(a); int rB = rankOf(b); int rC = rA - rB; if (rC < 0) { int[][] ans = new int[2][]; ans[0] = PrimitiveBuffers.allocIntPow2(1); ans[1] = PrimitiveBuffers.allocIntPow2(a, rA + 1); return ans; } int[] quotient = PrimitiveBuffers.allocIntPow2(rC + 1); int[] r = PrimitiveBuffers.allocIntPow2(a, rA + 1); long inv = power.inverse(b[rB]); for (int i = rA, j = rC; i >= rB; i--, j--) { if (r[i] == 0) { continue; } int factor = DigitUtils.mod(-r[i] * inv, mod); quotient[j] = DigitUtils.negate(factor, mod); for (int k = rB; k >= 0; k--) { r[k + j] = (int) ((r[k + j] + (long) factor * b[k]) % mod); } } return new int[][]{quotient, Polynomials.normalizeAndReplace(r)}; } public int[] inverse(int[] p, int m) { int[] ans = inverse0(p, Log2.ceilLog(m)); return PrimitiveBuffers.replace(module(ans, m), ans); } protected int[] inverse0(int[] p, int m) { if (m == 0) { int[] ans = PrimitiveBuffers.allocIntPow2(2); ans[0] = power.inverse(p[0]); return ans; } int[] C = inverse0(p, m - 1); int n = 1 << (m + 1); C = PrimitiveBuffers.resize(C, n); int[] A = PrimitiveBuffers.allocIntPow2(p, 1 << m, n); //B = C(2-AC) int[] AC = PrimitiveBuffers.replace(modmul(A, C, 1 << m), A); for (int i = 0; i < AC.length; i++) { AC[i] = DigitUtils.negate(AC[i], mod); } AC[0] = DigitUtils.modplus(AC[0], 2, mod); int[] B = PrimitiveBuffers.replace(modmul(C, AC, 1 << m), AC, C); return B; } public int[] interpolate(int[] x, int[] y, int n) { IntPoly.PolynomialTree tree = build(x, 0, n - 1); int[] diffM = differential(tree.p); int[] v = PrimitiveBuffers.allocIntPow2(n); multiApply(diffM, x, v, 0, n - 1, tree); for (int i = 0; i < n; i++) { v[i] = (int) ((long) y[i] * power.inverse(v[i]) % mod); } int[] ans = interpolate0(v, 0, n - 1, tree); releaseTree(tree, 0, n - 1); return ans; } private int[] interpolate0(int[] v, int l, int r, IntPoly.PolynomialTree tree) { if (l == r) { int[] ans = PrimitiveBuffers.allocIntPow2(1); ans[0] = v[l]; return ans; } int m = DigitUtils.floorAverage(l, r); int[] f0 = interpolate0(v, l, m, tree.left); int[] f1 = interpolate0(v, m + 1, r, tree.right); int[] a = PrimitiveBuffers.replace(convolution(f0, tree.right.p), f0); int[] b = PrimitiveBuffers.replace(convolution(f1, tree.left.p), f1); int[] sum = PrimitiveBuffers.replace(plus(a, b), a, b); return sum; } protected static class PolynomialTree { public int[] p; public IntPoly.PolynomialTree left; public IntPoly.PolynomialTree right; } } static class IntExtGCDObject { private int[] xy = new int[2]; public int extgcd(int a, int b) { return ExtGCD.extGCD(a, b, xy); } public int getX() { return xy[0]; } } static interface InverseNumber { } static class Log2 { public static int ceilLog(int x) { if (x <= 0) { return 0; } return 32 - Integer.numberOfLeadingZeros(x - 1); } } static class Modular { int m; public int getMod() { return m; } public Modular(int m) { this.m = m; } public Modular(long m) { this.m = (int) m; if (this.m != m) { throw new IllegalArgumentException(); } } public Modular(double m) { this.m = (int) m; if (this.m != m) { throw new IllegalArgumentException(); } } public String toString() { return "mod " + m; } } static class Buffer<T> { private Deque<T> deque; private Supplier<T> supplier; private Consumer<T> cleaner; private int allocTime; private int releaseTime; public Buffer(Supplier<T> supplier) { this(supplier, (x) -> { }); } public Buffer(Supplier<T> supplier, Consumer<T> cleaner) { this(supplier, cleaner, 0); } public Buffer(Supplier<T> supplier, Consumer<T> cleaner, int exp) { this.supplier = supplier; this.cleaner = cleaner; deque = new ArrayDeque<>(exp); } public T alloc() { allocTime++; return deque.isEmpty() ? supplier.get() : deque.removeFirst(); } public void release(T e) { releaseTime++; cleaner.accept(e); deque.addLast(e); } } static class IntPolyFFT extends IntPoly { private static final int FFT_THRESHOLD = 50; private static final int FFT_DIVIDE_THRESHOLD = 200; public IntPolyFFT(int mod) { super(mod); } public int[] convolution(int[] a, int[] b) { if (a != b) { return multiplyMod(a, b); } else { return pow2(a); } } public int[] pow2(int[] a) { int rA = rankOf(a); if (rA < FFT_THRESHOLD) { return mulBF(a, a); } int need = rA * 2 + 1; double[] aReal = PrimitiveBuffers.allocDoublePow2(need); double[] aImag = PrimitiveBuffers.allocDoublePow2(need); int n = aReal.length; for (int i = 0; i <= rA; i++) { int x = DigitUtils.mod(a[i], mod); aReal[i] = x & ((1 << 15) - 1); aImag[i] = x >> 15; } FastFourierTransform.fft(new double[][]{aReal, aImag}, false); double[] bReal = PrimitiveBuffers.allocDoublePow2(aReal, aReal.length); double[] bImag = PrimitiveBuffers.allocDoublePow2(aImag, bReal.length); for (int i = 0, j = 0; i <= j; i++, j = n - i) { double ari = aReal[i]; double aii = aImag[i]; double bri = bReal[i]; double bii = bImag[i]; double arj = aReal[j]; double aij = aImag[j]; double brj = bReal[j]; double bij = bImag[j]; double a1r = (ari + arj) / 2; double a1i = (aii - aij) / 2; double a2r = (aii + aij) / 2; double a2i = (arj - ari) / 2; double b1r = (bri + brj) / 2; double b1i = (bii - bij) / 2; double b2r = (bii + bij) / 2; double b2i = (brj - bri) / 2; aReal[i] = a1r * b1r - a1i * b1i - a2r * b2i - a2i * b2r; aImag[i] = a1r * b1i + a1i * b1r + a2r * b2r - a2i * b2i; bReal[i] = a1r * b2r - a1i * b2i + a2r * b1r - a2i * b1i; bImag[i] = a1r * b2i + a1i * b2r + a2r * b1i + a2i * b1r; if (i != j) { a1r = (arj + ari) / 2; a1i = (aij - aii) / 2; a2r = (aij + aii) / 2; a2i = (ari - arj) / 2; b1r = (brj + bri) / 2; b1i = (bij - bii) / 2; b2r = (bij + bii) / 2; b2i = (bri - brj) / 2; aReal[j] = a1r * b1r - a1i * b1i - a2r * b2i - a2i * b2r; aImag[j] = a1r * b1i + a1i * b1r + a2r * b2r - a2i * b2i; bReal[j] = a1r * b2r - a1i * b2i + a2r * b1r - a2i * b1i; bImag[j] = a1r * b2i + a1i * b2r + a2r * b1i + a2i * b1r; } } FastFourierTransform.fft(new double[][]{aReal, aImag}, true); FastFourierTransform.fft(new double[][]{bReal, bImag}, true); int[] ans = PrimitiveBuffers.allocIntPow2(need); for (int i = 0; i < need; i++) { long aa = DigitUtils.mod(Math.round(aReal[i]), mod); long bb = DigitUtils.mod(Math.round(bReal[i]), mod); long cc = DigitUtils.mod(Math.round(aImag[i]), mod); ans[i] = DigitUtils.mod(aa + (bb << 15) + (cc << 30), mod); } PrimitiveBuffers.release(aReal, bReal, aImag, bImag); return ans; } private int[] multiplyMod(int[] a, int[] b) { int rA = rankOf(a); int rB = rankOf(b); if (Math.min(rA, rB) < FFT_THRESHOLD) { return mulBF(a, b); } int need = rA + rB + 1; double[] aReal = PrimitiveBuffers.allocDoublePow2(need); double[] aImag = PrimitiveBuffers.allocDoublePow2(need); int n = aReal.length; for (int i = 0; i <= rA; i++) { int x = DigitUtils.mod(a[i], mod); aReal[i] = x & ((1 << 15) - 1); aImag[i] = x >> 15; } FastFourierTransform.fft(new double[][]{aReal, aImag}, false); double[] bReal = PrimitiveBuffers.allocDoublePow2(need); double[] bImag = PrimitiveBuffers.allocDoublePow2(need); for (int i = 0; i <= rB; i++) { int x = DigitUtils.mod(b[i], mod); bReal[i] = x & ((1 << 15) - 1); bImag[i] = x >> 15; } FastFourierTransform.fft(new double[][]{bReal, bImag}, false); for (int i = 0, j = 0; i <= j; i++, j = n - i) { double ari = aReal[i]; double aii = aImag[i]; double bri = bReal[i]; double bii = bImag[i]; double arj = aReal[j]; double aij = aImag[j]; double brj = bReal[j]; double bij = bImag[j]; double a1r = (ari + arj) / 2; double a1i = (aii - aij) / 2; double a2r = (aii + aij) / 2; double a2i = (arj - ari) / 2; double b1r = (bri + brj) / 2; double b1i = (bii - bij) / 2; double b2r = (bii + bij) / 2; double b2i = (brj - bri) / 2; aReal[i] = a1r * b1r - a1i * b1i - a2r * b2i - a2i * b2r; aImag[i] = a1r * b1i + a1i * b1r + a2r * b2r - a2i * b2i; bReal[i] = a1r * b2r - a1i * b2i + a2r * b1r - a2i * b1i; bImag[i] = a1r * b2i + a1i * b2r + a2r * b1i + a2i * b1r; if (i != j) { a1r = (arj + ari) / 2; a1i = (aij - aii) / 2; a2r = (aij + aii) / 2; a2i = (ari - arj) / 2; b1r = (brj + bri) / 2; b1i = (bij - bii) / 2; b2r = (bij + bii) / 2; b2i = (bri - brj) / 2; aReal[j] = a1r * b1r - a1i * b1i - a2r * b2i - a2i * b2r; aImag[j] = a1r * b1i + a1i * b1r + a2r * b2r - a2i * b2i; bReal[j] = a1r * b2r - a1i * b2i + a2r * b1r - a2i * b1i; bImag[j] = a1r * b2i + a1i * b2r + a2r * b1i + a2i * b1r; } } FastFourierTransform.fft(new double[][]{aReal, aImag}, true); FastFourierTransform.fft(new double[][]{bReal, bImag}, true); int[] ans = PrimitiveBuffers.allocIntPow2(need); for (int i = 0; i < need; i++) { long aa = DigitUtils.mod(Math.round(aReal[i]), mod); long bb = DigitUtils.mod(Math.round(bReal[i]), mod); long cc = DigitUtils.mod(Math.round(aImag[i]), mod); ans[i] = DigitUtils.mod(aa + (bb << 15) + (cc << 30), mod); } PrimitiveBuffers.release(aReal, bReal, aImag, bImag); return ans; } public int[][] divideAndRemainder(int[] a, int[] b) { int rankA = rankOf(a); int rankB = rankOf(b); int rankC = rankA - rankB; if (rankC < 0) { int[][] ans = new int[2][]; ans[0] = PrimitiveBuffers.allocIntPow2(1); ans[1] = PrimitiveBuffers.allocIntPow2(a, rankA + 1); return ans; } if (rankB < FFT_DIVIDE_THRESHOLD || rankC < FFT_DIVIDE_THRESHOLD) { return super.divideAndRemainder(a, b); } int[] quotient = divide(a, b); int[] prod = convolution(b, quotient); int[] remainder = PrimitiveBuffers.replace(subtract(a, prod), prod); remainder = PrimitiveBuffers.replace(module(remainder, rankB), remainder); remainder = Polynomials.normalizeAndReplace(remainder); return new int[][]{quotient, remainder}; } } static class Power implements InverseNumber { static IntExtGCDObject extGCD = new IntExtGCDObject(); int mod; public Power(Modular modular) { this.mod = modular.getMod(); } public Power(int mod) { this(new Modular(mod)); } public int inverse(int x) { int ans = inverseExtGCD(x); // if(modular.mul(ans, x) != 1){ // throw new IllegalStateException(); // } return ans; } public int inverseExtGCD(int x) { if (extGCD.extgcd(x, mod) != 1) { throw new IllegalArgumentException(); } return DigitUtils.mod(extGCD.getX(), mod); } } }