Expand description
mathematical datas
Modules§
- arbitrary_
mod_ 🔒binomial - array_
vec 🔒 - binomial_
prefix_ 🔒sum - bit_
matrix 🔒 - bitwise_
transform 🔒 - bitwiseand_
convolve 🔒 - bitwiseor_
convolve 🔒 - bitwisexor_
convolve 🔒 - black_
box_ 🔒matrix - black_
box_ 🔒mint_ matrix - convolve_
steps 🔒 - discrete_
logarithm 🔒 - factorial 🔒
- fast_
fourier_ 🔒transform - fast_
prime_ 🔒mod - floor_
sum 🔒 - formal_
power_ 🔒series - garner 🔒
- gcd 🔒
- gcd_
convolve 🔒 - lagrange_
interpolation 🔒 - lcm_
convolve 🔒 - linear_
congruence 🔒 - linear_
diophantine 🔒 - matrix 🔒
- miller_
rabin 🔒 - min_
plus_ 🔒convolution - Exact min-plus convolution algorithms for structured integer sequences.
- mint_
fft_ 🔒convolve - mint_
matrix 🔒 - mod_
sqrt 🔒 - number_
theoretic_ 🔒transform - polynomial 🔒
- pow_
prec 🔒 - prime 🔒
- prime_
factors 🔒 - prime_
list 🔒 - prime_
table 🔒 - primitive_
root 🔒 - quotient_
array 🔒 - relaxed_
convolution 🔒 - subset_
convolve 🔒
Structs§
- Arbitrary
ModBinomial - Array
Vec - Binomial
Polynomial Prefix Sum - Binomial
Prefix Sum - BitMatrix
- A matrix over GF(2), stored as packed rows.
- BitMatrix
Solution - Bitwiseand
Convolve - Bitwiseor
Convolve - Bitwisexor
Convolve EXACT_DIVISIONnormalizes with division instead of a multiplicative inverse.- Black
BoxMatrix Impl - Convolve
- Euler
PhiTable - Fast
Prime Mod - Fast online inverse and power queries for a prime modulus.
- Formal
Power Series - Garner
- Garner’s algorithm with precomputation for fixed moduli.
- GcdConvolve
- LcmConvolve
- Matrix
- Memorized
Factorial - Online
Subset Mobius Transform - Online
Subset Zeta Transform - Online
Superset Mobius Transform - Online
Superset Zeta Transform - Polynomial
- PowPrec
- Prime
List - Prime
Table - Quotient
Array - store with index ${\lfloor\frac{n}{i}\rfloor \mid i=1,2,\ldots,n}$
- Relaxed
Convolution - Sparse
Matrix - Subset
Convolve
Enums§
Traits§
- Black
BoxM IntMatrix - Black
BoxMatrix - Convolve
Steps - Formal
Power Series Coefficient - Formal
Power Series Coefficient Sqrt - MInt
Matrix - NttReuse
- ToArray
Vec - ToArray
VecScalar
Functions§
- bitwise_
transform - check_
primitive_ root - discrete_
logarithm - a^x ≡ b (mod n)
- discrete_
logarithm_ prime_ mod - divisors
- euler_
phi - extgcd
- extgcd_
binary - extgcd_
recurse - floor_
power_ sum - $$\sum_{i=0}^{n-1}x^iy^{\left\lfloor\frac{a\times i+b}{m}\right\rfloor}$$
- floor_
sum - Sum of Floor of Linear mod 2^64
- floor_
sum_ i64 - Sum of Floor of Linear mod 2^64
- floor_
sum_ polynomial - $$\sum_{i=0}^{n-1}i^X\left\lfloor\frac{a\times i+b}{m}\right\rfloor^Y$$
- floor_
sum_ polynomial_ i64 - $$\sum_{i=l}^{r-1}i^X\left\lfloor\frac{a\times i+b}{m}\right\rfloor^Y$$
- floor_
sum_ range_ freq - gcd
- binary gcd
- gcd_
loop - highly_
composite_ number - [(hcn, #divisor)]
- lagrange_
interpolation - lagrange_
interpolation_ polynomial - lcm
- miller_
rabin - miller_
rabin_ with_ br - min_
of_ mod_ of_ linear - $$\min({(a\times i+b)\bmod m\mid0\leq i<n}\cup{m})$$
- min_
plus_ convolution - Computes min-plus convolution after selecting a deterministic exact method from the observed input structure.
- min_
plus_ convolution_ bounded_ ntt - Computes exact min-plus convolution for small integer value spans using NTT.
- min_
plus_ convolution_ concave_ both - Computes convolution of two concave inputs from antidiagonal endpoints.
- min_
plus_ convolution_ concave_ envelope - Computes convolution when one finite input is concave using offline envelopes.
- min_
plus_ convolution_ convex_ divide_ and_ conquer - Computes convolution when one input is convex using monotone divide and conquer.
- min_
plus_ convolution_ convex_ merge - Computes convolution of two convex inputs by merging their slope sequences.
- min_
plus_ convolution_ convex_ smawk - Computes convolution when one input is convex using SMAWK in
O(n + m). - min_
plus_ convolution_ linear - Computes convolution when at least one input is finite and linear.
- min_
plus_ convolution_ monotone_ runs - Computes convolution of same-direction monotone inputs from equal-value runs.
- min_
plus_ convolution_ naive - Computes min-plus convolution by enumerating all input pairs.
- min_
plus_ convolution_ near_ convex_ scan - Computes exact near-convex convolution by scanning witness-relevant pairs.
- min_
plus_ convolution_ piecewise_ linear - Computes convolution using the input with fewer maximal linear pieces.
- min_
plus_ convolution_ sparse - Computes min-plus convolution by enumerating finite input pairs only.
- min_
plus_ convolution_ with_ squared_ distance - Computes min-plus convolution with squared distance in linear time.
- modinv
- modinv_
extgcd_ binary - 0 < a < p, gcd(a, p) == 1, p is prime > 2
- modinv_
recurse - moebius
- g(d) = Sigma mu(d) * f(n/d)
- prime_
factors - prime_
factors_ flatten - primitive_
root - solve_
linear_ congruence - return: (y,z)
- solve_
linear_ diophantine - Solve ax + by = c
- solve_
simultaneous_ linear_ congruence - return: (y,z)
- with_
prime_ list
Type Aliases§
- Convolve998244353
- Fps
- Fps998244353
- MInt
Convolve - Raw transforms require each integer coefficient reconstructed by CRT to be below
the product of the three NTT moduli.
convolvesplits products exceeding this bound. - U64Convolve
- Convolution modulo 2^64. Multiply only freshly transformed operands; reconstruct and transform again before multiplying another factor.