| Safe Haskell | None |
|---|---|
| Language | GHC2021 |
AtCoder.Internal.Convolution
Description
Internal implementation of Convolution module.
Since: 1.0.0
Synopsis
- data FftInfo (p :: k)
- newInfo :: forall m (p :: Nat). (PrimMonad m, Modulus p) => m (FftInfo p)
- butterfly :: forall m (p :: Nat). (PrimMonad m, Modulus p) => FftInfo p -> MVector (PrimState m) (ModInt p) -> m ()
- butterflyInv :: forall m (p :: Nat). (PrimMonad m, Modulus p) => FftInfo p -> MVector (PrimState m) (ModInt p) -> m ()
- convolutionNaive :: forall (p :: Nat). Modulus p => Vector (ModInt p) -> Vector (ModInt p) -> Vector (ModInt p)
- convolutionFft :: forall (p :: Nat). Modulus p => Vector (ModInt p) -> Vector (ModInt p) -> Vector (ModInt p)
FFT information
Data for FFT calculation.
Since: 1.0.0
newInfo :: forall m (p :: Nat). (PrimMonad m, Modulus p) => m (FftInfo p) #
\(O(\log m)\) Creates FftInfo.
Since: 1.0.0
Butterfly operation
butterfly :: forall m (p :: Nat). (PrimMonad m, Modulus p) => FftInfo p -> MVector (PrimState m) (ModInt p) -> m () #
Since: 1.0.0
butterflyInv :: forall m (p :: Nat). (PrimMonad m, Modulus p) => FftInfo p -> MVector (PrimState m) (ModInt p) -> m () #
Since: 1.0.0