結果
| 問題 | No.940 ワープ ε=ε=ε=ε=ε=│;p>д＜│ |
| ユーザー |
 CuriousFairy315
|
| 提出日時 | 2021-04-04 05:40:10 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 879 ms / 5,000 ms |
| コード長 | 45,728 bytes |
| コンパイル時間 | 2,985 ms |
| コンパイル使用メモリ | 91,576 KB |
| 実行使用メモリ | 197,296 KB |
| 最終ジャッジ日時 | 2023-08-27 00:57:36 |
| 合計ジャッジ時間 | 14,986 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 283 ms
149,084 KB |
| testcase_01 | AC | 222 ms
149,040 KB |
| testcase_02 | AC | 219 ms
149,004 KB |
| testcase_03 | AC | 224 ms
149,044 KB |
| testcase_04 | AC | 213 ms
148,888 KB |
| testcase_05 | AC | 245 ms
149,064 KB |
| testcase_06 | AC | 228 ms
150,980 KB |
| testcase_07 | AC | 242 ms
149,328 KB |
| testcase_08 | AC | 225 ms
148,908 KB |
| testcase_09 | AC | 239 ms
149,020 KB |
| testcase_10 | AC | 225 ms
148,900 KB |
| testcase_11 | AC | 228 ms
149,088 KB |
| testcase_12 | AC | 254 ms
149,016 KB |
| testcase_13 | AC | 236 ms
148,884 KB |
| testcase_14 | AC | 222 ms
149,404 KB |
| testcase_15 | AC | 567 ms
189,020 KB |
| testcase_16 | AC | 747 ms
195,104 KB |
| testcase_17 | AC | 245 ms
149,156 KB |
| testcase_18 | AC | 235 ms
149,028 KB |
| testcase_19 | AC | 235 ms
149,024 KB |
| testcase_20 | AC | 236 ms
148,980 KB |
| testcase_21 | AC | 227 ms
149,008 KB |
| testcase_22 | AC | 697 ms
194,944 KB |
| testcase_23 | AC | 730 ms
195,388 KB |
| testcase_24 | AC | 723 ms
195,016 KB |
| testcase_25 | AC | 850 ms
197,296 KB |
| testcase_26 | AC | 879 ms
195,120 KB |
ソースコード
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.BitSet;
import java.util.NoSuchElementException;
public class Main {
public static void main(String[] args) {
new Main();
}
public Main() {
InputChecker ic = new InputChecker(System.in);
java.io.PrintWriter out = new java.io.PrintWriter(System.out);
solve(ic, out);
out.flush();
}
static final int MAX = 3123456;
static final long[] fac = new long[MAX];
static final long[] ifac = new long[MAX];
static final long[] inv = new long[MAX];
static final long[] pw2 = new long[MAX];
static final int MOD = 1_000_000_007;
{
fac[0] = fac[1] = ifac[0] = ifac[1] = inv[0] = inv[1] = pw2[0] = 1;
pw2[1] = 2;
for (int i = 2; i < fac.length; ++i) {
fac[i] = i * fac[i - 1] % MOD;
inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
ifac[i] = inv[i] * ifac[i - 1] % MOD;
pw2[i] = 2 * pw2[i - 1] % MOD;
}
}
static final long comb(int n, int k) {
return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}
public void solve(InputChecker ic, java.io.PrintWriter out) {
int X = ic.nextInt();
ic.nextChar(' ');
int Y = ic.nextInt();
ic.nextChar(' ');
int Z = ic.nextInt();
ic.readNewLine();
ic.checkEOF();
if (X == 0 && Y == 0 && Z == 0) {
out.println(1);
return;
}
int[] xxx = new int[] { X, Y, Z };
Arrays.sort(xxx);
X = xxx[2];
Y = xxx[1];
Z = xxx[0];
int[] f = new int[Math.min(X + Y, Math.min(Y + Z, Z + X)) + 1];
int[] g = new int[Math.min(X, Y) + 1];
int[] h = new int[Z + 1];
for (int i = 0; i < f.length; ++i) {
f[i] = (int)(pw2[X + Y + Z - 1 - i] * (i % 2 == 0 ? 1 : MOD - 1) % MOD * fac[X + Y + Z - i] % MOD
* ifac[X + Y - i] % MOD);
}
for (int i = 0; i < g.length; ++i) {
g[Math.min(X, Y) - i] = (int)(fac[X + Y - i] * ifac[X - i] % MOD * ifac[Y - i] % MOD * ifac[i] % MOD);
}
for (int i = 0; i < h.length; ++i) {
h[Z - i] = (int)(ifac[Z - i] * ifac[i] % MOD);
}
int[] fg = Convolution.convolution1_000_000_007(f, g);
long ret = 0;
for (int i = Math.max(0, Math.min(X, Y) + Z - h.length + 1); i < Math.min(fg.length,
Math.min(X, Y) + Z + 1); ++i) {
ret = (ret + (long)fg[i] * h[Math.min(X, Y) + Z - i]) % MOD;
}
out.println(ret);
}
public static int exponent10(int n, int e) {
return n * pow(10, e);
}
public static long exponent10L(int n, int e) {
return n * pow(10L, e);
}
public static int pow(int a, int b) {
int ans = 1;
for (int mul = a;b > 0;b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;
return ans;
}
public static long pow(long a, long b) {
long ans = 1;
for (long mul = a;b > 0;b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;
return ans;
}
public static class CharSet {
private final BitSet set = new BitSet(256);
public void add(char... c) {
for (char i : c) set.set(i);
}
public void add(CharSet... s) {
for (CharSet i : s) set.or(i.set);
}
public boolean contains(char... c) {
for (char i : c) if (!set.get(i)) return false;
return true;
}
public boolean contains(String s) {
return contains(s.toCharArray());
}
private static final class Chars extends CharSet {
public Chars(char... c) {
super.add(c);
}
public Chars(CharSet... s) {
super.add(s);
}
@Override
public void add(char... c) {
throw new UnsupportedOperationException();
}
@Override
public void add(CharSet... s) {
throw new UnsupportedOperationException();
}
}
public static final CharSet NUMBER = new Chars('0','1','2','3','4','5','6','7','8','9');
public static final CharSet LOWER = new Chars('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z');
public static final CharSet UPPER = new Chars('A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z');
public static final CharSet ALPHABET = new Chars(LOWER, UPPER);
}
public static class InputChecker {
private InputStream in;
private final byte[] buffer = new byte[1024];
private final byte[] undo = new byte[1024];
private int undoSize = 0;
private int read = 0;
private int length = 0;
public InputChecker(InputStream in) {
this.in = in;
}
public final void setInputStream(InputStream in) {
this.in = in;
}
public final void setInputStream(File in) {
try {
this.in = new FileInputStream(in);
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
private boolean hasNextByte() {
if (undoSize > 0) return true;
if (read < length) return true;
read = 0;
try {
length = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
return length > 0;
}
private byte readByte() {
if (hasNextByte()) return undoSize > 0 ? undo[--undoSize] : buffer[read++];
throw new NoSuchElementException();
}
private void undo(byte b) {
undo[undoSize ++] = b;
}
private void undo(char c) {
if ((c & 0xFF80) == 0) {
undo((byte)c);
return;
}
undo((byte)(c & 0x3F | 0x80));
if ((c & 0xF800) == 0) {
undo((byte)(c >> 6 & 0x1F | 0xC0));
} else {
undo((byte)(c >> 6 & 0x3F | 0x80));
undo((byte)(c >> 12 | 0xE0));
}
}
public final boolean hasNext() {
return hasNextByte();
}
public final char nextChar() {
byte b = readByte();
if ((b & 0x80) == 0) return (char)b;
if ((b & 0x20) == 0) return (char)((b & 0x1F) << 6 | readByte() & 0x3F);
return (char)((b & 0xF) << 12 | (readByte() & 0x3F) << 6 | readByte() & 0x3F);
}
public final char nextChar(char estimate) {
char c = nextChar();
if (estimate == c) return estimate;
undo(c);
throw new AssertionError();
}
public final char nextChar(CharSet estimate) {
char c = nextChar();
if (estimate.contains(c)) return c;
undo(c);
throw new AssertionError();
}
public final void readNewLine() {
char c = nextChar();
if (c == '\r') {
c = nextChar();
if (c != '\n') undo(c);
return;
} else if (c == '\n') return;
undo(c);
throw new AssertionError();
}
public final void checkEOF() {
if (hasNextByte()) throw new AssertionError();
}
public final String next(CharSet contains) {
StringBuilder sb = new StringBuilder();
try {
do {
char c = nextChar();
if (!contains.contains(c)) {
undo(c);
return sb.toString();
}
sb.append(c);
} while(true);
} catch (NoSuchElementException e) {
if (sb.length() <= 0) throw new AssertionError();
return sb.toString();
}
}
public final int nextInt() {
byte b = readByte();
int n = 0;
if (b == '-') {
if (!isNumber(b = readByte())) {
undo(b);
throw new NumberFormatException();
}
try {
if (b == '0') {
if (!isNumber(b = readByte())) {
undo(b);
return 0;
}
throw new NumberFormatException();
}
do n = Math.addExact(Math.multiplyExact(n, 10), '0' - b); while(isNumber(b = readByte()));
undo(b);
} catch (NoSuchElementException e) {
}
return n;
}
if (!isNumber(b)) {
undo(b);
throw new NumberFormatException();
}
try {
if (b == '0') {
if (!isNumber(b = readByte())) {
undo(b);
return 0;
}
throw new NumberFormatException();
}
do n = Math.addExact(Math.multiplyExact(n, 10), b - '0'); while(isNumber(b = readByte()));
undo(b);
} catch (NoSuchElementException e) {
}
return n;
}
public final int nextInt(int min, int max) {
int n = nextInt();
if (min <= n && n <= max) return n;
throw new NumberFormatException();
}
private static boolean isNumber(byte c) {
return '0' <= c && c <= '9';
}
public final long nextLong() {
byte b = readByte();
long n = 0;
if (b == '-') {
if (!isNumber(b = readByte())) {
undo(b);
throw new NumberFormatException();
}
try {
if (b == '0') {
if (!isNumber(b = readByte())) {
undo(b);
return 0;
}
throw new NumberFormatException();
}
do n = Math.addExact(Math.multiplyExact(n, 10), '0' - b); while(isNumber(b = readByte()));
undo(b);
} catch (NoSuchElementException e) {
}
return n;
}
if (!isNumber(b)) {
undo(b);
throw new NumberFormatException();
}
try {
if (b == '0') {
if (!isNumber(b = readByte())) {
undo(b);
return 0;
}
throw new NumberFormatException();
}
do n = Math.addExact(Math.multiplyExact(n, 10), b - '0'); while(isNumber(b = readByte()));
undo(b);
} catch (NoSuchElementException e) {
}
return n;
}
public final long nextLong(long min, long max) {
long n = nextLong();
if (min <= n && n <= max) return n;
throw new NumberFormatException();
}
public final double nextDouble() {
StringBuilder sb = new StringBuilder();
byte b = readByte();
if (b == '-') {
sb.append(b);
b = readByte();
}
if (b == '0') {
sb.append(b);
b = readByte();
} else {
while(isNumber(b)) {
sb.append(b);
b = readByte();
}
}
if (b == '.') {
sb.append(b);
b = readByte();
while(isNumber(b)) {
sb.append(b);
b = readByte();
}
}
if (b == 'e' || b == 'E') {
sb.append(b);
b = readByte();
if (b == '-' || b == '+') {
sb.append(b);
b = readByte();
}
while(isNumber(b)) {
sb.append(b);
b = readByte();
}
}
undo(b);
return Double.parseDouble(sb.toString());
}
}
public static final class MathLib {
public static class Barrett {
private final int mod;
private final long h, l;
private final long MAX = 1L << 62;
private final int MASK = (1 << 31) - 1;
Barrett(final int mod) {
this.mod = mod;
final long t = MAX / mod;
h = t >>> 31;
l = t & MASK;
}
int reduce(final long x) {
final long xh = x >>> 31, xl = x & MASK;
long z = xl * l;
z = xl * h + xh * l + (z >>> 31);
z = xh * h + (z >>> 31);
final int ret = (int) (x - z * mod);
return ret >= mod ? ret - mod : ret;
}
}
public static class BarrettSmall {
private final int mod;
final long t;
BarrettSmall(final int mod) {
this.mod = mod;
t = (1L << 42) / mod;
}
int reduce(long x) {
long q = x * t >> 42;
x -= q * mod;
return (int) (x >= mod ? x - mod : x);
}
}
private static long safe_mod(long x, final long m) {
x %= m;
if (x < 0) x += m;
return x;
}
private static long[] inv_gcd(long a, final long b) {
a = safe_mod(a, b);
if (a == 0) return new long[] { b, 0 };
long s = b, t = a;
long m0 = 0, m1 = 1;
while (t > 0) {
final long u = s / t;
s -= t * u;
m0 -= m1 * u;
long tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0) m0 += b / s;
return new long[] { s, m0 };
}
public static int pow(long n, long m, final int mod) {
assert m >= 0 && mod >= 1;
if (mod == 1) return 0;
return pow(n, m, new Barrett(mod));
}
public static int pow(long n, long m, Barrett mod) {
assert m >= 0;
long ans = 1, num = n;
while (m != 0) {
if ((m & 1) != 0) ans = mod.reduce(ans * num);
m >>>= 1;
num = mod.reduce(num * num);
}
return (int) ans;
}
public static int pow998_244_353(long n, long m) {
assert m >= 0;
long ans = 1, num = n;
while (m != 0) {
if ((m & 1) != 0) ans = ans * num % 998_244_353;
m >>>= 1;
num = num * num % 998_244_353;
}
return (int) ans;
}
public static int pow754_974_721(long n, long m) {
assert m >= 0;
long ans = 1, num = n;
while (m != 0) {
if ((m & 1) != 0) ans = ans * num % 754_974_721;
m >>>= 1;
num = num * num % 754_974_721;
}
return (int) ans;
}
public static int pow167_772_161(long n, long m) {
assert m >= 0;
long ans = 1, num = n;
while (m != 0) {
if ((m & 1) != 0) ans = ans * num % 167_772_161;
m >>>= 1;
num = num * num % 167_772_161;
}
return (int) ans;
}
public static int pow469_762_049(long n, long m) {
assert m >= 0;
long ans = 1, num = n;
while (m != 0) {
if ((m & 1) != 0) ans = ans * num % 469_762_049;
m >>>= 1;
num = num * num % 469_762_049;
}
return (int) ans;
}
public static int pow1_000_000_007(long n, long m) {
assert m >= 0;
long ans = 1, num = n;
while (m != 0) {
if ((m & 1) != 0) ans = ans * num % 1_000_000_007;
m >>>= 1;
num = num * num % 1_000_000_007;
}
return (int) ans;
}
public static int pow(long n, long m, BarrettSmall mod) {
assert m >= 0;
long ans = 1, num = n;
while (m != 0) {
if ((m & 1) != 0) ans = mod.reduce(ans * num);
m >>>= 1;
num = mod.reduce(num * num);
}
return (int) ans;
}
public static long[] crt(final long[] r, final long[] m) {
assert r.length == m.length;
final int n = r.length;
long r0 = 0, m0 = 1;
for (int i = 0; i < n; i++) {
assert 1 <= m[i];
long r1 = safe_mod(r[i], m[i]), m1 = m[i];
if (m0 < m1) {
long tmp = r0;
r0 = r1;
r1 = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 % m1 == 0) {
if (r0 % m1 != r1) return new long[] { 0, 0 };
continue;
}
final long[] ig = inv_gcd(m0, m1);
final long g = ig[0], im = ig[1];
final long u1 = m1 / g;
if ((r1 - r0) % g != 0) return new long[] { 0, 0 };
final long x = (r1 - r0) / g % u1 * im % u1;
r0 += x * m0;
m0 *= u1;
if (r0 < 0) r0 += m0;
// System.err.printf("%d %d\n", r0, m0);
}
return new long[] { r0, m0 };
}
public static long floor_sum(final long n, final long m, long a, long b) {
long ans = 0;
if (a >= m) {
ans += (n - 1) * n * (a / m) / 2;
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
final long y_max = (a * n + b) / m;
final long x_max = y_max * m - b;
if (y_max == 0) return ans;
ans += (n - (x_max + a - 1) / a) * y_max;
ans += floor_sum(y_max, a, m, (a - x_max % a) % a);
return ans;
}
}
/**
* Convolution.
*
* @verified https://atcoder.jp/contests/practice2/tasks/practice2_f
* @verified https://judge.yosupo.jp/problem/convolution_mod_1000000007
*/
public static final class Convolution {
/**
* writer: amotama 勝手に借りてます、問題あったらごめんね
*/
private static void fft(double[] a, double[] b, boolean invert) {
int count = a.length;
for (int i = 1, j = 0; i < count; i++) {
int bit = count >> 1;
for (; j >= bit; bit >>= 1) {
j -= bit;
}
j += bit;
if (i < j) {
double temp = a[i];
a[i] = a[j];
a[j] = temp;
temp = b[i];
b[i] = b[j];
b[j] = temp;
}
}
for (int len = 2; len <= count; len <<= 1) {
int halfLen = len >> 1;
double angle = 2 * Math.PI / len;
if (invert) {
angle = -angle;
}
double wLenA = Math.cos(angle);
double wLenB = Math.sin(angle);
for (int i = 0; i < count; i += len) {
double wA = 1;
double wB = 0;
for (int j = 0; j < halfLen; j++) {
double uA = a[i + j];
double uB = b[i + j];
double vA = a[i + j + halfLen] * wA - b[i + j + halfLen] * wB;
double vB = a[i + j + halfLen] * wB + b[i + j + halfLen] * wA;
a[i + j] = uA + vA;
b[i + j] = uB + vB;
a[i + j + halfLen] = uA - vA;
b[i + j + halfLen] = uB - vB;
double nextWA = wA * wLenA - wB * wLenB;
wB = wA * wLenB + wB * wLenA;
wA = nextWA;
}
}
}
if (invert) {
for (int i = 0; i < count; i++) {
a[i] /= count;
b[i] /= count;
}
}
}
/**
* writer: amotama 勝手に借りてます、問題あったらごめんね
*/
public static long[] convolution(long[] a, long[] b) {
int resultSize = Integer.highestOneBit(Math.max(a.length, b.length) - 1) << 2;
resultSize = Math.max(resultSize, 1);
double[] aReal = new double[resultSize];
double[] aImaginary = new double[resultSize];
double[] bReal = new double[resultSize];
double[] bImaginary = new double[resultSize];
for (int i = 0; i < a.length; i++) aReal[i] = a[i];
for (int i = 0; i < b.length; i++) bReal[i] = b[i];
fft(aReal, aImaginary, false);
if (a == b) {
System.arraycopy(aReal, 0, bReal, 0, aReal.length);
System.arraycopy(aImaginary, 0, bImaginary, 0, aImaginary.length);
} else {
fft(bReal, bImaginary, false);
}
for (int i = 0; i < resultSize; i++) {
double real = aReal[i] * bReal[i] - aImaginary[i] * bImaginary[i];
aImaginary[i] = aImaginary[i] * bReal[i] + bImaginary[i] * aReal[i];
aReal[i] = real;
}
fft(aReal, aImaginary, true);
long[] result = new long[a.length + b.length - 1];
for (int i = 0; i < result.length; i++) result[i] = Math.round(aReal[i]);
return result;
}
/**
* writer: amotama 勝手に借りてます、問題あったらごめんね
*/
public static int[] convolution(int[] a, int[] b) {
int resultSize = Integer.highestOneBit(Math.max(a.length, b.length) - 1) << 2;
resultSize = Math.max(resultSize, 1);
double[] aReal = new double[resultSize];
double[] aImaginary = new double[resultSize];
double[] bReal = new double[resultSize];
double[] bImaginary = new double[resultSize];
for (int i = 0; i < a.length; i++) aReal[i] = a[i];
for (int i = 0; i < b.length; i++) bReal[i] = b[i];
fft(aReal, aImaginary, false);
if (a == b) {
System.arraycopy(aReal, 0, bReal, 0, aReal.length);
System.arraycopy(aImaginary, 0, bImaginary, 0, aImaginary.length);
} else {
fft(bReal, bImaginary, false);
}
for (int i = 0; i < resultSize; i++) {
double real = aReal[i] * bReal[i] - aImaginary[i] * bImaginary[i];
aImaginary[i] = aImaginary[i] * bReal[i] + bImaginary[i] * aReal[i];
aReal[i] = real;
}
fft(aReal, aImaginary, true);
int[] result = new int[a.length + b.length - 1];
for (int i = 0; i < result.length; i++) result[i] = (int) Math.round(aReal[i]);
return result;
}
/**
* Find a primitive root.
*
* @param m A prime number.
* @return Primitive root.
*/
private static int primitiveRoot(final int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
final int[] divs = new int[20];
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long) i * i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
boolean ok = true;
for (int i = 0; i < cnt; i++) {
if (MathLib.pow(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
/**
* Ceil of power 2.
*
* @param n Value.
* @return Ceil of power 2.
*/
private static int ceilPow2(final int n) {
int x = 0;
while (1L << x < n) x++;
return x;
}
/**
* Garner's algorithm.
*
* @param c Mod convolution results.
* @param mods Mods.
* @return Result.
*/
private static long garner(final long[] c, final int[] mods) {
final int n = c.length + 1;
final long[] cnst = new long[n];
final long[] coef = new long[n];
java.util.Arrays.fill(coef, 1);
for (int i = 0; i < n - 1; i++) {
final int m1 = mods[i];
long v = (c[i] - cnst[i] + m1) % m1;
v = v * MathLib.pow(coef[i], m1 - 2, m1) % m1;
for (int j = i + 1; j < n; j++) {
final long m2 = mods[j];
cnst[j] = (cnst[j] + coef[j] * v) % m2;
coef[j] = coef[j] * m1 % m2;
}
}
return cnst[n - 1];
}
/**
* Garner's algorithm.
*
* @param c Mod convolution results.
* @param mods Mods.
* @return Result.
*/
private static int garner(int c0, int c1, int c2, final MathLib.Barrett[] mods) {
final long[] cnst = new long[4];
final long[] coef = new long[4];
java.util.Arrays.fill(coef, 1);
MathLib.Barrett m1 = mods[0];
long v = m1.reduce(c0 - cnst[0] + m1.mod);
v = m1.reduce(v * MathLib.pow(coef[0], m1.mod - 2, m1));
{
MathLib.Barrett m2 = mods[1];
cnst[1] = m2.reduce(cnst[1] + coef[1] * v);
coef[1] = m2.reduce(coef[1] * m1.mod);
m2 = mods[2];
cnst[2] = m2.reduce(cnst[2] + coef[2] * v);
coef[2] = m2.reduce(coef[2] * m1.mod);
m2 = mods[3];
cnst[3] = m2.reduce(cnst[3] + coef[3] * v);
coef[3] = m2.reduce(coef[3] * m1.mod);
}
m1 = mods[1];
v = m1.reduce(c1 - cnst[1] + m1.mod);
v = m1.reduce(v * MathLib.pow(coef[1], m1.mod - 2, m1));
{
MathLib.Barrett m2 = mods[2];
cnst[2] = m2.reduce(cnst[2] + coef[2] * v);
coef[2] = m2.reduce(coef[2] * m1.mod);
m2 = mods[3];
cnst[3] = m2.reduce(cnst[3] + coef[3] * v);
coef[3] = m2.reduce(coef[3] * m1.mod);
}
m1 = mods[2];
v = m1.reduce(c2 - cnst[2] + m1.mod);
v = m1.reduce(v * MathLib.pow(coef[2], m1.mod - 2, m1));
{
MathLib.Barrett m2 = mods[3];
cnst[3] = m2.reduce(cnst[3] + coef[3] * v);
coef[3] = m2.reduce(coef[3] * m1.mod);
}
return (int) cnst[3];
}
/**
* Garner's algorithm.
*
* @param c Mod convolution results.
* @param mods Mods.
* @return Result.
*/
private static int garner1_000_000_007(int c0, int c1, int c2) {
final long[] cnst = new long[4];
final long[] coef = new long[4];
java.util.Arrays.fill(coef, 1);
long v = (c0 - cnst[0] + 754_974_721) % 754_974_721;
v = v * MathLib.pow754_974_721(coef[0], 754_974_721 - 2) % 754_974_721;
{
cnst[1] = (cnst[1] + coef[1] * v) % 167_772_161;
coef[1] = coef[1] * 754_974_721 % 167_772_161;
cnst[2] = (cnst[2] + coef[2] * v) % 469_762_049;
coef[2] = coef[2] * 754_974_721 % 469_762_049;
cnst[3] = (cnst[3] + coef[3] * v) % 1_000_000_007;
coef[3] = coef[3] * 754_974_721 % 1_000_000_007;
}
v = (c1 - cnst[1] + 167_772_161) % 167_772_161;
v = v * MathLib.pow167_772_161(coef[1], 167_772_161 - 2) % 167_772_161;
{
cnst[2] = (cnst[2] + coef[2] * v) % 469_762_049;
coef[2] = coef[2] * 167_772_161 % 469_762_049;
cnst[3] = (cnst[3] + coef[3] * v) % 1_000_000_007;
coef[3] = coef[3] * 167_772_161 % 1_000_000_007;
}
v = (c2 - cnst[2] + 469_762_049) % 469_762_049;
v = v * MathLib.pow469_762_049(coef[2], 469_762_049 - 2) % 469_762_049;
{
cnst[3] = (cnst[3] + coef[3] * v) % 1_000_000_007;
coef[3] = coef[3] * 469_762_049 % 1_000_000_007;
}
return (int) cnst[3];
}
/**
* Pre-calculation for NTT.
*
* @param mod NTT Prime.
* @param g Primitive root of mod.
* @return Pre-calculation table.
*/
private static long[] sumE(final int mod, final int g) {
final long[] sum_e = new long[30];
final long[] es = new long[30];
final long[] ies = new long[30];
final int cnt2 = Integer.numberOfTrailingZeros(mod - 1);
long e = MathLib.pow(g, mod - 1 >> cnt2, mod);
long ie = MathLib.pow(e, mod - 2, mod);
for (int i = cnt2; i >= 2; i--) {
es[i - 2] = e;
ies[i - 2] = ie;
e = e * e % mod;
ie = ie * ie % mod;
}
long now = 1;
for (int i = 0; i < cnt2 - 2; i++) {
sum_e[i] = es[i] * now % mod;
now = now * ies[i] % mod;
}
return sum_e;
}
/**
* Pre-calculation for inverse NTT.
*
* @param mod Mod.
* @param g Primitive root of mod.
* @return Pre-calculation table.
*/
private static long[] sumIE(final int mod, final int g) {
final long[] sum_ie = new long[30];
final long[] es = new long[30];
final long[] ies = new long[30];
final int cnt2 = Integer.numberOfTrailingZeros(mod - 1);
long e = MathLib.pow(g, mod - 1 >> cnt2, mod);
long ie = MathLib.pow(e, mod - 2, mod);
for (int i = cnt2; i >= 2; i--) {
es[i - 2] = e;
ies[i - 2] = ie;
e = e * e % mod;
ie = ie * ie % mod;
}
long now = 1;
for (int i = 0; i < cnt2 - 2; i++) {
sum_ie[i] = ies[i] * now % mod;
now = now * es[i] % mod;
}
return sum_ie;
}
/**
* Inverse NTT.
*
* @param a Target array.
* @param sumIE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterflyInv(final long[] a, final long[] sumIE, final int mod) {
final int n = a.length;
final int h = ceilPow2(n);
for (int ph = h; ph >= 1; ph--) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long inow = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p];
a[i + offset] = (l + r) % mod;
a[i + offset + p] = (mod + l - r) * inow % mod;
}
final int x = Integer.numberOfTrailingZeros(~s);
inow = inow * sumIE[x] % mod;
}
}
}
/**
* Inverse NTT.
*
* @param a Target array.
* @param sumE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterfly(final long[] a, final long[] sumE, final int mod) {
final int n = a.length;
final int h = ceilPow2(n);
for (int ph = 1; ph <= h; ph++) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long now = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p] * now % mod;
a[i + offset] = (l + r) % mod;
a[i + offset + p] = (l - r + mod) % mod;
}
final int x = Integer.numberOfTrailingZeros(~s);
now = now * sumE[x] % mod;
}
}
}
/**
* Inverse NTT used mod 998_244_353.
*
* @param a Target array.
* @param sumIE Pre-calculation table.
*/
private static void butterflyInv998_244_353(final int[] a, final int[] sumIE) {
final int n = a.length;
final int h = ceilPow2(n);
for (int ph = h; ph >= 1; ph--) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long inow = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p];
a[i + offset] = (int)((l + r) % 998_244_353);
a[i + offset + p] = (int)((998_244_353 + l - r) * inow % 998_244_353);
}
final int x = Integer.numberOfTrailingZeros(~s);
inow = inow * sumIE[x] % 998_244_353;
}
}
}
/**
* Inverse NTT used mod 754_974_721.
*
* @param a Target array.
* @param sumIE Pre-calculation table.
*/
private static void butterflyInv754_974_721(final int[] a, final int[] sumIE) {
final int n = a.length;
final int h = ceilPow2(n);
for (int ph = h; ph >= 1; ph--) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long inow = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p];
a[i + offset] = (int)((l + r) % 754_974_721);
a[i + offset + p] = (int)((754_974_721 + l - r) * inow % 754_974_721);
}
final int x = Integer.numberOfTrailingZeros(~s);
inow = inow * sumIE[x] % 754_974_721;
}
}
}
/**
* Inverse NTT used mod 167_772_161.
*
* @param a Target array.
* @param sumIE Pre-calculation table.
*/
private static void butterflyInv167_772_161(final int[] a, final int[] sumIE) {
final int n = a.length;
final int h = ceilPow2(n);
for (int ph = h; ph >= 1; ph--) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long inow = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p];
a[i + offset] = (int)((l + r) % 167_772_161);
a[i + offset + p] = (int)((167_772_161 + l - r) * inow % 167_772_161);
}
final int x = Integer.numberOfTrailingZeros(~s);
inow = inow * sumIE[x] % 167_772_161;
}
}
}
/**
* Inverse NTT used mod 469_762_049.
*
* @param a Target array.
* @param sumIE Pre-calculation table.
*/
private static void butterflyInv469_762_049(final int[] a, final int[] sumIE) {
final int n = a.length;
final int h = ceilPow2(n);
for (int ph = h; ph >= 1; ph--) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long inow = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p];
a[i + offset] = (int)((l + r) % 469_762_049);
a[i + offset + p] = (int)((469_762_049 + l - r) * inow % 469_762_049);
}
final int x = Integer.numberOfTrailingZeros(~s);
inow = inow * sumIE[x] % 469_762_049;
}
}
}
/**
* Inverse NTT.
*
* @param a Target array.
* @param sumIE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterflyInv(final int[] a, final int[] sumIE, final MathLib.Barrett mod) {
final int n = a.length;
final int h = ceilPow2(n);
for (int ph = h; ph >= 1; ph--) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long inow = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p];
long sum = l + r;
if (sum >= mod.mod) sum -= mod.mod;
a[i + offset] = (int)sum;
a[i + offset + p] = mod.reduce((mod.mod + l - r) * inow);
}
final int x = Integer.numberOfTrailingZeros(~s);
inow = mod.reduce(inow * sumIE[x]);
}
}
}
/**
* Inverse NTT used mod 998_244_353.
*
* @param a Target array.
* @param sumE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterfly998_244_353(final int[] a, final int[] sumE) {
final int n = a.length;
final int h = ceilPow2(n);
final long ADD = (long)(998_244_353 - 2) * 998_244_353;
for (int ph = 1; ph <= h; ph++) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long now = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p] * now;
a[i + offset] = (int)((l + r) % 998_244_353);
a[i + offset + p] = (int)((l - r + ADD) % 998_244_353);
}
final int x = Integer.numberOfTrailingZeros(~s);
now = now * sumE[x] % 998_244_353;
}
}
}
/**
* Inverse NTT used mod 754_974_721.
*
* @param a Target array.
* @param sumE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterfly754_974_721(final int[] a, final int[] sumE) {
final int n = a.length;
final int h = ceilPow2(n);
final long ADD = (long)(754_974_721 - 2) * 754_974_721;
for (int ph = 1; ph <= h; ph++) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long now = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p] * now;
a[i + offset] = (int)((l + r) % 754_974_721);
a[i + offset + p] = (int)((l - r + ADD) % 754_974_721);
}
final int x = Integer.numberOfTrailingZeros(~s);
now = now * sumE[x] % 754_974_721;
}
}
}
/**
* Inverse NTT used mod 167_772_161.
*
* @param a Target array.
* @param sumE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterfly167_772_161(final int[] a, final int[] sumE) {
final int n = a.length;
final int h = ceilPow2(n);
final long ADD = (long)(167_772_161 - 2) * 167_772_161;
for (int ph = 1; ph <= h; ph++) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long now = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p] * now;
a[i + offset] = (int)((l + r) % 167_772_161);
a[i + offset + p] = (int)((l - r + ADD) % 167_772_161);
}
final int x = Integer.numberOfTrailingZeros(~s);
now = now * sumE[x] % 167_772_161;
}
}
}
/**
* Inverse NTT used mod 469_762_049.
*
* @param a Target array.
* @param sumE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterfly469_762_049(final int[] a, final int[] sumE) {
final int n = a.length;
final int h = ceilPow2(n);
final long ADD = (long)(469_762_049 - 2) * 469_762_049;
for (int ph = 1; ph <= h; ph++) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long now = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p] * now;
a[i + offset] = (int)((l + r) % 469_762_049);
a[i + offset + p] = (int)((l - r + ADD) % 469_762_049);
}
final int x = Integer.numberOfTrailingZeros(~s);
now = now * sumE[x] % 469_762_049;
}
}
}
/**
* Inverse NTT.
*
* @param a Target array.
* @param sumE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterfly(final int[] a, final int[] sumE, final MathLib.Barrett mod) {
final int n = a.length;
final int h = ceilPow2(n);
final long ADD = (long)(mod.mod - 2) * mod.mod;
for (int ph = 1; ph <= h; ph++) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long now = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p] * now;
a[i + offset] = mod.reduce(l + r);
a[i + offset + p] = mod.reduce(l - r + ADD);
}
final int x = Integer.numberOfTrailingZeros(~s);
now = mod.reduce(now * sumE[x]);
}
}
}
/**
* Convolution used mod 998_244_353.
*
* @param a Target array 1.
* @param b Target array 2.
* @return Answer.
*/
public static int[] convolution998_244_353(int[] a, int[] b) {
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new int[0];
final int z = 1 << ceilPow2(n + m - 1);
{
final int[] na = new int[z];
final int[] nb = new int[z];
System.arraycopy(a, 0, na, 0, n);
System.arraycopy(b, 0, nb, 0, m);
a = na;
b = nb;
}
final int g = primitiveRoot(998_244_353);
final int[] sume;
{
long[] s = sumE(998_244_353, g);
sume = new int[s.length];
for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
}
final int[] sumie;
{
long[] s = sumIE(998_244_353, g);
sumie = new int[s.length];
for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
}
butterfly998_244_353(a, sume);
butterfly998_244_353(b, sume);
for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 998_244_353);
butterflyInv998_244_353(a, sumie);
a = java.util.Arrays.copyOf(a, n + m - 1);
final long iz = MathLib.pow998_244_353(z, 998_244_353 - 2);
for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 998_244_353);
return a;
}
/**
* Convolution used mod 754_974_721.
*
* @param a Target array 1.
* @param b Target array 2.
* @return Answer.
*/
public static int[] convolution754_974_721(int[] a, int[] b) {
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new int[0];
final int z = 1 << ceilPow2(n + m - 1);
{
final int[] na = new int[z];
final int[] nb = new int[z];
System.arraycopy(a, 0, na, 0, n);
System.arraycopy(b, 0, nb, 0, m);
a = na;
b = nb;
}
final int g = primitiveRoot(754_974_721);
final int[] sume;
{
long[] s = sumE(754_974_721, g);
sume = new int[s.length];
for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
}
final int[] sumie;
{
long[] s = sumIE(754_974_721, g);
sumie = new int[s.length];
for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
}
butterfly754_974_721(a, sume);
butterfly754_974_721(b, sume);
for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 754_974_721);
butterflyInv754_974_721(a, sumie);
a = java.util.Arrays.copyOf(a, n + m - 1);
final long iz = MathLib.pow754_974_721(z, 754_974_721 - 2);
for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 754_974_721);
return a;
}
/**
* Convolution used mod 167_772_161.
*
* @param a Target array 1.
* @param b Target array 2.
* @return Answer.
*/
public static int[] convolution167_772_161(int[] a, int[] b) {
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new int[0];
final int z = 1 << ceilPow2(n + m - 1);
{
final int[] na = new int[z];
final int[] nb = new int[z];
System.arraycopy(a, 0, na, 0, n);
System.arraycopy(b, 0, nb, 0, m);
a = na;
b = nb;
}
final int g = primitiveRoot(167_772_161);
final int[] sume;
{
long[] s = sumE(167_772_161, g);
sume = new int[s.length];
for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
}
final int[] sumie;
{
long[] s = sumIE(167_772_161, g);
sumie = new int[s.length];
for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
}
butterfly167_772_161(a, sume);
butterfly167_772_161(b, sume);
for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 167_772_161);
butterflyInv167_772_161(a, sumie);
a = java.util.Arrays.copyOf(a, n + m - 1);
final long iz = MathLib.pow167_772_161(z, 167_772_161 - 2);
for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 167_772_161);
return a;
}
/**
* Convolution used mod 469_762_049.
*
* @param a Target array 1.
* @param b Target array 2.
* @return Answer.
*/
public static int[] convolution469_762_049(int[] a, int[] b) {
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new int[0];
final int z = 1 << ceilPow2(n + m - 1);
{
final int[] na = new int[z];
final int[] nb = new int[z];
System.arraycopy(a, 0, na, 0, n);
System.arraycopy(b, 0, nb, 0, m);
a = na;
b = nb;
}
final int g = primitiveRoot(469_762_049);
final int[] sume;
{
long[] s = sumE(469_762_049, g);
sume = new int[s.length];
for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
}
final int[] sumie;
{
long[] s = sumIE(469_762_049, g);
sumie = new int[s.length];
for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
}
butterfly469_762_049(a, sume);
butterfly469_762_049(b, sume);
for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 469_762_049);
butterflyInv469_762_049(a, sumie);
a = java.util.Arrays.copyOf(a, n + m - 1);
final long iz = MathLib.pow469_762_049(z, 469_762_049 - 2);
for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 469_762_049);
return a;
}
/**
* Convolution.
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod NTT Prime.
* @return Answer.
*/
public static int[] convolution(int[] a, int[] b, final int mod) {
MathLib.Barrett barrett = new MathLib.Barrett(mod);
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new int[0];
final int z = 1 << ceilPow2(n + m - 1);
{
final int[] na = new int[z];
final int[] nb = new int[z];
System.arraycopy(a, 0, na, 0, n);
System.arraycopy(b, 0, nb, 0, m);
a = na;
b = nb;
}
final int g = primitiveRoot(mod);
final int[] sume;
{
long[] s = sumE(mod, g);
sume = new int[s.length];
for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
}
final int[] sumie;
{
long[] s = sumIE(mod, g);
sumie = new int[s.length];
for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
}
butterfly(a, sume, barrett);
butterfly(b, sume, barrett);
for (int i = 0; i < z; i++) a[i] = barrett.reduce((long) a[i] * b[i]);
butterflyInv(a, sumie, barrett);
a = java.util.Arrays.copyOf(a, n + m - 1);
final long iz = MathLib.pow(z, mod - 2, mod);
for (int i = 0; i < n + m - 1; i++) a[i] = barrett.reduce(a[i] * iz);
return a;
}
/**
* Convolution.
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod NTT Prime.
* @return Answer.
*/
public static long[] convolution(long[] a, long[] b, final int mod) {
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new long[0];
final int z = 1 << ceilPow2(n + m - 1);
{
final long[] na = new long[z];
final long[] nb = new long[z];
System.arraycopy(a, 0, na, 0, n);
System.arraycopy(b, 0, nb, 0, m);
a = na;
b = nb;
}
final int g = primitiveRoot(mod);
final long[] sume = sumE(mod, g);
final long[] sumie = sumIE(mod, g);
butterfly(a, sume, mod);
butterfly(b, sume, mod);
for (int i = 0; i < z; i++) {
a[i] = a[i] * b[i] % mod;
}
butterflyInv(a, sumie, mod);
a = java.util.Arrays.copyOf(a, n + m - 1);
final long iz = MathLib.pow(z, mod - 2, mod);
for (int i = 0; i < n + m - 1; i++) a[i] = a[i] * iz % mod;
return a;
}
/**
* Convolution.
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod Any mod.
* @return Answer.
*/
public static long[] convolutionLL(final long[] a, final long[] b, final int mod) {
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new long[0];
final int mod1 = 754_974_721;
final int mod2 = 167_772_161;
final int mod3 = 469_762_049;
final long[] c1 = convolution(a, b, mod1);
final long[] c2 = convolution(a, b, mod2);
final long[] c3 = convolution(a, b, mod3);
final int retSize = c1.length;
final long[] ret = new long[retSize];
final int[] mods = { mod1, mod2, mod3, mod };
for (int i = 0; i < retSize; ++i) {
ret[i] = garner(new long[] { c1[i], c2[i], c3[i] }, mods);
}
return ret;
}
/**
* Convolution.
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod Any mod.
* @return Answer.
*/
public static int[] convolutionLL(final int[] a, final int[] b, final int mod) {
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new int[0];
final int mod1 = 754_974_721;
final int mod2 = 167_772_161;
final int mod3 = 469_762_049;
final int[] c1 = convolution754_974_721(a, b);
final int[] c2 = convolution167_772_161(a, b);
final int[] c3 = convolution469_762_049(a, b);
final int retSize = c1.length;
final int[] ret = new int[retSize];
final MathLib.Barrett[] mods = { new MathLib.Barrett(mod1), new MathLib.Barrett(mod2),
new MathLib.Barrett(mod3), new MathLib.Barrett(mod) };
for (int i = 0; i < retSize; ++i) ret[i] = garner(c1[i], c2[i], c3[i], mods);
return ret;
}
/**
* Convolution used mod 1_000_000_007.
*
* @param a Target array 1.
* @param b Target array 2.
* @return Answer.
*/
public static int[] convolution1_000_000_007(final int[] a, final int[] b) {
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new int[0];
final int[] c1 = convolution754_974_721(a, b);
final int[] c2 = convolution167_772_161(a, b);
final int[] c3 = convolution469_762_049(a, b);
final int retSize = c1.length;
final int[] ret = new int[retSize];
for (int i = 0; i < retSize; ++i) ret[i] = garner1_000_000_007(c1[i], c2[i], c3[i]);
return ret;
}
/**
* Convolution. need: length < 2000
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod Any mod.
* @return Answer.
*/
public static int[] convolutionLL2(final int[] a, final int[] b, final int mod) {
if (Math.max(a.length, b.length) < 4000) {
long[] la = new long[a.length], ha = new long[a.length], ma = new long[a.length], lb = new long[b.length],
hb = new long[b.length], mb = new long[b.length];
MathLib.Barrett barrett = new MathLib.Barrett(mod);
for (int i = 0; i < a.length; ++i) {
ha[i] = a[i] >> 15;
la[i] = a[i] & 0x7FFF;
ma[i] = la[i] + ha[i];
}
for (int i = 0; i < b.length; ++i) {
hb[i] = b[i] >> 15;
lb[i] = b[i] & 0x7FFF;
mb[i] = lb[i] + hb[i];
}
long[] l = convolution(la, lb), h = convolution(ha, hb), m = convolution(ma, mb);
int[] ret = new int[m.length];
for (int i = 0; i < m.length; ++i) {
h[i] = barrett.reduce(h[i]);
m[i] = barrett.reduce(m[i] - l[i] - h[i] + (long)m.length * mod);
ret[i] = barrett.reduce((h[i] << 30) + (m[i] << 15) + l[i]);
}
return ret;
}
return convolutionLL(a, b, mod);
}
/**
* Naive convolution. (Complexity is O(N^2)!!)
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod Mod.
* @return Answer.
*/
public static long[] convolutionNaive(final long[] a, final long[] b, final int mod) {
final int n = a.length;
final int m = b.length;
final int k = n + m - 1;
final long[] ret = new long[k];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ret[i + j] += a[i] * b[j] % mod;
ret[i + j] %= mod;
}
}
return ret;
}
}
}