src/cplib/convolution/relaxed_convolution

    Dark Mode
Search:
Group by:
  Source   Edit

Types

RelaxedConvolution[T] = object
  coefficientCount: int
  currentIndex: int
  left, right, product: seq[T]
  leftPrefixTransforms, rightPrefixTransforms: seq[seq[T]]
  Source   Edit 
RelaxedExp[T] = object
  coefficientCount, currentIndex: int
  convolution: RelaxedConvolution[T]
  values: seq[T]
  Source   Edit 
RelaxedInv[T] = object
  coefficientCount, currentIndex: int
  convolution: RelaxedConvolution[T]
  values: seq[T]
  constantInverse: T
  Source   Edit 
RelaxedLog[T] = object
  coefficientCount, currentIndex: int
  inverse: RelaxedInv[T]
  convolution: RelaxedConvolution[T]
  values: seq[T]
  Source   Edit 
RelaxedPow[T] = object
  coefficientCount, currentIndex, exponent: int
  order, shift, bodyCount: int
  constantInverse, constantPower: T
  logarithm: RelaxedLog[T]
  exponential: RelaxedExp[T]
  body, values: seq[T]
  Source   Edit 
RelaxedSqrt[T] = object
  coefficientCount, currentIndex: int
  convolution: RelaxedConvolution[T]
  values: seq[T]
  inverseDoubleConstant: T
  failed: bool
  Source   Edit

Procs

proc add[T](self: var RelaxedConvolution[T]; leftValue, rightValue: T): T
次の2係数を追加し、その次数の積の係数を返す。   Source   Edit 
proc add[T](self: var RelaxedExp[T]; coefficient: T): T
fの次の係数を追加し、exp(f)の同じ次数の係数を返す。   Source   Edit 
proc add[T](self: var RelaxedInv[T]; coefficient: T): T
fの次の係数を追加し、f^(-1)の同じ次数の係数を返す。   Source   Edit 
proc add[T](self: var RelaxedLog[T]; coefficient: T): T
fの次の係数を追加し、log(f)の同じ次数の係数を返す。   Source   Edit 
proc add[T](self: var RelaxedPow[T]; coefficient: T): T
fの次の係数を追加し、f^kの同じ次数の係数を返す。   Source   Edit 
proc add[T](self: var RelaxedSqrt[T]; coefficient: T): Option[T]
fの次の係数を追加し、sqrt(f)の同じ次数の係数を返す。 定数項が0の場合は出力係数が逐次に定まらないため扱わない。   Source   Edit 
proc append[T](self: var RelaxedConvolution[T]; leftValue, rightValue: T): T
  Source   Edit 
proc append[T](self: var RelaxedExp[T]; coefficient: T): T
  Source   Edit 
proc append[T](self: var RelaxedInv[T]; coefficient: T): T
  Source   Edit 
proc append[T](self: var RelaxedLog[T]; coefficient: T): T
  Source   Edit 
proc append[T](self: var RelaxedPow[T]; coefficient: T): T
  Source   Edit 
proc append[T](self: var RelaxedSqrt[T]; coefficient: T): Option[T]
  Source   Edit 
proc coefficients[T](self: RelaxedConvolution[T]): seq[T]
現在までに確定した積の係数を返す。   Source   Edit 
proc coefficients[T](self: RelaxedExp[T]): seq[T]
  Source   Edit 
proc coefficients[T](self: RelaxedInv[T]): seq[T]
  Source   Edit 
proc coefficients[T](self: RelaxedLog[T]): seq[T]
  Source   Edit 
proc coefficients[T](self: RelaxedPow[T]): seq[T]
  Source   Edit 
proc coefficients[T](self: RelaxedSqrt[T]): Option[seq[T]]
  Source   Edit 
proc expRelaxed[T: BarrettModint or MontgomeryModint](f: seq[T]): seq[T]
  Source   Edit 
proc expRelaxed[T: BarrettModint or MontgomeryModint](f: seq[T]; n: int): seq[T]
Relaxed convolutionにより形式的指数関数を低次から逐次計算する。   Source   Edit 
proc get[T](self: var RelaxedConvolution[T]; leftValue, rightValue: T): T
  Source   Edit 
proc get[T](self: var RelaxedExp[T]; coefficient: T): T
  Source   Edit 
proc get[T](self: var RelaxedInv[T]; coefficient: T): T
  Source   Edit 
proc get[T](self: var RelaxedLog[T]; coefficient: T): T
  Source   Edit 
proc get[T](self: var RelaxedPow[T]; coefficient: T): T
  Source   Edit 
proc get[T](self: var RelaxedSqrt[T]; coefficient: T): Option[T]
  Source   Edit 
proc initRelaxedConvolution[T: BarrettModint or MontgomeryModint](
    coefficientCount: int): RelaxedConvolution[T]
先頭からcoefficientCount項を逐次計算する畳み込みを初期化する。 NTTが利用できる場合、全項の計算量はO(N log^2 N)となる。   Source   Edit 
proc initRelaxedExp[T: BarrettModint or MontgomeryModint](coefficientCount: int): RelaxedExp[
    T]
形式的指数関数の係数を逐次計算する状態を初期化する。   Source   Edit 
proc initRelaxedInv[T: BarrettModint or MontgomeryModint](coefficientCount: int): RelaxedInv[
    T]
乗法逆元の係数を逐次計算する状態を初期化する。   Source   Edit 
proc initRelaxedLog[T: BarrettModint or MontgomeryModint](coefficientCount: int): RelaxedLog[
    T]
形式的対数の係数を逐次計算する状態を初期化する。   Source   Edit 
proc initRelaxedPow[T: BarrettModint or MontgomeryModint](
    coefficientCount, exponent: int): RelaxedPow[T]
非負整数冪の係数を逐次計算する状態を初期化する。   Source   Edit 
proc initRelaxedSqrt[T: BarrettModint or MontgomeryModint](coefficientCount: int): RelaxedSqrt[
    T]
非零の定数項を持つFPSの平方根を逐次計算する状態を初期化する。   Source   Edit 
proc invRelaxed[T: BarrettModint or MontgomeryModint](f: seq[T]): seq[T]
  Source   Edit 
proc invRelaxed[T: BarrettModint or MontgomeryModint](f: seq[T]; n: int): seq[T]
Relaxed convolutionにより逆元を低次から逐次計算する。   Source   Edit 
proc len[T](self: RelaxedConvolution[T]): int
  Source   Edit 
proc len[T](self: RelaxedExp[T]): int
  Source   Edit 
proc len[T](self: RelaxedInv[T]): int
  Source   Edit 
proc len[T](self: RelaxedLog[T]): int
  Source   Edit 
proc len[T](self: RelaxedPow[T]): int
  Source   Edit 
proc len[T](self: RelaxedSqrt[T]): int
  Source   Edit 
proc logRelaxed[T: BarrettModint or MontgomeryModint](f: seq[T]): seq[T]
  Source   Edit 
proc logRelaxed[T: BarrettModint or MontgomeryModint](f: seq[T]; n: int): seq[T]
Relaxed convolutionにより形式的対数を低次から逐次計算する。   Source   Edit 
proc pendingCoefficient[T](self: RelaxedConvolution[T]): T
次に確定する係数に既に加算済みの寄与を返す。   Source   Edit 
proc powRelaxed[T: BarrettModint or MontgomeryModint](f: seq[T]; k, n: int): seq[
    T]
Relaxed convolutionにより非負整数冪を低次から逐次計算する。   Source   Edit 
proc powRelaxed[T: BarrettModint or MontgomeryModint](f: seq[T]; k: int): seq[T]
  Source   Edit 
proc sqrtRelaxed[T: BarrettModint or MontgomeryModint](f: seq[T]): Option[seq[T]]
  Source   Edit 
proc sqrtRelaxed[T: BarrettModint or MontgomeryModint](f: seq[T]; n: int): Option[
    seq[T]]
Relaxed convolutionにより平方根を低次から逐次計算する。   Source   Edit

Made with Nim. Generated: 2026-09-08 06:14:39 UTC