ntt
The ntt module.
Generated from spec/std/ntt.cp by cpl doc --format json.
Curved
pub enum Curved = Both | Right | NeitherWhich arguments of a convolution over a semiring other than (+, *) have the shape that makes
it fast: convex for min, concave for max. Neither asks for the O(n m) loop by name.
Curved.Both
BothCurved.Right
RightCurved.Neither
NeitherDisjoint
pub struct DisjointThe index op of a subset convolution: i | j over disjoint pairs i & j == 0. A value with a
transform impl, so user libraries can define more index ops the same way.
subset
pub const subset = Disjoint()on: subset in convolve.
SosOver
pub enum SosOver = Sub | SupDirection of a sum-over-subsets (SOS) zeta/Mobius transform.
SosOver.Sub
SubSosOver.Sup
SupRelaxedConvolve
pub struct RelaxedConvolve<P>O(log^2 n) amortized per step, O(n log^2 n) total. Online (relaxed) NTT convolution:
supply (a[k], b[k]) one step at a time and immediately receive c[k] = sum_{i=0..=k} a[i] * b[k - i].
RelaxedConvolve.new
fn new() -> RelaxedConvolve<P>An empty online convolution: no values pushed yet.
- cost: O(1)
- traps: never
Examples:
type Z = Mod<17>; var rc = RelaxedConvolve<17>(); rc.push(Z(0), Z(0)) == Z(0)
RelaxedConvolve.push
fn push(mut self, ai: Mod<P>, bi: Mod<P>) -> Mod<P>Append a[k] = ai and b[k] = bi at the next index k and return c[k] = sum_{i=0..=k} a[i] * b[k - i].
c[k] depends only on values already pushed, so a[k+1] and b[k+1] may be computed from
it: the shape of online DP like f[k] = sum f[i] g[k - i].
- cost: O(log^2 k) amortized
- traps: when
kreaches the largest NTT lengthPsupports
Examples:
type Z = Mod<17>; var rc = RelaxedConvolve<17>(); rc.push(Z(1), Z(3)) == Z(3)type Z = Mod<17>; var rc = RelaxedConvolve<17>(); rc.push(Z(1), Z(3)); rc.push(Z(2), Z(4)) == Z(10)
SemiRelaxedConvolve
pub struct SemiRelaxedConvolve<P>O(log^2 n) amortized per step. Semi-relaxed NTT convolution against a fixed b
(supply a[k] online and immediately receive c[k] = sum_{i=0..=k} a[i] * b[k - i]).
SemiRelaxedConvolve.new
fn new(b: List<Mod<P>>) -> SemiRelaxedConvolve<P>An online convolution against the fixed polynomial b, nothing pushed yet.
b is zero-padded as far as the pushes go, so pushing past b.len is allowed; an empty b
makes every c[k] zero.
- cost: O(b.len)
- empty: every pushed
c[k]is zero - traps: never
Examples:
type Z = Mod<17>; var sc = SemiRelaxedConvolve<17>([Z(1), Z(2)]); sc.push(Z(1)) == Z(1)type Z = Mod<17>; let e: List<Z> = []; var sc = SemiRelaxedConvolve<17>(e); sc.push(Z(5)) == Z(0)
SemiRelaxedConvolve.push
fn push(mut self, ai: Mod<P>) -> Mod<P>Append a[k] = ai at the next index k and return c[k] = sum_{i=0..=k} a[i] * b[k - i].
- cost: O(log^2 k) amortized
- traps: when
kreaches the largest NTT lengthPsupports
Examples:
type Z = Mod<17>; var sc = SemiRelaxedConvolve<17>([Z(1), Z(2)]); sc.push(Z(1)); sc.push(Z(2)); sc.push(Z(5)) == Z(9)