| Safe Haskell | None |
|---|---|
| Language | GHC2021 |
AtCoder.Convolution
Contents
Description
It calculates \((+,\times)\) convolution. Given two arrays \(a_0, a_1, \cdots, a_{N - 1}\) and \(b_0, b_1, \cdots, b_{M - 1}\), it calculates the array \(c\) of length \(N + M - 1\), defined by
\[ c_i = \sum_{j = 0}^i a_j b_{i - j} \]
Example
The convolution module basically works with ModInt:
>>>import AtCoder.Convolution qualified as C>>>import AtCoder.ModInt qualified as M>>>import Data.Proxy (Proxy)>>>import Data.Vector.Unboxed qualified as VU
It's handy to define specific items for interested modulus values:
>>>type Mint = M.ModInt998244353>>>let modInt :: Int -> Mint; modInt = M.new
Calculate convolution:
>>>let a = VU.map modInt $ VU.fromList [1, 2, 3, 4]>>>let b = VU.map modInt $ VU.fromList [5, 6, 7, 8]>>>C.convolution a b[5,16,34,60,61,52,32]
You can also target any Integral a
>>>let a = VU.fromList @Int [1, 2, 3, 4]>>>let b = VU.fromList @Int [5, 6, 7, 8]>>>C.convolutionRaw (Proxy @998244353) a b[5,16,34,60,61,52,32]
If you want to calculate large values without taking mod, use convolution64.
Since: 1.0.0
Synopsis
- convolution :: forall (p :: Nat). (HasCallStack, Modulus p) => Vector (ModInt p) -> Vector (ModInt p) -> Vector (ModInt p)
- convolutionRaw :: forall (p :: Nat) a. (HasCallStack, Modulus p, Integral a, Unbox a) => Proxy p -> Vector a -> Vector a -> Vector a
- convolution64 :: HasCallStack => Vector Int -> Vector Int -> Vector Int
Convolution in mod m
convolution :: forall (p :: Nat). (HasCallStack, Modulus p) => Vector (ModInt p) -> Vector (ModInt p) -> Vector (ModInt p) #
Calculates the convolution in \(\bmod m\) for a vector of ModInt. It returns an empty
array if at least one of \(a\) and \(b\) are empty.
Constraints
- \(2 \leq m \leq 2 \times 10^9\)
- \(m\) is prime.
- There is an integer \(c\) with \(2^c | (m - 1)\) and \(|a| + |b| - 1 \leq 2^c\).
Complexity
- \(O(n\log{n} + \log{\mathrm{mod}})\), where \(n = |a| + |b|\).
Since: 1.0.0
convolutionRaw :: forall (p :: Nat) a. (HasCallStack, Modulus p, Integral a, Unbox a) => Proxy p -> Vector a -> Vector a -> Vector a #
Calculates convolution in \(\bmod m\) for any Integral a.
Constraints
- \(2 \leq m \leq 2 \times 10^9\)
- \(m\) is prime.
- There is an integer \(c\) with \(2^c | (m - 1)\) and \(|a| + |b| - 1 \leq 2^c\).
Complexity
- \(O(n\log{n} + \log{\mathrm{mod}})\), where \(n = |a| + |b|\).
Since: 1.0.0
Convolution
convolution64 :: HasCallStack => Vector Int -> Vector Int -> Vector Int #
Calculates the convolution (without taking mod). It returns an empty array if at least one of \(a\) and \(b\) are empty.
Constraints
- \(|a| + |b| - 1 \leq 2^{24}\)
Complexity
- \(O(n\log{n})\), where \(n = |a| + |b|\).
Since: 1.0.0