| Safe Haskell | Safe-Inferred |
|---|---|
| Language | GHC2021 |
AtCoder.Convolution
Contents
Description
It calculates (+,×) convolution. Given two arrays a0,a1,⋯,aN−1 and b0,b1,⋯,bM−1, it calculates the array c of length N+M−1, defined by
ci=i∑j=0ajbi−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
Define specific modulus items:
>>>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 aconvolutionRaw:
>>>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.0
Synopsis
- convolution :: forall p. (HasCallStack, Modulus p) => Vector (ModInt p) -> Vector (ModInt p) -> Vector (ModInt p)
- convolutionRaw :: forall p 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. (HasCallStack, Modulus p) => Vector (ModInt p) -> Vector (ModInt p) -> Vector (ModInt p) Source #
Calculates the convolution in modm for a vector of ModInt. It returns an empty
array if at least one of a and b are empty.
Constraints
- 2≤m≤2×109
- m is prime.
- There is an integer c with 2c|(m−1) and |a|+|b|−1≤2c.
Complexity
- O(nlogn+logmod), where n=|a|+|b|.
Since: 1.0.0.0
convolutionRaw :: forall p a. (HasCallStack, Modulus p, Integral a, Unbox a) => Proxy p -> Vector a -> Vector a -> Vector a Source #
Calculates convolution in modm for any Integral a.
Constraints
- 2≤m≤2×109
- m is prime.
- There is an integer c with 2c|(m−1) and |a|+|b|−1≤2c.
Complexity
- O(nlogn+logmod), where n=|a|+|b|.
Since: 1.0.0.0
Convolution
convolution64 :: HasCallStack => Vector Int -> Vector Int -> Vector Int Source #
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≤224
Complexity
- O(nlogn), where n=|a|+|b|.
Since: 1.0.0.0