結果
| 問題 | No.3619 Compositional Power with Schröder Coordinate |
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2026-08-10 21:39:59 |
| 言語 | Java (openjdk 25.0.2) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 65,530 bytes |
| 記録 | |
| コンパイル時間 | 3,326 ms |
| コンパイル使用メモリ | 107,216 KB |
| 実行使用メモリ | 451,056 KB |
| 最終ジャッジ日時 | 2026-08-10 21:40:33 |
| 合計ジャッジ時間 | 15,884 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 1 TLE * 1 -- * 4 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Queue;
import java.util.Random; public class Main { static MyPrintWriter pw = MyPrintWriter.getInstance(); static FastScanner sc = FastScanner.getInstance(); public static void main(String[] args) throws IOException { Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1)); new Main().run(); pw.flush(); } void run() { int N = sc.nextInt(); int M = sc.nextInt(); long[] A = sc.nextLongs(N); long[] B = sc.nextLongs(N); long[] C = sc.nextLongs(N); Fp fp = Fp.MOD998244353; var mod = fp.modulus(); long A1POW = fp.pow(A[1], M); var P = PolynomialFpDynamic.MOD998244353; for (int i = 0; i < B.length; i++) { B[i] = (B[i] * A1POW) % mod; } var W = P.comp(C, B, N); pw.println(W); } } class ArrayUtils { public static void swap(int i, int j, long[] A) { if (i == j) { return; } long tmp = A[i]; A[i] = A[j]; A[j] = tmp; } public static void swap(long[] A, long[] B) { if (A.length != B.length) { throw new AssertionError(); } for (int i = 0; i < A.length; i++) { long tmp = A[i]; A[i] = B[i]; B[i] = tmp; } } public static void reverse(long[] a) { int s = 0; int t = a.length - 1; while (s < t) { swap(s, t, a); ++s; --t; } } public static long[][] copy(long[][] a) { long[][] b = new long[a.length][]; Arrays.setAll(b, i -> Arrays.copyOf(a[i], a[i].length)); return b; } } interface CommutativeRingElement<X extends CommutativeRingElement<X>> extends RingElement<X> {} interface CommutativeRingStrategy<T> extends RingStrategy<T> {} interface EuclideanDomainElement<X extends EuclideanDomainElement<X>> extends UFDElement<X> { X div(X a); X mod(X a); long norm(); } interface EuclideanDomainStrategy<T> extends GCDDomainStrategy<T> { T div(T a, T b); T mod(T a, T b); long norm(T a); default T canonicalUnit(T a) { return one(); } @Override default T gcd(T a, T b) { while (!equals(b, zero())) { a = mod(a, b); T t = a; a = b; b = t; } if (equals(a, zero())) { return a; } return div(a, canonicalUnit(a)); } record ExtGCDResult<T>(T x, T y, T gcd) {} default ExtGCDResult<T> extgcd(T a, T b) { T x0 = one(); T y0 = zero(); T g0 = a; T x1 = zero(); T y1 = one(); T g1 = b; while (!equals(g1, zero())) { T q = div(g0, g1); T nextG = sub(g0, mul(q, g1)); T nextX = sub(x0, mul(q, x1)); T nextY = sub(y0, mul(q, y1)); x0 = x1; y0 = y1; g0 = g1; x1 = nextX; y1 = nextY; g1 = nextG; } if (equals(g0, zero())) { return new ExtGCDResult<>(x0, y0, g0); } T u = canonicalUnit(g0); return new ExtGCDResult<>(div(x0, u), div(y0, u), div(g0, u)); } } interface ExactDivRingStrategy<T> extends IntegralDomainStrategy<T> { T exactDiv(T a, T b); } class FastScanner { private static FastScanner instance = null; private final InputStream in = System.in; private final byte[] buffer = new byte[1 << 16]; private int ptr = 0; private int buflen = 0; private FastScanner() { } public static FastScanner getInstance() { if (instance == null) { instance = new FastScanner(); } return instance; } private boolean hasNextByte() { if (ptr < buflen) { return true; } ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } return buflen > 0; } private int readByte() { if (hasNextByte()) { return buffer[ptr++]; } else { return -1; } } private boolean isPrintableChar(int c) { return (33 <= c) && (c <= 126); } public boolean hasNext() { while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) { ptr++; } return hasNextByte(); } public long nextLong() { if (!hasNext()) { throw new NoSuchElementException(); } long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } while ((b >= '0') && (b <= '9')) { n = ((n << 1) + (n << 3)) + (b - '0'); b = readByte(); } return minus ? -n : n; } public int nextInt() { return ((int) (nextLong())); } public long[] nextLongs(int n) { long[] a = new long[n]; for (int i = 0; i < n; ++i) { a[i] = nextLong(); } return a; } } interface FieldElement<X extends FieldElement<X>> extends EuclideanDomainElement<X> { X inv(); @Override default X pow(long n) { if (n < 0) { return inv().pow(-n); } return EuclideanDomainElement.super.pow(n); } } interface FieldStrategy<T> extends EuclideanDomainStrategy<T> , ExactDivRingStrategy<T> { @Override default T exactDiv(T a, T b) { return div(a, b); } T inv(T a); default T div(T a, T b) { return mul(a, inv(b)); } default T mod(T a, T b) { return zero(); } @Override default T pow(T a, long n) { if (n < 0) { return pow(inv(a), -n); } return EuclideanDomainStrategy.super.pow(a, n); } default T geometricSum(T a) { return inv(sub(one(), a)); } default EuclideanDomainStrategy.ExtGCDResult<T> extgcd(T a, T b) { if (!equals(a, zero())) { return new EuclideanDomainStrategy.ExtGCDResult<>(inv(a), zero(), one()); } else if (!equals(b, zero())) { return new EuclideanDomainStrategy.ExtGCDResult<>(zero(), inv(b), one()); } else { return new EuclideanDomainStrategy.ExtGCDResult<>(zero(), zero(), zero()); } } } class Fp extends Zn implements LongFieldStrategy { public static final Fp MOD998244353 = new Fp(998244353); public Fp(long mod) { super(mod); } int[] inv = new int[0]; public long inv(long n) { if (n < 0) { n = reduce(n); } return n < inv.length ? inv[((int) (n))] & 0xffffffffL : MathUtils.modInv(n, mod); } @Override public long div(long a, long b) { return mul(a, inv(b)); } @Override public long mod(long a, long b) { if (equals(b, zero())) { throw new ArithmeticException("Division by zero"); } return zero(); } @Override public long norm(long a) { return equals(a, zero()) ? 0 : 1; } @Override public long canonicalUnit(long a) { if (equals(a, zero())) { return one(); } return a; } public long pow(long a, long n) { if (n < 0) { a = inv(a); n = -n; } return MathUtils.modPow(a, n, mod); } } class FractionFieldElement<T> implements FieldElement<FractionFieldElement<T>> { public final T num; public final T den; private final FractionFieldStrategy<T> strategy; private final RingStrategy<FractionFieldElement<T>> parent = new RingStrategy<>() { @Override public FractionFieldElement<T> zero() { return FractionFieldElement.this.zero(); } @Override public FractionFieldElement<T> one() { return FractionFieldElement.this.one(); } @Override public FractionFieldElement<T> add(FractionFieldElement<T> a, FractionFieldElement<T> b) { return a.add(b); } @Override public FractionFieldElement<T> mul(FractionFieldElement<T> a, FractionFieldElement<T> b) { return a.mul(b); } @Override public FractionFieldElement<T> neg(FractionFieldElement<T> a) { return a.neg(); } @Override public boolean equals(FractionFieldElement<T> a, FractionFieldElement<T> b) { return a.equals(b); } }; @Override public RingStrategy<FractionFieldElement<T>> parent() { return parent; } @Override public FractionFieldElement<T> self() { return this; } public FractionFieldElement(T num, T den, FractionFieldStrategy<T> strategy) { this.num = num; this.den = den; this.strategy = strategy; } public T num() { return num; } public T den() { return den; } @Override public FractionFieldElement<T> add(FractionFieldElement<T> a) { return strategy.add(this, a); } @Override public FractionFieldElement<T> mul(FractionFieldElement<T> a) { return strategy.mul(this, a); } public FractionFieldElement<T> neg() { return strategy.neg(this); } public FractionFieldElement<T> inv() { return strategy.inv(this); } @Override public FractionFieldElement<T> gcd(FractionFieldElement<T> a) { return strategy.gcd(this, a); } @Override public FractionFieldElement<T> div(FractionFieldElement<T> a) { return strategy.div(this, a); } @Override public FractionFieldElement<T> mod(FractionFieldElement<T> a) { return strategy.mod(this, a); } @Override public long norm() { return strategy.norm(this); } @Override public FractionFieldElement<T> one() { return strategy.one(); } @Override public FractionFieldElement<T> zero() { return strategy.zero(); } @Override public String toString() { String ns = (num instanceof long[] a) ? Arrays.toString(a) : String.valueOf(num); String ds = (den instanceof long[] a) ? Arrays.toString(a) : String.valueOf(den); return (ns + "/") + ds; } @Override public boolean equals(Object o) { if (this == o) { return true; } if (!(o instanceof FractionFieldElement<?> that)) { return false; } return Objects.deepEquals(num, that.num) && Objects.deepEquals(den, that.den); } @Override public int hashCode() { return Objects.hash(Objects.hashCode(num), Objects.hashCode(den)); } } class FractionFieldStrategy<T> implements FieldStrategy<FractionFieldElement<T>> { private final IntegralDomainStrategy<T> strategy; public FractionFieldStrategy(IntegralDomainStrategy<T> strategy) { this.strategy = strategy; } public FractionFieldElement<T> of(T num, T den) { if (strategy.equals(den, strategy.zero())) { throw new ArithmeticException("Division by zero"); } return simplify(new FractionFieldElement<>(num, den, this)); } public FractionFieldElement<T> zero() { return new FractionFieldElement<>(strategy.zero(), strategy.one(), this); } @Override public FractionFieldElement<T> one() { return new FractionFieldElement<>(strategy.one(), strategy.one(), this); } @Override public FractionFieldElement<T> add(FractionFieldElement<T> a, FractionFieldElement<T> b) { T num = strategy.add(strategy.mul(a.num(), b.den()), strategy.mul(b.num(), a.den())); T den = strategy.mul(a.den(), b.den()); return simplify(new FractionFieldElement<>(num, den, this)); } @Override public FractionFieldElement<T> mul(FractionFieldElement<T> a, FractionFieldElement<T> b) { T num = strategy.mul(a.num(), b.num()); T den = strategy.mul(a.den(), b.den()); return simplify(new FractionFieldElement<>(num, den, this)); } @Override public FractionFieldElement<T> neg(FractionFieldElement<T> a) { return new FractionFieldElement<>(strategy.neg(a.num()), a.den(), this); } @Override public FractionFieldElement<T> inv(FractionFieldElement<T> a) { if (strategy.equals(a.num(), strategy.zero())) { throw new ArithmeticException("Division by zero"); } return simplify(new FractionFieldElement<>(a.den(), a.num(), this)); } @Override public boolean equals(FractionFieldElement<T> a, FractionFieldElement<T> b) { return strategy.equals(strategy.mul(a.num(), b.den()), strategy.mul(b.num(), a.den())); } @Override public FractionFieldElement<T> mod(FractionFieldElement<T> a, FractionFieldElement<T> b) { if (equals(b, zero())) { throw new ArithmeticException("Division by zero"); } return zero(); } @Override public long norm(FractionFieldElement<T> a) { return equals(a, zero()) ? 0 : 1; } @Override public FractionFieldElement<T> canonicalUnit(FractionFieldElement<T> a) { return equals(a, zero()) ? one() : a; } @Override public boolean equals(Object o) { if (this == o) { return true; } if ((o == null) || (getClass() != o.getClass())) { return false; } FractionFieldStrategy<?> that = ((FractionFieldStrategy<?>) (o)); return Objects.equals(strategy, that.strategy); } @Override public int hashCode() { return Objects.hash(strategy); } private FractionFieldElement<T> simplify(FractionFieldElement<T> f) { if (strategy instanceof GCDDomainStrategy<T> gs) { T g = gs.gcd(f.num(), f.den()); T num = f.num(); T den = f.den(); if ((!strategy.equals(g, strategy.zero())) && (!strategy.equals(g, strategy.one()))) { if (strategy instanceof ExactDivRingStrategy<T> eds) { num = eds.exactDiv(num, g); den = eds.exactDiv(den, g); } else if (strategy instanceof EuclideanDomainStrategy<T> ed) { num = ed.div(num, g); den = ed.div(den, g); } } if (strategy instanceof EuclideanDomainStrategy<T> ed) { T u = ed.canonicalUnit(den); if (!strategy.equals(u, strategy.one())) { num = ed.div(num, u); den = ed.div(den, u); } } return new FractionFieldElement<>(num, den, this); } return f; } } interface GCDDomainElement<X extends GCDDomainElement<X>> extends IntegralDomainElement<X> { X gcd(X a); } interface GCDDomainStrategy<T> extends IntegralDomainStrategy<T> { T gcd(T a, T b); } interface IntegralDomainElement<X extends IntegralDomainElement<X>> extends CommutativeRingElement<X> {} interface IntegralDomainStrategy<T> extends CommutativeRingStrategy<T> {} interface LongCommutativeRingStrategy extends LongRingStrategy {} interface LongEuclideanDomainStrategy extends LongGCDDomainStrategy { long div(long a, long b); long mod(long a, long b); long norm(long a); default long canonicalUnit(long a) { return one(); } @Override default long gcd(long a, long b) { while (!equals(b, zero())) { a = mod(a, b); long t = a; a = b; b = t; } if (equals(a, zero())) { return a; } return div(a, canonicalUnit(a)); } record ExtGCDResult(long x, long y, long gcd) {} default ExtGCDResult extgcd(long a, long b) { long x0 = one(); long y0 = zero(); long g0 = a; long x1 = zero(); long y1 = one(); long g1 = b; while (!equals(g1, zero())) { long q = div(g0, g1); long nextG = sub(g0, mul(q, g1)); long nextX = sub(x0, mul(q, x1)); long nextY = sub(y0, mul(q, y1)); x0 = x1; y0 = y1; g0 = g1; x1 = nextX; y1 = nextY; g1 = nextG; } if (equals(g0, zero())) { return new ExtGCDResult(x0, y0, g0); } long u = canonicalUnit(g0); return new ExtGCDResult(div(x0, u), div(y0, u), div(g0, u)); } } interface LongExactDivRingStrategy extends LongIntegralDomainStrategy { long divExact(long a, long b); } interface LongFieldStrategy extends LongEuclideanDomainStrategy , LongExactDivRingStrategy { @Override default long divExact(long a, long b) { return div(a, b); } long inv(long a); default long div(long a, long b) { return mul(a, inv(b)); } default long geometricSum(long a) { return inv(sub(one(), a)); } @Override default ExtGCDResult extgcd(long a, long b) { if (!equals(a, zero())) { return new ExtGCDResult(inv(a), zero(), one()); } else if (!equals(b, zero())) { return new ExtGCDResult(zero(), inv(b), one()); } else { return new ExtGCDResult(zero(), zero(), zero());}}}interface LongGCDDomainStrategy extends LongIntegralDomainStrategy { long gcd(long a, long b); } interface LongIntegralDomainStrategy extends LongCommutativeRingStrategy {} interface LongRingStrategy extends LongSemiRingStrategy { long neg(long a); default long sub(long a, long b) { return add(a,neg(b)); } } interface LongSemiRingStrategy { long zero(); long one();long add(long a,long b);long mul(long a,long b);boolean equals(long a,long b);}class MathUtils{public static long modPow(long a, long n, long mod) { if (n < 0) { long inv = MathUtils.modInv(a, mod); return MathUtils.modPow(inv, -n, mod); } if (n == 0) { return 1; } return (MathUtils.modPow((a * a) % mod, n / 2, mod) * ((n % 2) == 1 ? a : 1)) % mod; } public static long modInv(long a, long mod) { a = ((a % mod) + mod) % mod; long[] f0 = new long[]{ 1, 0, mod }; long[] f1 = new long[]{ 0, 1, a }; while (f1[2] != 0) { long q = f0[2] / f1[2]; for (int i = 0; i < 3; i++) { f0[i] -= q * f1[i]; } ArrayUtils.swap(f0, f1); } return f0[1] < 0 ? mod + f0[1] : f0[1]; } } class MyPrintWriter extends PrintWriter { private static MyPrintWriter instance = null; private MyPrintWriter() { super(System.out); } public static MyPrintWriter getInstance() { if (instance == null) { instance = new MyPrintWriter(); } return instance; } public void println(long[] a) { println(a, " "); } public void println(long[] a, String separator) { for (int i = 0; i < a.length; ++i) { super.print(a[i] + (i == (a.length - 1) ? "" : separator)); } super.println(); } } class PolynomialEuclideanStrategy<T> extends PolynomialRingStrategy<T> implements EuclideanDomainStrategy<T[]> { private final FieldStrategy<T> field; public PolynomialEuclideanStrategy(FieldStrategy<T> field) { super(field); this.field = field; } @Override public T[] div(T[] a, T[] b) { return divmod(a, b)[0]; } @Override public T[] mod(T[] a, T[] b) { return divmod(a, b)[1]; } @Override public long norm(T[] a) { return trim(a).length; } @Override public T[] canonicalUnit(T[] a) { T[] ta = trim(a); if (ta.length == 0) { return one(); } T[] res = createArray(1); res[0] = ta[ta.length - 1]; return res; } private T[][] divmod(T[] a, T[] b) { T[] ta = trim(a); T[] tb = trim(b); if (tb.length == 0) { throw new ArithmeticException("Division by zero"); } if (ta.length < tb.length) { T[][] res = ((T[][]) (Array.newInstance(clazz, 2, 0))); res[0] = zero(); res[1] = ta; return res; } T[] q = createArray((ta.length - tb.length) + 1); T[] r = ta.clone(); T invLeading = field.inv(tb[tb.length - 1]); for (int i = ta.length - 1; i >= (tb.length - 1); i--) { q[(i - tb.length) + 1] = field.mul(r[i], invLeading); T factor = q[(i - tb.length) + 1]; for (int j = 0; j < tb.length; j++) { r[((i - tb.length) + 1) + j] = field.sub(r[((i - tb.length) + 1) + j], field.mul(factor, tb[j])); } } T[][] res = ((T[][]) (Array.newInstance(clazz, 2, 0))); res[0] = trim(q); res[1] = trim(r); return res; } } class PolynomialFpDynamic extends PolynomialZnDynamic implements EuclideanDomainStrategy<long[]> , UFDStrategy<long[]> , ExactDivRingStrategy<long[]> { Fp fp; public final boolean isNTTFriendly; public final long primitiveRoot; public final int maxPow2; long[][] bitreversedRoots; long[][] bitreversedInvRoots; public static final int FFT_NAIVE_THRESHOLD = 128; public static final int FFT_MIN_LENGTH_THRESHOLD = 10; public static final PolynomialFpDynamic MOD998244353 = new PolynomialFpDynamic(998244353L, 3); public static final PolynomialFpDynamic MOD469762049 = new PolynomialFpDynamic(469762049L, 3); public static final PolynomialFpDynamic MOD167772161 = new PolynomialFpDynamic(167772161L, 3); public static final PolynomialFpDynamic MOD754974721 = new PolynomialFpDynamic(754974721L, 11); public static final PolynomialFpDynamic MOD1004535809 = new PolynomialFpDynamic(1004535809L, 3); public PolynomialFpDynamic(long mod, long primitiveRoot) { super(mod); fp = new Fp(mod); this.isNTTFriendly = true; this.primitiveRoot = primitiveRoot; this.maxPow2 = Long.numberOfTrailingZeros(mod - 1); this.bitreversedRoots = new long[maxPow2 + 1][]; this.bitreversedInvRoots = new long[maxPow2 + 1][]; } void prepareRoots(int n) { if (Integer.bitCount(n) != 1) { throw new AssertionError(); } int sz = Integer.numberOfTrailingZeros(n); if (sz > maxPow2) { throw new AssertionError("NTT length exceeds mod - 1 power of two"); } if (bitreversedRoots[sz] != null) { return; } long root = MathUtils.modPow(primitiveRoot, (mod - 1) / n, mod); long iroot = MathUtils.modInv(root, mod); bitreversedRoots[sz] = new long[n]; bitreversedInvRoots[sz] = new long[n]; for (int n_ = n / 2; n_ >= 1; n_ /= 2 , root = (root * root) % mod , iroot = (iroot * iroot) % mod) { long w = 1; long iw = 1; for (int j = 0; j < n_; ++j) { bitreversedRoots[sz][n_ + j] = w; bitreversedInvRoots[sz][n_ + j] = iw; w = (w * root) % mod; iw = (iw * iroot) % mod; } int cur = 0; for (int j = 0; j < n_; ++j) { if (cur < j) { ArrayUtils.swap(n_ + cur, n_ + j, bitreversedRoots[sz]); ArrayUtils.swap(n_ + cur, n_ + j, bitreversedInvRoots[sz]); } for (int k = n_ / 2; k > (cur ^= k); k /= 2); } } } public void fftToBitReversed(long[] a) { int n = a.length; int sz = Integer.numberOfTrailingZeros(n); prepareRoots(n); for (int m = 1, t = n / 2; m <= (n / 2); m *= 2 , t /= 2) { for (int i = 0, k = 0; i < m; ++i , k += 2 * t) { long s = bitreversedRoots[sz][m + i]; for (int j = k; j < (k + t); ++j) { long u = a[j]; long v = (a[j + t] * s) % mod; a[j] = addMod(u, v); a[j + t] = subMod(u, v); } } } } public void ifftFromBitReversed(long[] a) { long invN = MathUtils.modInv(a.length, mod); int n = a.length; int sz = Integer.numberOfTrailingZeros(n); prepareRoots(n); for (int m = n / 2, t = 1; m >= 1; m /= 2 , t *= 2) { for (int i = 0, k = 0; i < m; ++i , k += 2 * t) { long s = bitreversedInvRoots[sz][m + i]; if (m == 1) { s = (s * invN) % mod; } for (int j = k; j < (k + t); ++j) { long u = a[j]; long v = a[j + t]; if (m == 1) { a[j] = ((u + v) * invN) % mod; } else { a[j] = addMod(u, v); } a[j + t] = (((u + mod) - v) * s) % mod; } } } } public long[] mulFFT(long[] a, long[] b) { if ((a.length == 0) || (b.length == 0)) { return new long[0]; } int n = 1; int len = (a.length + b.length) - 1; while (n < len) { n *= 2; } if (Integer.numberOfTrailingZeros(n) > maxPow2) { throw new AssertionError("NTT length exceeds mod - 1 power of two"); } long[] fa = new long[n]; long[] fb = new long[n]; for (int i = 0; i < a.length; i++) { fa[i] = fp.reduce(a[i]); } for (int i = 0; i < b.length; i++) { fb[i] = fp.reduce(b[i]); } prepareRoots(n); fftToBitReversed(fa); fftToBitReversed(fb); for (int i = 0; i < n; ++i) { fa[i] = (fa[i] * fb[i]) % mod; } ifftFromBitReversed(fa); return Arrays.copyOf(fa, len); } @Override public long[] mul(long[] a, long[] b) { if ((a.length == 0) || (b.length == 0)) { return new long[0]; } if ((a.length == 1) && (b.length == 1)) { return new long[]{ (a[0] * b[0]) % mod }; } int n = a.length; int m = b.length; if ((isNTTFriendly && (((n + m) - 1) > FFT_NAIVE_THRESHOLD)) && (Math.min(n, m) > FFT_MIN_LENGTH_THRESHOLD)) { return mulFFT(a, b); } return super.mul(a, b); } @Override public long[] squared(long[] a) { if (a.length == 0) { return new long[0]; } if (a.length == 1) { return new long[]{ (a[0] * a[0]) % mod }; } int len = (2 * a.length) - 1; if (isNTTFriendly && (len > FFT_NAIVE_THRESHOLD)) { return squaredFFT(a); } return super.squared(a); } private long[] squaredFFT(long[] a) { if (a.length == 0) { return new long[0]; } int n = 1; int len = (2 * a.length) - 1; while (n < len) { n *= 2; } if (Integer.numberOfTrailingZeros(n) > maxPow2) { throw new AssertionError("NTT length exceeds mod - 1 power of two"); } long[] fa = new long[n]; for (int i = 0; i < a.length; i++) { fa[i] = fp.reduce(a[i]); } prepareRoots(n); fftToBitReversed(fa); for (int i = 0; i < n; ++i) { fa[i] = (fa[i] * fa[i]) % mod; } ifftFromBitReversed(fa); return Arrays.copyOf(fa, len); } @Override public long[] powFull(long[] a, int n) { if (n == 0) { return new long[]{ 1 }; } if (n == 1) { return a.clone(); } int d = deg(a); if (d == (-1)) { return new long[0]; } if (d == 0) { return new long[]{ MathUtils.modPow(a[0], n, mod) }; } if (d <= 40) { return sparsePow(a, (d * n) + 1, n); } long[] ret = new long[1]; ret[0] = 1; long[] b = a.clone(); while (n != 0) { if ((n % 2) == 1) { ret = mul(ret, b); } n /= 2; if (n == 0) { break; } b = mul(b, b); } return ret; } @Override public boolean equals(Object o) { if (this == o) { return true; } if ((o == null) || (getClass() != o.getClass())) { return false; } PolynomialFpDynamic that = ((PolynomialFpDynamic) (o)); return mod == that.mod; } @Override public int hashCode() { return Objects.hash(mod); } public long[] monic(long[] a) { int deg = deg(a); if (deg == (-1)) { return new long[0]; } if (deg == 0) { return new long[]{ 1 }; } long inv = fp.inv(a[deg]); long[] res = new long[deg + 1]; for (int i = 0; i < deg; i++) { res[i] = (a[i] * inv) % mod; } res[deg] = 1; return res; } public long[] divNaive(long[] a, long[] b) { int degA = deg(a); int degB = deg(b); if (degB == (-1)) { throw new ArithmeticException("division by zero polynomial"); } if (degA < degB) { return new long[]{ 0 }; } long[] r = Arrays.copyOf(a, degA + 1); long[] q = new long[(degA - degB) + 1]; long invB = fp.inv(b[degB]); for (int i = degA; i >= degB; i--) { if (r[i] == 0) { continue; } long c = (r[i] * invB) % mod; q[i - degB] = c; for (int j = 0; j <= degB; j++) { r[(i - degB) + j] -= (c * b[j]) % mod; if (r[(i - degB) + j] < 0) { r[(i - degB) + j] += mod; } } } return resize(q); } public long[] modNaive(long[] a, long[] b) { int degA = deg(a); int degB = deg(b); if (degB == (-1)) { throw new ArithmeticException("division by zero polynomial"); } if (degA < degB) { return resize(a); } long[] r = Arrays.copyOf(a, degA + 1); long invB = fp.inv(b[degB]); for (int i = degA; i >= degB; i--) { if (r[i] == 0) { continue; } long c = (r[i] * invB) % mod; for (int j = 0; j <= degB; j++) { r[(i - degB) + j] -= (c * b[j]) % mod; if (r[(i - degB) + j] < 0) { r[(i - degB) + j] += mod; } } } return resize(r); } public static class DivModResult { public long[] q; public long[] r; public DivModResult(long[] q, long[] r) { this.q = q; this.r = r; } } public DivModResult divmod(long[] a, long[] b) { var q = div(a, b); var r = sub(a, mul(q, b)); r = resize(r); return new DivModResult(q, r); } public long[] gcdNaive(long[] a, long[] b) { a = resize(a); b = resize(b); while (deg(b) != (-1)) { long[] r = modNaive(a, b); a = b; b = r; } return monic(a); } public long[] differentiate(long[] a) { long[] ret = new long[a.length]; for (int i = 1; i < a.length; ++i) { ret[i - 1] = (i * a[i]) % mod; } return ret; } public long[] integrate(long[] a) { long[] ret = new long[a.length]; for (int i = 0; (i + 1) < a.length; ++i) { ret[i + 1] = (MathUtils.modInv(i + 1, mod) * a[i]) % mod; } return ret; } public long[] invNaive(long[] a) { long[] g = new long[a.length]; long inv0 = MathUtils.modInv(a[0], mod); g[0] = inv0; for (int i = 1; i < a.length; i++) { long sum = 0; for (int j = 1; j <= i; j++) { if (j < a.length) { sum = (sum + (a[j] * g[i - j])) % mod; } } g[i] = (sum == 0) ? 0 : (((mod - sum) % mod) * inv0) % mod; } return g; } public long[] invFFT(long[] a) { long[] g = new long[]{ MathUtils.modInv(a[0], mod) }; for (int len = 1; len < a.length; len *= 2) { long[] fftG = Arrays.copyOf(g, len * 4); long[] fftA = new long[4 * len]; System.arraycopy(a, 0, fftA, 0, Math.min(2 * len, a.length)); prepareRoots(4 * len); fftToBitReversed(fftG); fftToBitReversed(fftA); for (int i = 0; i < fftG.length; ++i) { fftG[i] = (((fftG[i] * fftG[i]) % mod) * fftA[i]) % mod; } ifftFromBitReversed(fftG); for (int i = 0; i < len; ++i) { fftG[i] = g[i]; } for (int i = len; i < (2 * len); ++i) { if (fftG[i] != 0) { fftG[i] = mod - fftG[i]; } } g = Arrays.copyOf(fftG, Math.min(a.length, 2 * len)); } return g; } public long[] inv(long[] a) { if (a[0] == 0) { throw new AssertionError(); } return isNTTFriendly ? invFFT(a) : invNaive(a); } public long[] log(long[] a) { return integrate(Arrays.copyOf(mul(differentiate(a), inv(a)), a.length)); } public long[] expNaive(long[] a) { if (a[0] != 0) { throw new AssertionError(); } int n = a.length; long[] g = new long[n]; long[] df = new long[n]; for (int i = 0; i < n; i++) { df[i] = (i * a[i]) % mod; } g[0] = 1; for (int i = 1; i < n; i++) { long sum = 0; for (int j = 1; j <= i; j++) { sum = (sum + (df[j] * g[i - j])) % mod; } g[i] = (sum * fp.inv(i)) % mod; } return g; } public long[] expFFT(long[] a) { if (a[0] != 0) { throw new AssertionError(); } long[] g = new long[]{ 1 }; for (int len = 1; len < a.length; len *= 2) { long[] tmp = sub(Arrays.copyOf(a, Math.min(2 * len, a.length)), log(Arrays.copyOf(g, Math.min(2 * len, a.length)))); tmp[0] = addMod(tmp[0], 1); g = Arrays.copyOf(mul(g, tmp), Math.min(2 * len, a.length)); } return Arrays.copyOf(g, a.length); } public long[] exp(long[] a) { return isNTTFriendly ? expFFT(a) : expNaive(a); } public long[] mul(long[] a, long b) { long[] ret = new long[a.length]; for (int i = 0; i < a.length; i++) { ret[i] = (a[i] * b) % mod; } return ret; } public long[] pow(long[] a, long m) { int len = a.length; if (m == 0) { long[] ret = new long[len]; ret[0] = 1; return ret; } if (m == 1) { return a.clone(); } if (m == 2) { return squared(a); } int s = 0; while ((s < a.length) && (a[s] == 0)) { ++s; } if (s == a.length) { return a.clone(); } long[] aa = (s != 0) ? Arrays.copyOfRange(a, s, a.length) : a.clone(); long b = MathUtils.modInv(aa[0], mod); for (int i = 0; i < aa.length; i++) { aa[i] = (b * aa[i]) % mod; } aa = log(aa); for (int i = 0; i < aa.length; i++) { aa[i] = ((m % mod) * aa[i]) % mod; } aa = exp(aa); b = MathUtils.modPow(MathUtils.modInv(b, mod), m % (mod - 1), mod); for (int i = 0; i < aa.length; i++) { aa[i] = (b * aa[i]) % mod; } long[] ret = new long[len]; if (s <= ((len - 1) / m)) { for (long i = ((long) (s)) * m; (i < len) && ((i - (s * m)) < aa.length); ++i) { ret[((int) (i))] = aa[((int) (i - (s * m)))]; } } return ret; } public long[] cyclicmulFFT(long[] a, long[] b, int n) { if (!isNTTFriendly) { throw new AssertionError("cyclicmulFFT requires NTT-friendly mod"); } if (Integer.bitCount(n) != 1) { throw new AssertionError(); } long[] A = new long[n]; long[] B = new long[n]; for (int i = 0; i < a.length; i++) { A[i % n] = addMod(A[i % n], fp.reduce(a[i])); } for (int i = 0; i < b.length; i++) { B[i % n] = addMod(B[i % n], fp.reduce(b[i])); } prepareRoots(n); fftToBitReversed(A); fftToBitReversed(B); for (int i = 0; i < n; ++i) { A[i] = (A[i] * B[i]) % mod; } ifftFromBitReversed(A); return Arrays.copyOf(A, n); } public long[] mulAll(long[][] f) { if (f.length == 0) { return new long[]{ 1 }; } long[][] copy = f.clone(); Arrays.sort(copy, (a, b) -> Arrays.compare(a, b)); Queue<long[]> pq = new ArrayDeque<>(); for (int i = 0; i < copy.length;) { int j = i; while ((j < copy.length) && Arrays.equals(copy[i], copy[j])) { j++; } int count = j - i; if (count == 1) { pq.add(copy[i]); } else { pq.add(powFull(copy[i], count)); } i = j; } while (pq.size() >= 2) { pq.add(mul(pq.poll(), pq.poll())); } return pq.peek(); } public long[][] sumRationals(long[][][] rationals) { Queue<long[][]> que = new ArrayDeque<>(); for (long[][] r : rationals) { que.add(r); } while (que.size() >= 2) { long[][] a = que.poll(); long[][] b = que.poll(); que.add(new long[][]{ add(mul(a[0], b[1]), mul(a[1], b[0])), mul(a[1], b[1]) }); } return que.poll(); } public long[] multipointEval(long[] a, long[] points) { int M = points.length; int len = 1; while (len < M) { len *= 2; } long[][] mods = new long[2 * len][]; long[][] modded = new long[2 * len][]; for (int i = 0; i < len; i++) { mods[i + len] = (i < M) ? new long[]{ (mod - points[i]) % mod, 1 } : new long[]{ 1 }; } for (int i = len - 1, e = 0; i >= 1; i--) { if ((((mods[2 * i].length == mods[(2 * i) + 1].length) && (mods[2 * i].length == (1 + (1 << e)))) && (e >= 10)) && isNTTFriendly) { mods[i] = cyclicmulFFT(mods[2 * i], mods[(2 * i) + 1], 1 << (e + 1)); mods[i] = Arrays.copyOf(mods[i], 1 + (1 << (e + 1))); mods[i][0]--; if (mods[i][0] < 0) { mods[i][0] += mod; } mods[i][1 << (e + 1)] = 1; } else { mods[i] = mul(mods[2 * i], mods[(2 * i) + 1]); } } modded[1] = mod(a, mods[1]); for (int i = 2; i < (2 * len); i++) { modded[i] = mod(modded[i / 2], mods[i]); } long[] ret = new long[M]; for (int i = 0; i < M; i++) { if (modded[i + len].length > 0) { ret[i] = modded[i + len][0]; } } return ret; } public long[] interpolate(long[] x, long[] y) { if (x.length != y.length) { throw new AssertionError(); } int n = x.length; long[][] a = new long[n][2]; for (int i = 0; i < n; i++) { a[i] = new long[]{ (mod - x[i]) % mod, 1 }; } long[] f = mulAll(a); long[] df = differentiate(f); long[] evals = multipointEval(df, x); long[][][] b = new long[n][2][2]; for (int i = 0; i < n; i++) { b[i][0] = new long[]{ (y[i] * MathUtils.modInv(evals[i], mod)) % mod }; b[i][1] = new long[]{ (mod - x[i]) % mod, 1 }; } long[][] q = sumRationals(b); long[] h = div(mul(f, q[0]), q[1]); return Arrays.copyOf(h, n); } @Override public long[] exactDiv(long[] a, long[] b) { return div(a, b); } @Override public long[] div(long[] a, long[] b) { if (b.length == 1) { if (b[0] == 0) { throw new ArithmeticException("Division by zero"); } if (b[0] == 1) { return a.clone(); } long inv = fp.inv(b[0]); long[] res = new long[a.length]; for (int i = 0; i < a.length; i++) { res[i] = (a[i] * inv) % mod; } return res; } int degA = deg(a); int degB = deg(b); if ((isNTTFriendly && (((degA - degB) + 1) > FFT_NAIVE_THRESHOLD)) && (degB >= 10)) { return divFast(a, b); } return divNaive(a, b); } public long[] divFast(long[] a, long[] b) { int degA = deg(a); int degB = deg(b); if (degA < degB) { return new long[]{ 0 }; } long[] ra = resize(a); long[] rb = resize(b); ArrayUtils.reverse(ra); ArrayUtils.reverse(rb); rb = Arrays.copyOf(rb, degA + 1); long[] q = mul(ra, inv(rb)); q = Arrays.copyOf(q, (degA - degB) + 1); ArrayUtils.reverse(q); return q; } @Override public long[] mod(long[] a, long[] b) { int degA = deg(a); int degB = deg(b); if (isNTTFriendly && (((degA - degB) + 1) > FFT_NAIVE_THRESHOLD)) { return modFast(a, b); } return modNaive(a, b); } public long[] modFast(long[] a, long[] b) { long[] q = divFast(a, b); return resize(sub(a, mul(b, q))); } public class HalfGcdResult { public long[] p00; public long[] p01; public long[] p10; public long[] p11; public HalfGcdResult(long[] p00, long[] p01, long[] p10, long[] p11) { this.p00 = p00; this.p01 = p01; this.p10 = p10; this.p11 = p11; } public long[][] apply(long[] a, long[] b) { return new long[][]{ resize(add(mul(p00, a), mul(p01, b))), resize(add(mul(p10, a), mul(p11, b))) }; } HalfGcdResult swapColumns() { return new HalfGcdResult(p01, p00, p11, p10); } } HalfGcdResult identityMatrix() { return new HalfGcdResult(new long[]{ 1 }, new long[]{ 0 }, new long[]{ 0 }, new long[]{ 1 }); } HalfGcdResult leftMulEuclideanStep(HalfGcdResult mat, long[] q) { return new HalfGcdResult(mat.p10, mat.p11, sub(mat.p00, mul(q, mat.p10)), sub(mat.p01, mul(q, mat.p11))); } HalfGcdResult multiplyMatrix(HalfGcdResult a, HalfGcdResult b) { return new HalfGcdResult(resize(add(mul(a.p00, b.p00), mul(a.p01, b.p10))), resize(add(mul(a.p00, b.p01), mul(a.p01, b.p11))), resize(add(mul(a.p10, b.p00), mul(a.p11, b.p10))), resize(add(mul(a.p10, b.p01), mul(a.p11, b.p11)))); } HalfGcdResult halfGcdNaiveOrdered(long[] a, long[] b) { int threshold = deg(a) / 2; HalfGcdResult mat = identityMatrix(); while (deg(b) > threshold) { DivModResult dm = divmod(a, b); mat = leftMulEuclideanStep(mat, dm.q); a = b; b = dm.r; } return mat; } public HalfGcdResult halfGcd(long[] a, long[] b) { a = resize(a); b = resize(b); int degA = deg(a); int degB = deg(b); if (degB == (-1)) { return identityMatrix(); } if (degA < degB) { return halfGcd(b, a).swapColumns(); } if (degB <= (degA / 2)) { return identityMatrix(); } if (degA <= 128) { return halfGcdNaiveOrdered(a, b); } int threshold = degA / 2; int shift = (degA + 1) / 2; HalfGcdResult mat = halfGcd(divideByX(a, shift), divideByX(b, shift)); long[][] cd = mat.apply(a, b); long[] c = cd[0]; long[] d = cd[1]; if (deg(d) <= threshold) { return mat; } DivModResult dm = divmod(c, d); mat = leftMulEuclideanStep(mat, dm.q); c = d; d = dm.r; if (deg(d) <= threshold) { return mat; } int secondShift = (2 * threshold) - deg(c); if (secondShift < 0) { throw new AssertionError(); } return multiplyMatrix(halfGcd(divideByX(c, secondShift), divideByX(d, secondShift)), mat); } @Override public long[] gcd(long[] a, long[] b) { int degA = deg(a); int degB = deg(b); if (degA == (-1)) { return monic(b); } if (degB == (-1)) { return monic(a); } if ((degA == 0) || (degB == 0)) { return new long[]{ 1 }; } a = resize(a); b = resize(b); if (degA < degB) { long[] t = a; a = b; b = t; } while (deg(b) != (-1)) { if ((!isNTTFriendly) || (Math.max(deg(a), deg(b)) <= 3072)) { return gcdNaive(a, b); } HalfGcdResult mat = halfGcd(a, b); long[][] cd = mat.apply(a, b); a = cd[0]; b = cd[1]; if (deg(b) == (-1)) { break; } DivModResult dm = divmod(a, b); a = b; b = dm.r; if (deg(a) < deg(b)) { long[] t = a; a = b; b = t; } } return monic(a); } @Override public EuclideanDomainStrategy.ExtGCDResult<long[]> extgcd(long[] f, long[] g) { f = resize(f); g = resize(g); long[] a = f; long[] b = g; long[] x0 = new long[]{ 1 }; long[] y0 = new long[]{ 0 }; long[] x1 = new long[]{ 0 }; long[] y1 = new long[]{ 1 }; if (Math.max(deg(a), deg(b)) <= 3072) { while (deg(b) != (-1)) { DivModResult dm = divmod(a, b); long[] nx = sub(x0, mul(dm.q, x1)); long[] ny = sub(y0, mul(dm.q, y1)); a = b; b = dm.r; x0 = x1; y0 = y1; x1 = resize(nx); y1 = resize(ny); } } else { if (deg(a) < deg(b)) { long[] t = a; a = b; b = t; t = x0; x0 = x1; x1 = t; t = y0; y0 = y1; y1 = t; } while (deg(b) != (-1)) { HalfGcdResult mat = halfGcd(a, b); long[][] cd = mat.apply(a, b); long[] nx0 = resize(add(mul(mat.p00, x0), mul(mat.p01, x1))); long[] ny0 = resize(add(mul(mat.p00, y0), mul(mat.p01, y1))); long[] nx1 = resize(add(mul(mat.p10, x0), mul(mat.p11, x1))); long[] ny1 = resize(add(mul(mat.p10, y0), mul(mat.p11, y1))); a = cd[0]; b = cd[1]; x0 = nx0; y0 = ny0; x1 = nx1; y1 = ny1; if (deg(b) == (-1)) { break; } DivModResult dm = divmod(a, b); nx1 = resize(sub(x0, mul(dm.q, x1))); ny1 = resize(sub(y0, mul(dm.q, y1))); a = b; b = dm.r; x0 = x1; y0 = y1; x1 = nx1; y1 = ny1; if (deg(a) < deg(b)) { long[] t = a; a = b; b = t; t = x0; x0 = x1; x1 = t; t = y0; y0 = y1; y1 = t; } } } a = resize(a); int d = deg(a); if (d == (-1)) { return new EuclideanDomainStrategy.ExtGCDResult<>(new long[]{ 0 }, new long[]{ 0 }, new long[]{ 0 }); } long inv = MathUtils.modInv(a[d], mod); return new EuclideanDomainStrategy.ExtGCDResult<>(resize(mul(x0, inv)), resize(mul(y0, inv)), resize(mul(a, inv))); } public long[] comp(long[] f, long[] g, int n) { if (g[0] != 0) { throw new AssertionError(); } long[] num = resize(f); int m = num.length; ArrayUtils.reverse(num); int degG = deg(g); if (degG == (-1)) { long[] ret = new long[n]; ret[0] = f[0]; return ret; } long[][] den = new long[degG + 1][2]; den[0][0] = 1; for (int i = 0; i <= degG; i++) { den[i][1] = (mod - g[i]) % mod; } PolynomialFpDynamic2D p2d = PolynomialFpDynamic2D.of(this); long[][] x = comp2d(m - 1, m, n, num, den, p2d); long[] ret = new long[x.length]; for (int i = 0; i < x.length; i++) { ret[i] = x[i][0]; } return ret; } long[][] comp2d(int l, int r, int n, long[] p, long[][] q, PolynomialFpDynamic2D p2d) { if (n == 0) { return new long[1][1]; } if (n == 1) { long[] a = mul(p, inv(q[0])); long[][] ret = new long[1][r - l]; for (int i = l; i < r; i++) { ret[0][i - l] = (i < a.length) ? a[i] : 0; } return ret; } long[][] negatedQ = ArrayUtils.copy(q); for (int i = 0; i < negatedQ.length; i++) { for (int j = 0; j < negatedQ[i].length; j++) { if ((i % 2) == 1) { negatedQ[i][j] = (negatedQ[i][j] * (mod - 1)) % mod; } } } int e = Math.max(0, l - (q[0].length - 1)); q = p2d.mul(q, negatedQ); long[][] v = new long[(n + 1) / 2][q[0].length]; for (int i = 0; (i < n) && (i < q.length); i += 2) { for (int j = 0; j < q[i].length; j++) { v[i / 2][j] = q[i][j]; } } long[][] x = comp2d(e, r, (n + 1) / 2, p, v, p2d); long[][] a = new long[x.length * 2][x[0].length]; for (int i = 0; i < x.length; i++) { for (int j = 0; j < x[i].length; j++) { a[2 * i][j] = x[i][j]; } } a = p2d.mul(a, negatedQ); long[][] ret = new long[n][r - l]; for (int i = 0; (i < n) && (i < a.length); i++) { for (int j = l - e; (j < (r - e)) && (j < a[i].length); j++) { ret[i][j - (l - e)] = a[i][j]; } } return ret; } public long eval(long[] f, long x) { long res = 0; for (int i = f.length - 1; i >= 0; i--) { res = ((res * x) + fp.reduce(f[i])) % mod; } return res; } public long[] sparsePow(long[] f, int n, long k) { if (n <= 0) { return new long[0]; } if (k == 0) { long[] res = new long[n]; res[0] = 1; return res; } int d0 = 0; while (((d0 < f.length) && (d0 < n)) && (fp.reduce(f[d0]) == 0)) { d0++; } if ((d0 == f.length) || (d0 >= n)) { return new long[n]; } if ((d0 > 0) && (((n - 1) / d0) < k)) { return new long[n]; } int bias = ((int) (d0 * k)); if (bias >= n) { return new long[n]; } ArrayList<PolynomialZnDynamic.Term> terms = new ArrayList<>(); for (int i = d0 + 1; (i < f.length) && (i < n); i++) { long v = fp.reduce(f[i]); if (v != 0) { terms.add(new PolynomialZnDynamic.Term(i - d0, v)); } } long[] res = new long[n]; long f0 = fp.reduce(f[d0]); res[bias] = MathUtils.modPow(f0, k % (mod - 1), mod); long inv0 = fp.inv(f0); long kMod = k % mod; for (int d = 0; ((bias + d) + 1) < n; d++) { long tmp = 0; for (PolynomialZnDynamic.Term t : terms) { int j = d - t.d; if (j >= 0) { tmp = ((tmp + mod) - ((((t.v * res[(bias + j) + 1]) % mod) * (j + 1)) % mod)) % mod; } j = d - (t.d - 1); if (j >= 0) { tmp = (tmp + ((((((t.v * t.d) % mod) * res[bias + j]) % mod) * kMod) % mod)) % mod; } } res[(bias + d) + 1] = (((tmp * inv0) % mod) * fp.inv(d + 1)) % mod; } return res; } } class PolynomialFpDynamic2D implements UFDStrategy<long[][]> , ExactDivRingStrategy<long[][]> { public final long mod; Fp fp; final PolynomialFpDynamic poly1d; public static final PolynomialFpDynamic2D MOD998244353 = new PolynomialFpDynamic2D(PolynomialFpDynamic.MOD998244353); public static final PolynomialFpDynamic2D MOD469762049 = new PolynomialFpDynamic2D(PolynomialFpDynamic.MOD469762049); public static final PolynomialFpDynamic2D MOD167772161 = new PolynomialFpDynamic2D(PolynomialFpDynamic.MOD167772161); public static final PolynomialFpDynamic2D MOD754974721 = new PolynomialFpDynamic2D(PolynomialFpDynamic.MOD754974721); public static final PolynomialFpDynamic2D MOD1004535809 = new PolynomialFpDynamic2D(PolynomialFpDynamic.MOD1004535809); public static PolynomialFpDynamic2D of(PolynomialFpDynamic poly1d) { if (poly1d == PolynomialFpDynamic.MOD998244353) { return MOD998244353; } if (poly1d == PolynomialFpDynamic.MOD469762049) { return MOD469762049; } if (poly1d == PolynomialFpDynamic.MOD167772161) { return MOD167772161; } if (poly1d == PolynomialFpDynamic.MOD754974721) { return MOD754974721; } if (poly1d == PolynomialFpDynamic.MOD1004535809) { return MOD1004535809; } return new PolynomialFpDynamic2D(poly1d); } private PolynomialFpDynamic2D(PolynomialFpDynamic poly1d) { this.mod = poly1d.mod; fp = new Fp(mod); this.poly1d = poly1d; } public long[][] mulNaive(long[][] a, long[][] b) { int m0 = 0; int m1 = 0; for (long[] row : a) { m0 = Math.max(m0, row.length); } for (long[] row : b) { m1 = Math.max(m1, row.length); } if ((((a.length == 0) || (b.length == 0)) || (m0 == 0)) || (m1 == 0)) { return zero(); } ArrayList<Integer> ai = new ArrayList<>(); ArrayList<Integer> aj = new ArrayList<>(); ArrayList<Long> av = new ArrayList<>(); for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { if (a[i][j] != 0) { ai.add(i); aj.add(j); av.add(a[i][j]); } } } ArrayList<Integer> bi = new ArrayList<>(); ArrayList<Integer> bj = new ArrayList<>(); ArrayList<Long> bv = new ArrayList<>(); for (int i = 0; i < b.length; i++) { for (int j = 0; j < b[i].length; j++) { if (b[i][j] != 0) { bi.add(i); bj.add(j); bv.add(b[i][j]); } } } long[][] c = new long[(a.length + b.length) - 1][(m0 + m1) - 1]; for (int k = 0; k < av.size(); k++) { long v = av.get(k); int r = ai.get(k); int s = aj.get(k); for (int l = 0; l < bv.size(); l++) { c[r + bi.get(l)][s + bj.get(l)] = (c[r + bi.get(l)][s + bj.get(l)] + (v * bv.get(l))) % mod; } } return c; } @Override public long[][] zero() { return new long[0][0]; } @Override public long[][] one() { return new long[][]{ new long[]{ 1 } }; } @Override public long[][] add(long[][] a, long[][] b) { int n = Math.max(a.length, b.length); int m = 0; for (long[] row : a) { m = Math.max(m, row.length); } for (long[] row : b) { m = Math.max(m, row.length); } long[][] c = new long[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { long va = ((i < a.length) && (j < a[i].length)) ? a[i][j] : 0; long vb = ((i < b.length) && (j < b[i].length)) ? b[i][j] : 0; c[i][j] = poly1d.addMod(va, vb); } } return c; } @Override public long[][] sub(long[][] a, long[][] b) { int n = Math.max(a.length, b.length); int m = 0; for (long[] row : a) { m = Math.max(m, row.length); } for (long[] row : b) { m = Math.max(m, row.length); } long[][] c = new long[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { long va = ((i < a.length) && (j < a[i].length)) ? a[i][j] : 0; long vb = ((i < b.length) && (j < b[i].length)) ? b[i][j] : 0; c[i][j] = poly1d.subMod(va, vb); } } return c; } @Override public long[][] neg(long[][] a) { long[][] c = new long[a.length][]; for (int i = 0; i < a.length; i++) { c[i] = new long[a[i].length]; for (int j = 0; j < a[i].length; j++) { if (a[i][j] != 0) { c[i][j] = mod - a[i][j]; } } } return c; } @Override public boolean equals(long[][] a, long[][] b) { int nx = Math.max(a.length, b.length); for (int i = 0; i < nx; i++) { long[] ra = (i < a.length) ? a[i] : new long[0]; long[] rb = (i < b.length) ? b[i] : new long[0]; int ny = Math.max(ra.length, rb.length); for (int j = 0; j < ny; j++) { long va = (j < ra.length) ? ra[j] : 0; long vb = (j < rb.length) ? rb[j] : 0; if (va != vb) { return false; } } } return true; } @Override public long[][] exactDiv(long[][] a, long[][] b) { return lexdiv(a, b); } public DivModResult lexdivmod(long[][] a, long[][] b) { a = resize(a); b = resize(b); int dxB = degX(b); if (dxB == (-1)) { throw new ArithmeticException("division by zero polynomial"); } int dxA = degX(a); if (dxA < dxB) { return new DivModResult(zero(), a); } int dyA = degY(a); int dyB = degY(b); int stride = (Math.max(dyA, dyB) + (((dxA - dxB) + 1) * dyB)) + 1; long[] fa = flattenKronecker(a, stride); long[] fb = flattenKronecker(b, stride); PolynomialFpDynamic.DivModResult res = poly1d.divmod(fa, fb); long[][] q = unflattenKronecker(res.q, stride, Math.max(0, dxA - dxB), stride - 1); long[][] r = unflattenKronecker(res.r, stride, dxB, stride - 1); return new DivModResult(q, r); } public long[][] lexdiv(long[][] a, long[][] b) { a = resize(a); b = resize(b); int dxB = degX(b); if (dxB == (-1)) { throw new ArithmeticException("division by zero polynomial"); } if ((dxB == 0) && (poly1d.deg(b[0]) == 0)) { long inv = fp.inv(b[0][0]); long[][] res = new long[a.length][]; for (int i = 0; i < a.length; i++) { res[i] = poly1d.mul(a[i], inv); } return resize(res); } return lexdivmod(a, b).q; } public long[][] mul(long[][] a, long b) { long[][] res = new long[a.length][]; for (int i = 0; i < a.length; i++) { res[i] = poly1d.mul(a[i], b); } return res; } @Override public long[][] mul(long[][] a, long[][] b) { int m0 = 0; int m1 = 0; for (long[] row : a) { m0 = Math.max(m0, row.length); } for (long[] row : b) { m1 = Math.max(m1, row.length); } if ((((a.length == 0) || (b.length == 0)) || (m0 == 0)) || (m1 == 0)) { return zero(); } if ((!poly1d.isNTTFriendly) || (Math.min((1L * a.length) * m0, (1L * b.length) * m1) < 16)) { return mulNaive(a, b); } int stride = (m0 + m1) - 1; long[] f = new long[stride * a.length]; long[] g = new long[stride * b.length]; for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { f[(i * stride) + j] = a[i][j]; } } for (int i = 0; i < b.length; i++) { for (int j = 0; j < b[i].length; j++) { g[(i * stride) + j] = b[i][j]; } } long[] h = poly1d.mul(f, g); long[][] c = new long[(a.length + b.length) - 1][stride]; for (int i = 0; i < h.length; i++) { if (h[i] != 0) { c[i / stride][i % stride] = h[i]; } } return c; } public int degX(long[][] a) { for (int i = a.length - 1; i >= 0; i--) { if (poly1d.deg(a[i]) != (-1)) { return i; } } return -1; } public boolean isZero(long[][] f) { return degX(f) == (-1); } public long[][] resize(long[][] a) { int dx = degX(a); if (dx == (-1)) { return new long[0][0]; } long[][] res = new long[dx + 1][]; for (int i = 0; i <= dx; i++) { res[i] = (a[i] == null) ? poly1d.zero() : poly1d.resize(a[i]); } return res; } public long lead(long[][] a) { int dx = degX(a); if (dx == (-1)) { return 0; } if (a[dx] == null) { return 0; } int dy = poly1d.deg(a[dx]); return a[dx][dy]; } public long[][] monic(long[][] a) { a = resize(a); long leadVal = lead(a); if (leadVal == 0) { return a; } long inv = fp.inv(leadVal); long[][] res = new long[a.length][]; for (int i = 0; i < a.length; i++) { if (a[i] == null) { res[i] = poly1d.zero(); continue; } res[i] = new long[a[i].length]; for (int j = 0; j < a[i].length; j++) { res[i][j] = (a[i][j] * inv) % mod; } } return res; } public long[] contentX(long[][] a) { long[] g = poly1d.zero(); for (long[] row : a) { if (row != null) { g = poly1d.gcd(g, row); } } return g; } public long[][] lexdivByPolyY(long[][] a, long[] p) { long[][] res = new long[a.length][]; for (int i = 0; i < a.length; i++) { res[i] = (a[i] == null) ? poly1d.zero() : poly1d.div(a[i], p); } return res; } public long[][] mulByPolyY(long[][] a, long[] p) { long[][] res = new long[a.length][]; for (int i = 0; i < a.length; i++) { res[i] = (a[i] == null) ? poly1d.zero() : poly1d.mul(a[i], p); } return res; } public static class DivModResult { public long[][] q; public long[][] r; public DivModResult(long[][] q, long[][] r) { this.q = q; this.r = r; } } private long[] flattenKronecker(long[][] a, int sx) { a = resize(a); if (degX(a) == (-1)) { return poly1d.zero(); } long[] res = new long[((degX(a) * sx) + degY(a)) + 1]; for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { if (a[i][j] != 0) { res[(i * sx) + j] = a[i][j]; } } } return poly1d.resize(res); } private long[][] unflattenKronecker(long[] a, int sx, int maxX, int maxY) { a = poly1d.resize(a); if (a.length == 0) { return zero(); } long[][] res = new long[maxX + 1][maxY + 1]; for (int idx = 0; idx < a.length; idx++) { if (a[idx] == 0) { continue; } int x = idx / sx; int y = idx % sx; if ((x > maxX) || (y > maxY)) { return null; } res[x][y] = a[idx]; } return resize(res); } public int degY(long[][] a) { int res = -1; for (long[] row : a) { res = Math.max(res, poly1d.deg(row)); } return res; } @Override public long[][] gcd(long[][] a, long[][] b) { a = resize(a); b = resize(b); if (degX(a) == (-1)) { return monic(b); } if (degX(b) == (-1)) { return monic(a); } long[] contA = contentX(a); long[] contB = contentX(b); long[] gCont = poly1d.gcd(contA, contB); long[][] primA = lexdivByPolyY(a, contA); long[][] primB = lexdivByPolyY(b, contB); long[][] resPrim = gcdZippel(primA, primB); if (resPrim == null) { var field = new FractionFieldStrategy<>(poly1d); var strategy = new PolynomialEuclideanStrategy<>(field); FractionFieldElement<long[]>[] fA = toFractionArray(primA); FractionFieldElement<long[]>[] fB = toFractionArray(primB); FractionFieldElement<long[]>[] fG = strategy.gcd(fA, fB); resPrim = fromFractionArray(fG); } return monic(mulByPolyY(resPrim, gCont)); } private long[][] gcdZippel(long[][] f, long[][] g) { f = resize(f); g = resize(g); if (degX(f) == (-1)) { return monic(g); } if (degX(g) == (-1)) { return monic(f); } if (degX(f) < degX(g)) { long[][] t = f; f = g; g = t; } long[] lcf = f[degX(f)]; long[] lcg = g[degX(g)]; Random rnd = new Random(0); for (int attempt = 0; attempt < 20; attempt++) { long ry = poly1d.fp.reduce(rnd.nextLong()); if ((poly1d.eval(lcf, ry) == 0) || (poly1d.eval(lcg, ry) == 0)) { continue; } long[] f_r = new long[f.length]; for (int i = 0; i < f.length; i++) { f_r[i] = poly1d.eval(f[i], ry); } long[] g_r = new long[g.length]; for (int i = 0; i < g.length; i++) { g_r[i] = poly1d.eval(g[i], ry); } long[] gcd_r = poly1d.gcd(f_r, g_r); int skelDeg = poly1d.deg(gcd_r); if (skelDeg == (-1)) { continue; } long[][] G = new long[skelDeg + 1][]; boolean success = true; for (int i = 0; i <= skelDeg; i++) { if (gcd_r[i] == 0) { G[i] = new long[0]; continue; } G[i] = interpolateZippel(f, g, i, ry, gcd_r[i], skelDeg); if (G[i] == null) { success = false; break; } } if (!success) { continue; } long[][] res = resize(G); try { if (isDivisible(f, res) && isDivisible(g, res)) { return monic(res); } } catch (Exception e) { } } return null; } private long[] interpolateZippel(long[][] f, long[][] g, int xIdx, long ry, long targetVal, int skelDeg) { long[] lcf = f[degX(f)]; long[] lcg = g[degX(g)]; Random rnd = new Random(0); ArrayList<Long> pointsY = new ArrayList<>(); ArrayList<Long> valuesY = new ArrayList<>(); pointsY.add(ry); valuesY.add(targetVal); long[] currentCoeffPolyY = new long[]{ targetVal }; for (int t = 0; t < (degY(f) + 2); t++) { long ry2 = poly1d.fp.reduce(rnd.nextLong()); if ((poly1d.eval(lcf, ry2) == 0) || (poly1d.eval(lcg, ry2) == 0)) { continue; } long[] f_ry2 = new long[f.length]; for (int j = 0; j < f.length; j++) { f_ry2[j] = poly1d.eval(f[j], ry2); } long[] g_ry2 = new long[g.length]; for (int j = 0; j < g.length; j++) { g_ry2[j] = poly1d.eval(g[j], ry2); } long[] gcd_ry2 = poly1d.gcd(f_ry2, g_ry2); if (poly1d.deg(gcd_ry2) != skelDeg) { continue; } pointsY.add(ry2); valuesY.add(xIdx < gcd_ry2.length ? gcd_ry2[xIdx] : 0L); long[] p_arr = new long[pointsY.size()]; long[] v_arr = new long[valuesY.size()]; for (int j = 0; j < pointsY.size(); j++) { p_arr[j] = pointsY.get(j); v_arr[j] = valuesY.get(j); } long[] nextCoeffPolyY = poly1d.interpolate(p_arr, v_arr); if (Arrays.equals(nextCoeffPolyY, currentCoeffPolyY)) { return currentCoeffPolyY; } currentCoeffPolyY = nextCoeffPolyY; if (pointsY.size() > (degY(f) + 1)) { break; } } return currentCoeffPolyY; } private boolean isDivisible(long[][] a, long[][] b) { if (degX(b) == (-1)) { return false; } try { long[][] q = lexdiv(a, b); return equals(mul(b, q), a); } catch (Exception e) { return false; } } private FractionFieldElement<long[]>[] toFractionArray(long[][] a) { @SuppressWarnings("unchecked") FractionFieldElement<long[]>[] res = new FractionFieldElement[a.length]; var field = new FractionFieldStrategy<>(poly1d); for (int i = 0; i < a.length; i++) { res[i] = field.of(poly1d.resize(a[i]), poly1d.one()); } return res; } private long[][] fromFractionArray(FractionFieldElement<long[]>[] a) { long[] commonDen = new long[]{ 1 }; for (var f : a) { long[] g = poly1d.gcd(commonDen, f.den()); commonDen = poly1d.mul(commonDen, poly1d.div(f.den(), g)); } long[][] res = new long[a.length][]; for (int i = 0; i < a.length; i++) { res[i] = poly1d.mul(a[i].num(), poly1d.div(commonDen, a[i].den())); } return res; } } class PolynomialRingStrategy<T> implements IntegralDomainStrategy<T[]> , ExactDivRingStrategy<T[]> { protected final CommutativeRingStrategy<T> base; protected final Class<T> clazz; @SuppressWarnings("unchecked") public PolynomialRingStrategy(CommutativeRingStrategy<T> base) { this.base = base; this.clazz = ((Class<T>) (base.zero().getClass())); } protected T[] createArray(int n) { @SuppressWarnings("unchecked") T[] arr = ((T[]) (Array.newInstance(clazz, n))); Arrays.fill(arr, base.zero()); return arr; } protected T[] trim(T[] a) { int n = a.length; while ((n > 0) && base.equals(a[n - 1], base.zero())) { n--; } if (n == a.length) { return a; } return Arrays.copyOf(a, n); } @Override public T[] zero() { return createArray(0); } @Override public T[] one() { T[] res = createArray(1); res[0] = base.one(); return res; } @Override public T[] add(T[] a, T[] b) { T[] res = createArray(Math.max(a.length, b.length)); for (int i = 0; i < res.length; i++) { T va = (i < a.length) ? a[i] : base.zero(); T vb = (i < b.length) ? b[i] : base.zero(); res[i] = base.add(va, vb); } return trim(res); } @Override public T[] sub(T[] a, T[] b) { T[] res = createArray(Math.max(a.length, b.length)); for (int i = 0; i < res.length; i++) { T va = (i < a.length) ? a[i] : base.zero(); T vb = (i < b.length) ? b[i] : base.zero(); res[i] = base.sub(va, vb); } return trim(res); } @Override public T[] mul(T[] a, T[] b) { if ((a.length == 0) || (b.length == 0)) { return zero(); } T[] res = createArray((a.length + b.length) - 1); for (int i = 0; i < a.length; i++) { if (base.equals(a[i], base.zero())) { continue; } for (int j = 0; j < b.length; j++) { res[i + j] = base.add(res[i + j], base.mul(a[i], b[j])); } } return trim(res); } @Override public T[] neg(T[] a) { T[] res = createArray(a.length); for (int i = 0; i < a.length; i++) { res[i] = base.neg(a[i]); } return res; } @Override public boolean equals(T[] a, T[] b) { T[] ta = trim(a); T[] tb = trim(b); if (ta.length != tb.length) { return false; } for (int i = 0; i < ta.length; i++) { if (!base.equals(ta[i], tb[i])) { return false; } } return true; } @Override public T[] exactDiv(T[] a, T[] b) { T[] ta = trim(a); T[] tb = trim(b); if (tb.length == 0) { throw new ArithmeticException("Division by zero"); } if (ta.length < tb.length) { if (ta.length == 0) { return zero(); } throw new ArithmeticException("Not exactly divisible"); } if (!(base instanceof FieldStrategy)) { T[] res = createArray((ta.length - tb.length) + 1); T[] rem = ta.clone(); if (!(base instanceof ExactDivRingStrategy)) { throw new UnsupportedOperationException("Base must be ExactDivRingStrategy"); } ExactDivRingStrategy<T> ex = ((ExactDivRingStrategy<T>) (base)); for (int i = ta.length - 1; i >= (tb.length - 1); i--) { res[(i - tb.length) + 1] = ex.exactDiv(rem[i], tb[tb.length - 1]); T q = res[(i - tb.length) + 1]; for (int j = 0; j < tb.length; j++) { rem[((i - tb.length) + 1) + j] = base.sub(rem[((i - tb.length) + 1) + j], base.mul(q, tb[j])); } } for (T r : rem) { if (!base.equals(r, base.zero())) { throw new ArithmeticException("Not exactly divisible"); } } return trim(res); } return new PolynomialEuclideanStrategy<>(((FieldStrategy<T>) (base))).div(a, b); } } class PolynomialZnDynamic implements CommutativeRingStrategy<long[]> { public final long mod; public final Zn zn; public PolynomialZnDynamic(long mod) { this.mod = mod; this.zn = new Zn(mod); } protected long addMod(long a, long b) { long sum = a + b; return sum >= mod ? sum - mod : sum; } protected long subMod(long a, long b) { long diff = a - b; return diff < 0 ? diff + mod : diff; } public int countTerms(long[] a, int limit) { int count = 0; for (long v : a) { if (zn.reduce(v) != 0) { count++; if (count > limit) { return count; } } } return count; } public long[] mulNaive(long[] a, long[] b) { long[] c = new long[(a.length + b.length) - 1]; for (int i = 0; i < a.length; i++) { if (a[i] == 0) { continue; } for (int j = 0; j < b.length; j++) { if (b[j] == 0) { continue; } c[i + j] = (c[i + j] + (a[i] * b[j])) % mod; } } return c; } protected long[] mulCRT(long[] a, long[] b) { int n = a.length; int m = b.length; long m1 = 998244353L; long m2 = 469762049L; long m3 = 167772161L; double maxVal = (((double) (Math.min(n, m))) * (mod - 1)) * (mod - 1); int k_count = 3; if (maxVal < m1) { k_count = 1; } else if (maxVal < (((double) (m1)) * m2)) { k_count = 2; } long[] res1 = PolynomialFpDynamic.MOD998244353.mulFFT(a, b); if (k_count == 1) { for (int i = 0; i < res1.length; i++) { res1[i] %= mod; } return res1; } long[] res2 = PolynomialFpDynamic.MOD469762049.mulFFT(a, b); if (k_count == 2) { int len = res1.length; long[] res = new long[len]; long[] v = new long[2]; long[] ms = new long[]{ m1, m2 }; for (int i = 0; i < len; i++) { v[0] = res1[i]; v[1] = res2[i]; res[i] = Zn.crt(v, ms) % mod; } return res; } long[] res3 = PolynomialFpDynamic.MOD167772161.mulFFT(a, b); int len = res1.length; long[] res = new long[len]; long inv123 = MathUtils.modInv(((m1 % m3) * (m2 % m3)) % m3, m3); long m12m = ((m1 % mod) * (m2 % mod)) % mod; long[] v = new long[2]; long[] ms = new long[]{ m1, m2 }; for (int i = 0; i < len; i++) { v[0] = res1[i]; v[1] = res2[i]; long x12 = Zn.crt(v, ms); long k3 = ((((res3[i] - (x12 % m3)) + m3) % m3) * inv123) % m3; res[i] = ((x12 % mod) + (((k3 % mod) * m12m) % mod)) % mod; } return res; } @Override public long[] mul(long[] a, long[] b) { if ((a.length == 0) || (b.length == 0)) { return new long[0]; } if ((a.length == 1) && (b.length == 1)) { return new long[]{ (a[0] * b[0]) % mod }; } int n = a.length; int m = b.length; if (((n + m) - 1) <= 128) { return mulNaive(a, b); } int sparseThreshold = 50; int countB = countTerms(b, sparseThreshold); if (countB <= sparseThreshold) { return sparseMul(a, getTerms(b, countB), b.length); } int countA = countTerms(a, sparseThreshold); if (countA <= sparseThreshold) { return sparseMul(b, getTerms(a, countA), a.length); } if (((n + m) - 1) > 128) { return mulCRT(a, b); } return mulNaive(a, b); } public long[] squared(long[] a) { if (a.length == 0) { return new long[0]; } if (a.length == 1) { return new long[]{ (a[0] * a[0]) % mod }; } int len = (2 * a.length) - 1; if (len > 128) { return mulCRT(a, a); } return squaredNaive(a); } public long[] squaredNaive(long[] a) { int len = (2 * a.length) - 1; long[] ret = new long[len]; for (int i = 0; i < a.length; ++i) { if (a[i] == 0) { continue; } for (int j = i + 1; j < a.length; ++j) { if (a[j] == 0) { continue; } ret[i + j] = (ret[i + j] + ((2 * a[i]) * a[j])) % mod; } } for (int i = 0; i < a.length; ++i) { if (a[i] == 0) { continue; } ret[2 * i] = (ret[2 * i] + (a[i] * a[i])) % mod; } return ret; } public long[] powFull(long[] a, int n) { if (n == 0) { return new long[]{ 1 }; } if (n == 1) { return a.clone(); } int d = deg(a); if (d == (-1)) { return new long[0]; } if (d == 0) { return new long[]{ MathUtils.modPow(a[0], n, mod) }; } long[] ret = new long[1]; ret[0] = 1; long[] b = a.clone(); while (n != 0) { if ((n % 2) == 1) { ret = mul(ret, b); } n /= 2; if (n == 0) { break; } b = mul(b, b); } return ret; } @Override public long[] zero() { return new long[0]; } @Override public long[] one() { return new long[]{ 1 }; } @Override public long[] add(long[] a, long[] b) { long[] ret = new long[Math.max(a.length, b.length)]; for (int i = 0; i < ret.length; ++i) { ret[i] = (i < a.length ? a[i] : 0) + (i < b.length ? b[i] : 0); if (ret[i] >= mod) { ret[i] -= mod; } } return ret; } @Override public long[] neg(long[] a) { long[] ret = new long[a.length]; for (int i = 0; i < a.length; i++) { if (a[i] != 0) { ret[i] = mod - a[i]; } } return ret; } @Override public boolean equals(long[] a, long[] b) { int n = Math.max(a.length, b.length); for (int i = 0; i < n; i++) { long va = (i < a.length) ? a[i] : 0; long vb = (i < b.length) ? b[i] : 0; if (va != vb) { return false; } } return true; } @Override public boolean equals(Object o) { if (this == o) { return true; } if ((o == null) || (getClass() != o.getClass())) { return false; } PolynomialZnDynamic that = ((PolynomialZnDynamic) (o)); return mod == that.mod; } @Override public int hashCode() { return Objects.hash(mod); } public long norm(long[] a) { return deg(a) + 1; } public long[] canonicalUnit(long[] a) { int d = deg(a); if (d == (-1)) { return one(); } return new long[]{ a[d] }; } @Override public long[] sub(long[] a, long[] b) { if ((a.length == 1) && (b.length == 1)) { long diff = a[0] - b[0]; if (diff < 0) { diff += mod; } return new long[]{ diff }; } long[] ret = new long[Math.max(a.length, b.length)]; for (int i = 0; i < ret.length; ++i) { ret[i] = (i < a.length ? a[i] : 0) - (i < b.length ? b[i] : 0); if (ret[i] < 0) { ret[i] += mod; } } return ret; } public int deg(long[] a) { int n = a.length; if (n == 0) { return -1; } if (a[n - 1] != 0) { return n - 1; } for (int i = n - 2; i >= 0; i--) { if (a[i] != 0) { return i; } } return -1; } public boolean isZero(long[] f) { return deg(f) == (-1); } public long[] resize(long[] a) { return Arrays.copyOf(a, Math.max(0, deg(a)) + 1); } public static class Term { public final int d; public final long v; public Term(int d, long v) { this.d = d; this.v = v; } } public long[] sparseMul(long[] a, ArrayList<Term> sparseTerms, int sparseLen) { if ((a.length == 0) || (sparseLen == 0)) { return new long[0]; } long[] res = new long[(a.length + sparseLen) - 1]; if (sparseTerms.isEmpty()) { return res; } for (int i = 0; i < a.length; i++) { long v = zn.reduce(a[i]); if (v == 0) { continue; } for (Term t : sparseTerms) { res[i + t.d] = (res[i + t.d] + (v * t.v)) % mod; } } return res; } public ArrayList<Term> getTerms(long[] p, int initialCapacity) { ArrayList<Term> terms = new ArrayList<>(initialCapacity); for (int i = 0; i < p.length; i++) { long v = zn.reduce(p[i]); if (v != 0) { terms.add(new Term(i, v)); } } return terms; } public long[] divideByX(long[] f, int repeat) { return Arrays.copyOfRange(f, repeat, f.length); } } interface RingElement<X> extends SemiRingElement<X> { @Override RingStrategy<X> parent(); default X sub(X a) { return parent().sub(self(), a); } default X neg() { return parent().neg(self()); } } interface RingStrategy<T> extends SemiRingStrategy<T> { T neg(T a); default T sub(T a, T b) { return add(a, neg(b)); } } interface SemiRingElement<X> { SemiRingStrategy<X> parent(); X self(); default X add(X a) { return parent().add(self(), a); } default X mul(X a) { return parent().mul(self(), a); } default X pow(long n) { return parent().pow(self(), n); } default X one() { return parent().one(); } default X zero() { return parent().zero(); } } interface SemiRingStrategy<T> { T zero(); T one(); T add(T a, T b); T mul(T a, T b); boolean equals(T a, T b); default T pow(T a, long n) { if (n < 0) { throw new IllegalArgumentException("Exponent must be non-negative"); } T res = one(); T base = a; while (n > 0) { if ((n & 1) == 1) { res = mul(res, base); } base = mul(base, base); n >>= 1; } return res; } default boolean isZero(T a) { return equals(zero(), a); } default boolean isOne(T a) { return equals(one(), a); } default int hashCode(T a) { return Objects.hashCode(a); } } interface UFDElement<X extends UFDElement<X>> extends GCDDomainElement<X> {} interface UFDStrategy<T> extends GCDDomainStrategy<T> {} class Zn implements LongCommutativeRingStrategy { final long mod; public Zn(long mod) { this.mod = mod; } public long modulus() { return this.mod; } @Override public long zero() { return 0; } @Override public long one() { return 1 % mod; } public long pow(long a, long n) { if (n < 0) { throw new AssertionError(); } return MathUtils.modPow(a, n, mod); } public static long crt(long[] a, long[] m) { int N = a.length; long fac = 1; long x = 0; for (int i = 0; i < N; i++) { Fp mo = new Fp(m[i]); long c = mo.reduce((a[i] % m[i]) - (x % m[i])) * MathUtils.modInv(fac % m[i], m[i]); c = mo.reduce(c); x = x + (fac * c); fac *= m[i]; } return x; } @Override public long add(long a, long b) { long ret = (a + b) % mod; if (ret < 0) { ret += mod; } return ret; } public long sub(long a, long b) { long ret = (a - b) % mod; if (ret < 0) { ret += mod; } return ret; } @Override public long mul(long a, long b) { return (a * b) % mod; } @Override public long neg(long a) { return a == 0 ? 0 : mod - a; } @Override public boolean equals(long a, long b) { return a == b; } public long reduce(long a) { a %= mod; if (a < 0) { a += mod; } return a; } }