competitive-programming-java-library
This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub shun0923/competitive-programming-java-library
library/Fps.java
- View this file on GitHub
- Last update: 2023-03-23 19:06:36+09:00
Depends on
library/FastIO.java
Required by
Verified with
- library/Fps_addComposite_test.java
- library/Fps_composite_test.java
- library/Fps_divfloor_mod_test.java
- library/Fps_exp_test.java
- library/Fps_inv_test.java
- library/Fps_log_test.java
- library/Fps_mul_test.java
- library/Fps_pow_test.java
- library/Fps_random_test.java
- library/Fps_sqrt_test.java
Code
package library;
import java.util.*;
import java.util.function.*;
import library.FastIO;
import library.Mod;
import library.Convolution;
class CnvFpsOperator extends FpsOperator { // M(N)=NlogN
Convolution cnv;
static final int NAIVE_INV_THRESHOLD = 256;
static final int NAIVE_EXP_THRESHOLD = 160;
static final int NAIVE_SQRT_THRESHOLD = 100;
CnvFpsOperator(Convolution cnv) { super(cnv.md); this.cnv = cnv; }
// O(M(L))
public final Fps butterfly(final Fps f) { return butterfly(f, f.a.length); }
public final Fps butterfly(final Fps f, int l) { return butterflyEquals(resize(f, l)); }
public final Fps butterflyEquals(final Fps f) { cnv.butterfly(f.a); return f; }
public final Fps butterflyInv(final Fps f) { return butterflyInv(f, f.a.length); }
public final Fps butterflyInv(final Fps f, int l) { return butterflyInvEquals(resize(f, l)); }
public final Fps butterflyInvEquals(final Fps f) { cnv.butterflyInv(f.a); return f; }
public final Fps doubling(final Fps f) { return doubling(f, f.a.length); }
public final Fps doubling(final Fps f, int l) { return doublingEquals(resize(f, l)); }
public final Fps doublingEquals(final Fps f) { cnv.doubling(f.a); return f; }
// O(M(L))
public final Fps mul(final Fps f, final Fps g, final int l) { return new Fps(this, cnv.cnv(f.a, g.a, l)); }
public final Fps inv(Fps f, final int l) {
if(l <= NAIVE_INV_THRESHOLD) return naiveInv(f, l);
if(f.get(0) == 0) return null;
if(l == 0) return zero(0);
f = shrink(f, l);
int m = 1;
Fps g = zero(l);
g.a[0] = md.inv(f.a[0]);
long inv4 = md.inv(4);
long div = md.mod(-1);
while(m < l) {
m <<= 1;
Fps f1 = butterfly(f, m);
Fps g1 = butterfly(g, m);
mulElemwiseEquals(f1, g1);
butterflyInvEquals(f1);
m >>= 1;
rshiftEquals(f1, m);
butterflyEquals(f1);
mulElemwiseEquals(f1, g1);
butterflyInvEquals(f1);
div = md.mul(div, inv4);
f1 = resize(f1, Math.min(l - m, m));
mulEquals(f1, div);
System.arraycopy(f1.a, 0, g.a, m, f1.a.length);
m <<= 1;
}
return g;
}
public final Fps div(final Fps f, final Fps g, final int l) {
Fps h = inv(g, l);
return h == null ? null : mul(f, h, l);
}
protected final Fps calPow(final Fps f, final long n, final int l) {
return mulEquals(expEquals(mulEquals(log(div(f, f.a[0]), l), n)), md.pow(f.a[0], n));
}
public final Fps exp(Fps f, final int l) {
if(l <= NAIVE_EXP_THRESHOLD) return naiveExp(f, l);
if(l == 0) return zero(0);
if(f.get(0) != 0) return null;
f = shrink(f, l);
int size = 1;
Fps h = one(l);
Fps diff = diff(f);
Fps inv = one(l << 1);
Fps btfInv = zero(0);
long inv4 = md.inv(4);
long invLen2 = md.mod(-1);
long inv2 = md.inv(2);
long invLen = 1;
while(size < l) {
Fps btf = resize(h, size << 1);
butterflyEquals(btf);
if(size > 1) {
Fps g = mulElemwise(btf, btfInv, size);
butterflyInvEquals(g);
size >>= 1;
rshiftEquals(g, size);
butterflyEquals(g);
mulElemwiseEquals(g, btfInv);
butterflyInvEquals(g);
invLen2 = md.mul(invLen2, inv4);
mulEquals(g, invLen2);
System.arraycopy(g.a, 0, inv.a, size, size);
size <<= 1;
}
Fps t = diff(h, size);
{
Fps r = resize(diff, size);
r.a[size - 1] = 0;
butterflyEquals(r);
mulElemwiseEquals(r, btf);
butterflyInvEquals(r);
mulEquals(r, - invLen);
addEquals(r, t);
t = lshift(r, 1, size);
t.a[0] = r.a[size - 1];
}
size <<= 1;
t = butterfly(resize(t, size));
btfInv = butterfly(resize(inv, size));
mulElemwiseEquals(t, btfInv);
butterflyInvEquals(t);
size >>= 1;
invLen = md.mul(invLen, inv2);
mulEquals(t, invLen);
t = rshift(integ(lshift(resize(t, size), size - 1)), size);
Fps v = zero(size << 1);
if(size < f.a.length) System.arraycopy(f.a, size, v.a, 0, Math.min(f.a.length - size, size));
subEquals(v, t);
butterflyEquals(v);
mulElemwiseEquals(v, btf);
butterflyInvEquals(v);
v = resize(v, Math.min(size, l - size));
mulEquals(v, invLen);
System.arraycopy(v.a, 0, h.a, size, v.a.length);
size <<= 1;
}
return h;
}
protected final Fps calSqrt(Fps f, final int l) {
if(l <= NAIVE_SQRT_THRESHOLD) return calNaiveSqrt(f, l);
long sqrt = md.sqrt(f.a[0]);
if(sqrt == -1) return null;
f = shrink(f, l);
int size = 1;
Fps h = constant(sqrt, l);
Fps inv = constant(md.inv(sqrt), l << 1);
Fps btfInv = zero(0);
long inv4 = md.inv(4);
long invLen2 = md.mod(-1);
long inv2 = md.inv(2);
long invLen = inv2;
while(size < l) {
Fps btf = resize(h, size << 1);
butterflyEquals(btf);
if(size > 1) {
Fps g = mulElemwise(btf, btfInv);
butterflyInvEquals(g);
size >>= 1;
rshiftEquals(g, size);
butterflyEquals(g);
mulElemwiseEquals(g, btfInv);
butterflyInvEquals(g);
invLen2 = md.mul(invLen2, inv4);
mulEquals(g, invLen2);
System.arraycopy(g.a, 0, inv.a, size, size);
size <<= 1;
}
Fps t = mulElemwise(btf, btf);
butterflyInvEquals(t);
mulEquals(t, - invLen);
rshiftEquals(t, size);
for(int i = 0, m = Math.min(size, f.a.length - size); i < m; i ++) addEquals(t, i, f.a[i + size]);
butterflyEquals(t);
btfInv = butterfly(resize(inv, size << 1));
mulElemwiseEquals(t, btfInv);
butterflyInvEquals(t);
t = resize(t, Math.min(size, l - size));
invLen = md.mul(invLen, inv2);
mulEquals(t, invLen);
System.arraycopy(t.a, 0, h.a, size, t.a.length);
size <<= 1;
}
return h;
}
}
class NaiveFpsOperator extends FpsOperator { // M(N)=N^2
NaiveFpsOperator(Mod md) { super(md); }
// O(M(L))
public final Fps mul(final Fps f, final Fps g, final int l) { return naiveMul(f, g, l); }
public final Fps inv(final Fps f, final int l) { return naiveInv(f, l); }
public final Fps div(final Fps f, final Fps g, final int l) { return naiveDiv(f, g, l); }
protected final Fps calPow(final Fps f, final long n, final int l) { return calNaivePow(f, n, l); }
public final Fps exp(final Fps f, final int l) { return naiveExp(f, l); }
protected final Fps calSqrt(final Fps f, final int l) { return calNaiveSqrt(f, l); }
}
abstract class FpsOperator {
public final Mod md;
FpsOperator(Mod md) { this.md = md; }
// O(L)
public final Fps zero(final int l) { return new Fps(this, l); }
public final Fps one(final int l) { return setEquals(zero(l), 0, 1); }
public final Fps constant(final long c, final int l) { return setEquals(zero(l), 0, c); }
public final Fps sparse(final int d, final long c, final int l) { return addEquals(one(l), d, c); } // 1+cx^d
public final Fps combi(final int d, final long c, final int n, final int l) { // (1+cx^d)^k
if(l == 0) return zero(l);
if(n == 1) return one(l);
Fps f = zero(l);
long pow = 1;
long mul = md.pow(c, d);
for(int i = 0, j = 0; j < l; i ++, j += d) {
f.a[j] = md.mul(md.C(n, i), pow);
pow = md.mul(pow, mul);
}
return f;
}
public final long eval(final Fps f, final long x) {
long ans = 0;
long pow = 1;
for(int i = 0; i < f.a.length; i ++) {
ans = md.add(ans, md.mul(f.a[i], pow));
pow = md.mul(pow, x);
}
return ans;
}
public final Fps resize(final Fps f, final int l) { return new Fps(f, l); }
public final Fps resizeEquals(final Fps f, final int l) { f.a = resize(f, l).a; return f; }
public final Fps shrink(final Fps f) {
for(int i = f.a.length - 1; i >= 0; i --) if(f.a[i] != 0) return resize(f, i + 1);
return zero(0);
}
public final Fps shrink(final Fps f, final int l) { return shrink(l > f.a.length ? f : resize(f, l)); }
public final Fps lshift(final Fps f, final int k) { return lshift(f, k, Math.max(0, f.a.length + k)); }
public final Fps lshift(final Fps f, final int k, final int l) {
if(k < 0) return rshift(f, - k, l);
Fps g = zero(l);
if(l > k) System.arraycopy(f.a, 0, g.a, k, Math.min(f.a.length, l - k));
return g;
}
public final Fps lshiftEquals(final Fps f, final int k) { f.a = lshift(f, k, f.a.length).a; return f; }
public final Fps rshift(final Fps f, final int k) { return rshift(f, k, Math.max(0, f.a.length - k)); }
public final Fps rshift(final Fps f, final int k, final int l) {
if(k < 0) return lshift(f, - k, l);
Fps g = zero(l);
if(f.a.length > k) System.arraycopy(f.a, k, g.a, 0, Math.min(f.a.length - k, l));
return g;
}
public final Fps rshiftEquals(final Fps f, final int k) { f.a = rshift(f, k, f.a.length).a; return f; }
public final Fps reverse(final Fps f) { return reverseEquals(new Fps(f)); }
public final Fps reverseEquals(final Fps f) {
for(int i = 0, j = f.a.length - 1; i < j; i ++, j --) {
long tmp = f.a[i];
f.a[i] = f.a[j];
f.a[j] = tmp;
}
return f;
}
public final Fps negate(final Fps f) { return negate(f, f.a.length); }
public final Fps negate(final Fps f, final int l) { return negateEquals(resize(f, l)); }
public final Fps negateEquals(final Fps f) {
for(int i = 0; i < f.a.length; i ++) f.a[i] = md.mod(- f.a[i]);
return f;
}
public final Fps op(final Fps f, final int i, final LongUnaryOperator op) { return op(f, i, op, Math.max(f.a.length, i + 1)); }
public final Fps op(final Fps f, final int i, final LongUnaryOperator op, final int l) { return opEquals(resize(f, l), i, op); }
public final Fps opEquals(final Fps f, final int i, final LongUnaryOperator op) { f.a[i] = md.mod(op.applyAsLong(f.a[i])); return f; }
public final Fps set(final Fps f, final int i, final long x) { return set(f, i, x, Math.max(f.a.length, i + 1)); }
public final Fps set(final Fps f, final int i, final long x, final int l) { return setEquals(resize(f, l), i, x); }
public final Fps setEquals(final Fps f, final int i, final long x) { f.a[i] = md.mod(x); return f; }
public final Fps add(final Fps f, final int i, final long x) { return add(f, i, x, Math.max(f.a.length, i + 1)); }
public final Fps add(final Fps f, final int i, final long x, final int l) { return addEquals(resize(f, l), i, x); }
public final Fps addEquals(final Fps f, final int i, final long x) { f.a[i] = md.add(f.a[i], x); return f; }
public final Fps sub(final Fps f, final int i, final long x) { return sub(f, i, x, Math.max(f.a.length, i + 1)); }
public final Fps sub(final Fps f, final int i, final long x, final int l) { return subEquals(resize(f, l), i, x); }
public final Fps subEquals(final Fps f, final int i, final long x) { f.a[i] = md.sub(f.a[i], x); return f; }
public final Fps mul(final Fps f, final int i, final long x) { return mul(f, i, x, Math.max(f.a.length, i + 1)); }
public final Fps mul(final Fps f, final int i, final long x, final int l) { return mulEquals(resize(f, l), i, x); }
public final Fps mulEquals(final Fps f, final int i, final long x) { f.a[i] = md.mul(f.a[i], x); return f; }
public final Fps div(final Fps f, final int i, final long x) { return div(f, i, x, Math.max(f.a.length, i + 1)); }
public final Fps div(final Fps f, final int i, final long x, final int l) { return divEquals(resize(f, l), i, x); }
public final Fps divEquals(final Fps f, final int i, final long x) { f.a[i] = md.div(f.a[i], x); return f; }
public final Fps op(final Fps f, final LongUnaryOperator op) { return op(f, op, f.a.length); }
public final Fps op(final Fps f, final LongUnaryOperator op, final int l) { return opEquals(resize(f, l), op); }
public final Fps opEquals(final Fps f, final LongUnaryOperator op) { for(int i = 0; i < f.a.length; i ++) opEquals(f, i, op); return f; }
public final Fps mul(final Fps f, final long x) { return mul(f, x, f.a.length); }
public final Fps mul(final Fps f, final long x, final int l) { return mulEquals(resize(f, l), x); }
public final Fps mulEquals(final Fps f, final long x) { for(int i = 0; i < f.a.length; i ++) f.a[i] = md.mul(f.a[i], x); return f; }
public final Fps div(final Fps f, final long x) { return div(f, x, f.a.length); }
public final Fps div(final Fps f, final long x, final int l) { return divEquals(resize(f, l), x); }
public final Fps divEquals(final Fps f, final long x) { return mulEquals(f, md.inv(x)); }
public final Fps add(final Fps f, final Fps g) { return add(f, g, Math.max(f.a.length, g.a.length)); }
public final Fps add(final Fps f, final Fps g, final int l) { return addEquals(resize(f, l), g); }
public final Fps addEquals(final Fps f, final Fps g) {
for(int i = 0, l = Math.min(f.a.length, g.a.length); i < l; i ++) addEquals(f, i, g.a[i]);
return f;
}
public final Fps sub(final Fps f, final Fps g) { return sub(f, g, Math.max(f.a.length, g.a.length)); }
public final Fps sub(final Fps f, final Fps g, final int l) { return subEquals(resize(f, l), g); }
public final Fps subEquals(final Fps f, final Fps g) {
for(int i = 0, l = Math.min(f.a.length, g.a.length); i < l; i ++) subEquals(f, i, g.a[i]);
return f;
}
public final Fps mulElemwise(final Fps f, final Fps g) { return mulElemwise(f, g, Math.min(f.a.length, g.a.length)); }
public final Fps mulElemwise(final Fps f, final Fps g, final int l) { return mulElemwiseEquals(resize(f, l), g); }
public final Fps mulElemwiseEquals(final Fps f, final Fps g) {
for(int i = 0, l = Math.min(f.a.length, g.a.length); i < l; i ++) mulEquals(f, i, g.a[i]);
for(int i = g.a.length; i < f.a.length; i ++) f.a[i] = 0;
return f;
}
// O(M(L))
public final Fps mul(final Fps f, final Fps g) { return mul(f, g, Math.max(0, f.a.length + g.a.length - 1)); }
public abstract Fps mul(final Fps f, final Fps g, final int l);
public final Fps mulEquals(final Fps f, final Fps g) { f.a = mul(f, g, f.a.length).a; return f; }
public final Fps mulShrink(final Fps f, final Fps g, final int l) { return shrink(mul(f, g, Math.min(l, Math.max(0, f.a.length + g.a.length - 1)))); }
public final Fps inv(final Fps f) { return inv(f, f.a.length); }
public abstract Fps inv(final Fps f, final int l);
public final Fps invEquals(final Fps f) { f.a = inv(f, f.a.length).a; return f; }
public final Fps div(final Fps f, final Fps g) { return div(f, g, f.a.length); }
public abstract Fps div(final Fps f, final Fps g, final int l);
public final Fps divEquals(final Fps f, final Fps g) { f.a = div(f, g).a; return f; }
public final Fps divfloor(final Fps f, final Fps g) { return divfloor(f, g, Math.max(0, f.a.length - g.a.length + 1)); }
public final Fps divfloor(final Fps f, final Fps g, final int l) {
return resize(reverse(div(reverse(f), reverse(g), Math.max(0, f.a.length - g.a.length + 1))), l);
}
public final Fps divfloorEquals(final Fps f, final Fps g) { f.a = divfloor(f, g, f.a.length).a; return f; }
public final Fps mod(final Fps f, final Fps g) { return mod(f, g, Math.min(f.a.length, g.a.length - 1)); }
public final Fps mod(final Fps f, final Fps g, final int l) { return sub(f, mulShrink(divfloor(f, g), g, l), l); }
public final Fps modEquals(final Fps f, final Fps g) { f.a = mod(f, g, f.a.length).a; return f; }
public final Fps modShrink(final Fps f, final Fps g, final int l) { return shrink(mod(f, g, Math.min(l, Math.min(f.a.length, g.a.length - 1)))); }
public final Fps pow(final Fps f, final long k) { return pow(f, k, f.a.length); }
public final Fps pow(final Fps f, final long n, final int l) {
if(l == 0) return n < 0 ? null : zero(0);
if(n == 0) return one(l);
if(n == 1) return resize(f, l);
if(n == 2) return mul(f, f, l);
if(f.get(0) == 0) {
int i = f.lowest();
if(n < 0) return null;
if(n > (l - 1) / i) return zero(l);
return lshift(calPow(rshift(f, i), n, l - (int)n * i), (int)n * i);
}
if(n < 0) return invEquals(calPow(f, - n, l));
return calPow(f, n, l);
}
protected abstract Fps calPow(final Fps f, final long k, final int l);
public final Fps powEquals(final Fps f, final long k) { f.a = pow(f, k).a; return f; }
public final Fps powShrink(final Fps f, final long k, final int l) {
return f.a.length == 0 ? zero(0) : shrink(pow(f, k, k > (l - 1) / (f.a.length - 1) ? l : (f.a.length - 1) * (int) k + 1));
}
// O(M(L)logN)
public final Fps mul(final Fps[] fs, final int l) {
if(fs.length == 0) return one(l);
Deque<Fps> dq = new ArrayDeque<>();
for(Fps f : fs) dq.add(f);
while(dq.size() != 1) dq.addLast(mulShrink(dq.removeFirst(), dq.removeFirst(), l));
return resize(dq.removeFirst(), l);
}
// O(L^2)
public final Fps naiveMul(final Fps f, final Fps g) { return naiveMul(f, g, Math.max(0, f.a.length + g.a.length - 1)); }
public final Fps naiveMul(Fps f, Fps g, final int l) {
if(l == 0) return zero(0);
f = shrink(f, l);
g = shrink(g, l);
Fps h = zero(l);
for(int i = 0; i < l; i ++) {
long sum = 0;
for(int j = Math.max(0, i - g.a.length + 1), k = i - j, m = Math.min(f.a.length, i + 1); j < m; j ++, k --) {
sum = md.add(sum, md.mul(f.a[j], g.a[k]));
}
h.a[i] = sum;
}
return h;
}
public final Fps naiveMulEquals(final Fps f, final Fps g) { f.a = naiveMul(f, g, f.a.length).a; return f; }
public final Fps naiveMulShrink(final Fps f, final Fps g, final int l) { return shrink(naiveMul(f, g, Math.min(l, Math.max(0, f.a.length + g.a.length - 1)))); }
public final Fps naiveInv(final Fps f) { return naiveInv(f, f.a.length); }
public final Fps naiveInv(final Fps f, final int l) { return naiveDiv(one(1), f, l); }
public final Fps naiveInvEquals(final Fps f) { f.a = naiveInv(f).a; return f; }
public final Fps naiveDiv(final Fps f, final Fps g) { return naiveDiv(f, g, f.a.length); }
public final Fps naiveDiv(Fps f, Fps g, final int l) {
if(g.get(0) == 0) return null;
if(l == 0) return zero(0);
f = shrink(f, l);
g = shrink(g, l);
Fps h = resize(f, l);
long div = md.inv(g.a[0]);
for(int i = 0; i < l; i ++) {
long sum = 0;
for(int j = Math.max(0, i - g.a.length + 1), k = i - j; k > 0; j ++, k --) {
sum = md.add(sum, md.mul(h.a[j], g.a[k]));
}
h.a[i] = md.mul(md.sub(h.a[i], sum), div);
}
return h;
}
public final Fps naiveDivEquals(final Fps f, final Fps g) { f.a = naiveDiv(f, g).a; return f; }
public final Fps naivePow(final Fps f, final long n) { return naivePow(f, n, f.a.length); }
public final Fps naivePow(Fps f, long n, final int l) {
if(l == 0) return n < 0 ? null : zero(0);
if(n == 0) return one(l);
if(n == 1) return resize(f, l);
if(n == 2) return mul(f, f, l);
if(f.get(0) == 0) {
int i = f.lowest();
if(n < 0) return null;
if(n > (l - 1) / i) return zero(l);
return lshift(calNaivePow(rshift(f, i), n, l - (int)n * i), (int)n * i);
}
if(n < 0) return naiveInvEquals(calNaivePow(f, - n, l));
return calNaivePow(f, n, l);
}
protected final Fps calNaivePow(Fps f, long n, final int l) {
f = shrink(f, l);
long inv[] = md.invs(l);
long div = md.inv(f.a[0]);
for(int i = 0; i < l; i ++) inv[i] = md.mul(inv[i], div);
Fps g = constant(md.pow(f.a[0], n), l);
for(int i = 1; i < l; i ++) {
long sum = 0;
for(int j = 1, k = i - 1, m = Math.min(i, f.a.length - 1); j <= m; j ++, k --) {
sum = md.add(sum, md.mul(md.mul(n + 1, j) - i, f.a[j], g.a[k]));
}
g.a[i] = md.mul(sum, inv[i]);
}
return g;
}
public final Fps naivePowEquals(final Fps f, final long n) { f.a = naivePow(f, n).a; return f; }
// O(M(L)logN)
public final Fps binaryPow(final Fps f, final long n) { return binaryPow(f, n, f.a.length); }
public final Fps binaryPow(final Fps f, long n, final int l) {
if(l == 0) return n < 0 ? null : zero(0);
if(n == 0) return one(l);
if(n == 1) return resize(f, l);
if(n == 2) return mul(f, f, l);
if(f.get(0) == 0) {
int i = f.lowest();
if(n < 0) return null;
if(n > (l - 1) / i) return zero(l);
return lshift(binaryPow(rshift(f, i), n, l - (int)n * i), (int)n * i);
}
if(n < 0) return invEquals(binaryPow(f, - n, l));
Fps g = shrink(f, l);
Fps h = one(1);
while(true) {
if((n & 1) != 0) h = mulShrink(h, g, l);
n >>= 1;
if(n == 0) return resize(h, l);
g = mulShrink(g, g, l);
}
}
public final Fps binaryPowEquals(final Fps f, final long n) { f.a = binaryPow(f, n).a; return f; }
// O(L)
// f<-f*(1+cx^d)
public final Fps mulSparseEquals(final Fps f, final int d, long c) {
if(c == 1) for(int i = f.a.length - 1; i >= d; i --) addEquals(f, i, f.a[i - d]);
else if(c == -1) for(int i = f.a.length - 1; i >= d; i --) subEquals(f, i, f.a[i - d]);
else {
c = md.mod(c);
for(int i = f.a.length - 1; i >= d; i --) addEquals(f, i, md.mul(f.a[i - d], c));
}
return f;
}
// f<-f/(1+cx^d)
public final Fps divSparseEquals(final Fps f, final int d, long c) {
if(c == 1) for(int i = d; i < f.a.length; i ++) subEquals(f, i, f.a[i - d]);
else if(c == -1) for(int i = d; i < f.a.length; i ++) addEquals(f, i, f.a[i - d]);
else {
c = md.mod(c);
for(int i = d; i < f.a.length; i ++) subEquals(f, i, md.mul(f.a[i - d], c));
}
return f;
}
public final Fps diff(final Fps f) { return diff(f, Math.max(0, f.a.length - 1)); }
public final Fps diff(final Fps f, final int l) {
if(l == 0) return zero(0);
Fps g = zero(l);
for(int i = 1, m = Math.min(l + 1, f.a.length); i < m; i ++) g.a[i - 1] = md.mul(f.a[i], i);
return g;
}
public final Fps diffEquals(final Fps f) { f.a = diff(f, f.a.length).a; return f; }
public final Fps integ(final Fps f) { return integ(f, f.a.length + 1); }
public final Fps integ(final Fps f, final int l) {
if(l == 0) return zero(0);
Fps g = zero(l);
long inv[] = md.invs(Math.min(l - 1, f.a.length));
for(int i = 1; i < inv.length; i ++) g.a[i] = md.mul(f.a[i - 1], inv[i]);
return g;
}
public final Fps integEquals(final Fps f) { f.a = integ(f, f.a.length).a; return f; }
// O(M(L))
public final Fps log(final Fps f) { return log(f, f.a.length); }
public final Fps log(final Fps f, final int l) {
if(f.get(0) != 1) return null;
return integEquals(divEquals(diff(f, l), f));
}
public final Fps logEquals(final Fps f) { f.a = log(f).a; return f; }
public final Fps exp(final Fps f) { return exp(f, f.a.length); }
public abstract Fps exp(final Fps f, final int l);
public final Fps expEquals(final Fps f) { f.a = exp(f).a; return f; }
public final Fps sqrt(final Fps f) { return sqrt(f, f.a.length); }
public final Fps sqrt(final Fps f, final int l) {
if(l == 0) return zero(0);
if(f.get(0) == 0) {
int i = f.lowest();
if(i == f.a.length) return zero(l);
if((i & 1) != 0) return null;
i >>= 1;
if(i >= l) return zero(l);
Fps g = calSqrt(rshift(f, i << 1), l - i);
return g == null ? null : lshift(g, i);
}
return calSqrt(f, l);
}
protected abstract Fps calSqrt(final Fps f, final int l);
public final Fps sqrtEquals(final Fps f) { f.a = sqrt(f).a; return f; }
// O(L^2)
public final Fps naiveExp(final Fps f) { return naiveExp(f, f.a.length); }
public final Fps naiveExp(Fps f, final int l) {
if(l == 0) return zero(0);
if(f.get(0) != 0) return null;
long inv[] = md.invs(l);
f = shrink(f);
Fps g = one(l);
for(int i = 1; i < l; i ++) {
long sum = 0;
for(int j = 1, k = i - 1, m = Math.min(i, f.a.length - 1); j <= m; j ++, k --) {
sum = md.add(sum, md.mul(j, f.a[j], g.a[k]));
}
g.a[i] = md.mul(sum, inv[i]);
}
return g;
}
public final Fps naiveExpEquals(final Fps f) { f.a = naiveExp(f).a; return f; }
public final Fps naiveSqrt(final Fps f) { return naiveSqrt(f, f.a.length); }
public final Fps naiveSqrt(final Fps f, final int l) {
if(l == 0) return zero(0);
if(f.get(0) == 0) {
int i = f.lowest();
if(i == f.a.length) return zero(l);
if((i & 1) != 0) return null;
if(i << 1 >= l) return zero(l);
Fps g = calNaiveSqrt(rshift(f, i), l - (i >> 1));
return g == null ? null : lshift(g, i >> 1);
}
return calNaiveSqrt(f, l);
}
protected final Fps calNaiveSqrt(final Fps f, final int l) {
Fps g = resize(f, l);
long inv[] = md.invs(l);
long sqrt = md.sqrt(g.a[0]);
if(sqrt == -1) return null;
long div = md.inv(sqrt);
mulEquals(g, md.div(div, 2));
g.a[0] = sqrt;
for(int i = 0; i < l; i ++) inv[i] = md.mul(inv[i], div);
for(int i = 1; i < l; i ++) {
long sum = 0;
for(int j = 1, k = i - 1; j < i; j ++, k --) {
sum = md.add(sum, md.mul(j, g.a[j], g.a[k]));
}
subEquals(g, i, md.mul(sum, inv[i]));
}
return g;
}
public final Fps naiveSqrtEquals(final Fps f) { f.a = naiveSqrt(f).a; return f; }
// O(M(L))
// f <- 1/(1-f)=1+f+f^2+f^3+...=sum_{k=0}^inf f^k = 1/(1-f)
public final Fps geomSeries(final Fps f) { return geomSeries(f, f.a.length); }
public final Fps geomSeries(final Fps f, final int l) { return inv(add(negate(f), 0, 1), l); }
public final Fps geomSeriesEquals(final Fps f) { f.a = geomSeries(f).a; return f; }
// f <- (1-f^n)/(1-f)=1+f+f^2+...+f^(n-1)=sum_{k=0}^{n-1} f^k = (f^n-1)/(f-1)
public final Fps geomPartialSeries(final Fps f, final int n) { return geomPartialSeries(f, n, f.a.length); }
public final Fps geomPartialSeries(final Fps f, final int n, final int l) { return div(sub(powShrink(f, n, l), 0, 1), sub(f, 0, 1), l); }
public final Fps geomPartialSeriesEquals(final Fps f, final int n) { f.a = geomPartialSeries(f, n).a; return f; }
// f <- f/(1-x)=f+f*x+f*x^2+f*x^3+...=sum_{k=0}^inf f*x^k
Fps geomSeriesX(final Fps f) { return geomSeriesX(f, f.a.length); }
Fps geomSeriesX(final Fps f, final int l) { return divSparseEquals(resize(f, l), 1, -1); }
Fps geomSeriesXEquals(final Fps f) { f.a = geomSeriesX(f).a; return f; }
// f <- f*(1-x^n)/(1-x)=f+f*x+f*x^2+...+f*x^(n-1)=sum_{k=0}^{n-1} f*x^k
Fps geomPartialSeriesX(final Fps f, final int n) { return geomPartialSeriesX(f, n, f.a.length); }
Fps geomPartialSeriesX(final Fps f, final int n, final int l) { return mulSparseEquals(geomSeriesX(f, l), n, -1); }
Fps geomPartialSeriesXEquals(final Fps f, final int n) { f.a = geomPartialSeriesX(f, n).a; return f; }
//O(L^(1/2)M(L)+L^2)
// return f(g)
public final Fps composite(final Fps f, final Fps g) { return composite(f, g, f.a.length); }
public final Fps composite(Fps f, Fps g, final int l) {
if(l == 0) return zero(0);
f = shrink(f);
g = shrink(g);
if(f.a.length == 0) return zero(l);
if(g.a.length == 0) return constant(f.a[0], l);
if(l == 1 || g.a.length == 1) return constant(eval(f, g.a[0]), l);
int l2 = (int)Math.min(l, (long)(f.a.length - 1) * (g.a.length - 1) + 1);
int m = Math.max((int)Math.ceil(Math.sqrt(l2)), 2);
while(l2 > m * m) m ++;
Fps pow[] = new Fps[m + 1];
pow[0] = one(1);
for(int i = 1; i <= m; i ++) pow[i] = mulShrink(pow[i - 1], g, l);
Fps pow2[] = new Fps[m];
pow2[0] = one(1);
for(int i = 1; i < m; i ++) pow2[i] = mulShrink(pow2[i - 1], pow[m], l);
Fps fg[] = new Fps[m];
for(int i = 0; i < m; i ++) {
fg[i] = zero(l);
for(int j = 0; j < l; j ++) {
long sum = 0;
for(int k = 0, k2 = i * m, m2 = Math.min((i + 1) * m, f.a.length); k2 < m2; k ++, k2 ++) {
if(j < pow[k].a.length) sum = md.add(sum, md.mul(f.a[k2], pow[k].a[j]));
}
fg[i].a[j] = sum;
}
}
Fps h = zero(l);
for(int i = 0; i < m; i ++) addEquals(h, mulShrink(fg[i], pow2[i], l));
return h;
}
public final Fps compositeEquals(final Fps f, final Fps g) { f.a = composite(f, g).a; return f; }
// O(M(L))
// return f(x+c)
public final Fps addComposite(final Fps f, final long c) { return addComposite(f, c, f.a.length); }
public final Fps addComposite(final Fps f, final long c, final int l) {
if(l == 0) return zero(0);
Fps h = shrink(f, l);
if(h.a.length == 0) return zero(l);
long fact = 1;
for(int i = 0; i < h.a.length; i ++) { mulEquals(h, i, fact); fact = md.mul(fact, i + 1); }
reverseEquals(h);
long inv[] = md.invs(h.a.length);
Fps g = one(h.a.length);
for(int i = 1; i < g.a.length; i ++) g.a[i] = md.mul(g.a[i - 1], c, inv[i]);
reverseEquals(mulEquals(h, g));
long div = 1;
for(int i = 0; i < h.a.length; i ++) { mulEquals(h, i, div); div = md.mul(div, inv[i + 1]); }
return resize(h, l);
}
public final Fps addCompositeEquals(final Fps f, final long c) { f.a = addComposite(f, c).a; return f; }
// O(L)
// return f(cx)
public final Fps mulComposite(final Fps f, final long c) { return mulComposite(f, c, f.a.length); }
public final Fps mulComposite(final Fps f, final long c, final int l) { return mulCompositeEquals(resize(f, l), c); }
public final Fps mulCompositeEquals(final Fps f, final long c) {
long pow = 1;
for(int i = 0; i < f.a.length; i ++) { mulEquals(f, i, pow); pow = md.mul(pow, c); }
return f;
}
// O(L/d)
// return f(x^d)
public final Fps powComposite(final Fps f, final int d) { return powComposite(f, d, Math.max(0, f.a.length * d - d + 1)); }
public final Fps powComposite(final Fps f, final int d, final int l) {
FastIO.nonNegativeCheck(d);
if(l == 0) return zero(0);
if(d == 0) return constant(eval(f, 1), f.a.length);
Fps g = zero(l);
for(int i = 0, j = 0, m = Math.min(f.a.length, l / d + 1); i < m; i ++, j += d) g.a[j] = f.a[i];
return g;
}
public final Fps powCompositeEquals(final Fps f, final int d) { f.a = powComposite(f, d).a; return f; }
// O(L)
// return f(1+cx^d)
public final Fps sparseComposite(final Fps f, final int d, final long c) { return sparseComposite(f, d, c, Math.max(0, f.a.length * d - d + 1)); }
public final Fps sparseComposite(final Fps f, final int d, final long c, final int l) { return powCompositeEquals(mulCompositeEquals(addComposite(f, 1, l), c), d); }
public final Fps sparseCompositeEquals(final Fps f, final int d, final long c) { f.a = sparseComposite(f, d, c).a; return f; }
}
class Fps implements Comparable<Fps> {
private final FpsOperator op;
public long a[];
// O(L)
Fps(final FpsOperator op, final int l) { FastIO.nonNegativeCheck(l); this.op = op; a = new long[l]; }
Fps(final FpsOperator op, final int l, final long x) { this(op, l); Arrays.fill(a, op.md.mod(x)); }
Fps(final FpsOperator op, final long[] a, final int l) { this(op, l); System.arraycopy(a, 0, this.a, 0, Math.min(a.length, l)); }
Fps(final FpsOperator op, final long[] a) { this(op, a, a.length); }
Fps(final FpsOperator op, final Fps g, final int l) { this(op, g.a, l); }
Fps(final FpsOperator op, final Fps g) { this(op, g.a); }
Fps(final Fps g, final int l) { this(g.op, g.a, l); }
Fps(final Fps g) { this(g.op, g.a); }
// O(1)
public int size() { return a.length; }
public long[] get() { return a; }
public long get(final int i) { return i < a.length ? a[i] : 0; }
// O(L)
public int lowest() { for(int i = 0; i < a.length; i ++) if(a[i] != 0) return i; return a.length; }
@Override public String toString() { return Arrays.toString(a); }
@Override public int hashCode() { return Arrays.hashCode(a); }
@Override
public boolean equals(final Object obj) {
if(this == obj) return true;
if(obj == null) return false;
if(this.getClass() != obj.getClass()) return false;
Fps that = (Fps) obj;
if(!Arrays.equals(a, that.a)) return false;
return true;
}
@Override
public int compareTo(final Fps that) { return Integer.compare(a.length, that.a.length); }
// O(L)
public final Fps resize(final int l) { return op.resizeEquals(this, l); }
public final Fps lshift(final int k) { return op.lshiftEquals(this, k); }
public final Fps rshift(final int k) { return op.rshiftEquals(this, k); }
public final Fps reverse() { return op.reverseEquals(this); }
public final Fps negate() { return op.negateEquals(this); }
public final Fps op(final int i, final LongUnaryOperator operator) { return op.opEquals(this, i, operator); }
public final Fps set(final int i, final long x) { return op.setEquals(this, i, x); }
public final Fps add(final int i, final long x) { return op.addEquals(this, i, x); }
public final Fps sub(final int i, final long x) { return op.subEquals(this, i, x); }
public final Fps mul(final int i, final long x) { return op.mulEquals(this, i, x); }
public final Fps div(final int i, final long x) { return op.divEquals(this, i, x); }
public final Fps op(final LongUnaryOperator operator) { return op.opEquals(this, operator); }
public final Fps mul(final long x) { return op.mulEquals(this, x); }
public final Fps div(final long x) { return op.divEquals(this, x); }
public final Fps add(final Fps g) { return op.addEquals(this, g); }
public final Fps sub(final Fps g) { return op.subEquals(this, g); }
public final Fps mulElemwise(final Fps g) { return op.mulElemwiseEquals(this, g); }
// O(M(L))
public final Fps mul(final Fps g) { return op.mulEquals(this, g); }
public final Fps inv() { return op.invEquals(this); }
public final Fps div(final Fps g) { return op.divEquals(this, g); }
public final Fps divfloor(final Fps g) { return op.divfloorEquals(this, g); }
public final Fps mod(final Fps g) { return op.modEquals(this, g); }
public final Fps pow(final long n) { return op.powEquals(this, n); }
// O(L^2)
public final Fps naiveMul(final Fps g) { return op.naiveMulEquals(this, g); }
public final Fps naiveInv() { return op.naiveInvEquals(this); }
public final Fps naiveDiv(final Fps g) { return op.naiveDivEquals(this, g); }
public final Fps naivePow(final long n) { return op.naivePowEquals(this, n); }
// O(M(L)logN)
public final Fps binaryPow(final long n) { return op.binaryPowEquals(this, n); }
// O(L)
public final Fps mulSparse(final int d, final long c) { return op.mulSparseEquals(this, d, c); }
public final Fps divSparse(final int d, final long c) { return op.divSparseEquals(this, d, c); }
public final Fps diff() { return op.diffEquals(this); }
public final Fps integ() { return op.integEquals(this); }
// O(M(L))
public final Fps log() { return op.logEquals(this); }
public final Fps exp() { return op.expEquals(this); }
public final Fps sqrt() { return op.sqrtEquals(this); }
// O(L^2)
public final Fps naiveExp() { return op.naiveExpEquals(this); }
public final Fps naiveSqrt() { return op.naiveSqrtEquals(this); }
// O(M(L))
public final Fps geomSeries() { return op.geomSeriesEquals(this); }
public final Fps geomPartialSeries(final int n) { return op.geomPartialSeriesEquals(this, n); }
public final Fps geomSeriesX() { return op.geomSeriesXEquals(this); }
public final Fps geomPartialSeriesX(final int n) { return op.geomPartialSeriesXEquals(this, n); }
// O(L^(1/2)M(L)+L^2)
public final Fps composite(final Fps g) { return op.compositeEquals(this, g); }
// O(L)
public final Fps addComposite(final long c) { return op.addCompositeEquals(this, c); }
// O(L/d)
public final Fps mulComposite(final int d) { return op.mulCompositeEquals(this, d); }
// O(L)
public final Fps sparseComposite(final int d, final long c) { return op.sparseCompositeEquals(this, d, c); }
}Traceback (most recent call last):
File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/user_defined.py", line 71, in bundle
return subprocess.check_output(shlex.split(command))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/subprocess.py", line 466, in check_output
return run(*popenargs, stdout=PIPE, timeout=timeout, check=True,
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/subprocess.py", line 571, in run
raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['false']' returned non-zero exit status 1.