| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.BinaryLifting
Description
Type class-based binary lifting with caches. Prefer Stimes module if it's one-shot.
Actually, BinaryLifting makes almost no sense.
Binary lifting is a technique for calculating nth power of a semigroup element in a (big) constant time, or applying them to their semigroup action target.
The i-th element of the underlying vector of BinaryLifting stores \(s^{2^i}\), with which we
can construct any of \(s^i\) ((0 <= i < 2^63)) in a big (63) constant time.
Synopsis
- cacheBLU :: (Semigroup a, Unbox a) => a -> Vector a
- cacheBLV :: Semigroup a => a -> Vector a
- stimesBL :: (Semigroup a, Vector v a) => v a -> Int -> a -> a
- mtimesBL :: (Monoid a, Vector v a) => v a -> Int -> a
- sactBL :: (SemigroupAction a b, Vector v a) => v a -> Int -> b -> b
- newtype Permutation = Permutation (Vector Int)
- idPermutation :: Int -> Permutation
- unPermutation :: Permutation -> Vector Int
- newtype IndexMap = IndexMap (Vector Int)
- unIndexMap :: IndexMap -> Vector Int
- idIndexMap :: Int -> IndexMap
- newtype IndexMapWithAction a = IndexMapWithAction (Vector (Int, a))
- unIndexMapWithAction :: IndexMapWithAction a -> Vector (Int, a)
- idIndexMapWithAction :: Unbox a => Int -> a -> IndexMapWithAction a
Documentation
stimesBL :: (Semigroup a, Vector v a) => v a -> Int -> a -> a #
\(O((\diamond) \cdot \mathit{popCount}(n))\)
mtimesBL :: (Monoid a, Vector v a) => v a -> Int -> a #
\(O({(\diamond)} \cdot \mathit{popCount}(n))\)
sactBL :: (SemigroupAction a b, Vector v a) => v a -> Int -> b -> b #
\(O(\mathit{sact} \cdot \mathit{popCount}(n))\) Performs semigroup action based on the binary lifting table.
Product
Permutation
newtype Permutation #
Semigroup action of permutation.
Constructors
| Permutation (Vector Int) |
Instances
| Semigroup Permutation # | |
Defined in Data.BinaryLifting Methods (<>) :: Permutation -> Permutation -> Permutation # sconcat :: NonEmpty Permutation -> Permutation # stimes :: Integral b => b -> Permutation -> Permutation # | |
| SemigroupAction Permutation Int # |
|
Defined in Data.BinaryLifting Methods sact :: Permutation -> Int -> Int # | |
| SemigroupAction Permutation (Vector Int) # |
|
Defined in Data.BinaryLifting | |
idPermutation :: Int -> Permutation #
Creates identity Permutation of length n.
unPermutation :: Permutation -> Vector Int #
Creates identity Permutation of length n.
IndexMap
unIndexMap :: IndexMap -> Vector Int #
Creates identity Permutation of length n.
idIndexMap :: Int -> IndexMap #
Creates identity Permutation of length n.
IndexMapWithAction: Transition + Semigroup
newtype IndexMapWithAction a #
Transition + semigroup concatanation. LCA is based on this.
Typical problems (Permutation)
- Typical 058 - Original Calculator (★4) = Typical problems (Permutation)
Typical problems (IndexMapWithAction)
c.f. LCA.
Constructors
| IndexMapWithAction (Vector (Int, a)) |
Instances
unIndexMapWithAction :: IndexMapWithAction a -> Vector (Int, a) #
idIndexMapWithAction :: Unbox a => Int -> a -> IndexMapWithAction a #
The identity element of IndexMapWithAction.