Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.Extra.Semigroup.Matrix

Contents

Matrix
Constructors
Mapping
Multiplications
Powers
Rank
Inverse
Determinant

Description

A simple HxW matrix backed by a vector, mainly for binary exponention.

The matrix is a left semigroup action: $m_2 (m_1 v) = (m_2 \circ m_1) v$ .

Since: 1.1.0.0

Synopsis

data Matrix a = Matrix {
- hM :: !Int
- wM :: !Int
- vecM :: !(Vector a)
}
new :: (HasCallStack, Unbox a) => Int -> Int -> Vector a -> Matrix a
square :: (HasCallStack, Unbox a) => Int -> Vector a -> Matrix a
zero :: (Unbox a, Num a) => Int -> Matrix a
ident :: (Unbox a, Num a) => Int -> Matrix a
diag :: (Unbox a, Num a) => Vector a -> Matrix a
map :: (Unbox a, Unbox b) => (a -> b) -> Matrix a -> Matrix b
mulToCol :: (Num a, Unbox a) => Matrix a -> Col a -> Col a
mul :: forall e. (Num e, Unbox e) => Matrix e -> Matrix e -> Matrix e
mulMod :: Int -> Matrix Int -> Matrix Int -> Matrix Int
mulMint :: forall a. KnownNat a => Matrix (ModInt a) -> Matrix (ModInt a) -> Matrix (ModInt a)
pow :: Int -> Matrix Int -> Matrix Int
powMod :: Int -> Int -> Matrix Int -> Matrix Int
powMint :: forall m. KnownNat m => Int -> Matrix (ModInt m) -> Matrix (ModInt m)
rank :: (Fractional a, Eq a, Unbox a) => Matrix a -> Int
inv :: forall a. (Fractional a, Eq a, Unbox a) => Matrix a -> Maybe (a, Matrix a)
invRaw :: forall a. (Fractional a, Eq a, Unbox a) => Matrix a -> Maybe (a, Vector (Vector a))
detMod :: Int -> Matrix Int -> Int
detMint :: forall a. KnownNat a => Matrix (ModInt a) -> ModInt a

Matrix

data Matrix a Source #

A simple HxW matrix backed by a vector, mainly for binary exponention.

The matrix is a left semigroup action: $m_2 (m_1 v) = (m_2 \circ m_1) v$ .

Since: 1.1.0.0

Constructors

Matrix
Fields hM :: !Int Since: 1.1.0.0 wM :: !Int Since: 1.1.0.0 vecM :: !(Vector a) Since: 1.1.0.0

Instances

Instances details

(Num a, Unbox a) => Semigroup (Matrix a) Source #	Since: 1.1.0.0
Instance details Defined in AtCoder.Extra.Semigroup.Matrix Methods (<>) :: Matrix a -> Matrix a -> Matrix a # sconcat :: NonEmpty (Matrix a) -> Matrix a # stimes :: Integral b => b -> Matrix a -> Matrix a #
(Show a, Unbox a) => Show (Matrix a) Source #	Since: 1.1.0.0
Instance details Defined in AtCoder.Extra.Semigroup.Matrix Methods showsPrec :: Int -> Matrix a -> ShowS # show :: Matrix a -> String # showList :: [Matrix a] -> ShowS #
(Unbox a, Eq a) => Eq (Matrix a) Source #	Since: 1.1.0.0
Instance details Defined in AtCoder.Extra.Semigroup.Matrix Methods (==) :: Matrix a -> Matrix a -> Bool # (/=) :: Matrix a -> Matrix a -> Bool #

Constructors

new :: (HasCallStack, Unbox a) => Int -> Int -> Vector a -> Matrix a Source #

$O(hw)$ Creates an HxW matrix.

Since: 1.1.0.0

square :: (HasCallStack, Unbox a) => Int -> Vector a -> Matrix a Source #

$O(n^2)$ Creates an NxN square matrix.

Since: 1.1.1.0

zero :: (Unbox a, Num a) => Int -> Matrix a Source #

$O(n^2)$ Creates an NxN zero matrix.

Since: 1.1.0.0

ident :: (Unbox a, Num a) => Int -> Matrix a Source #

$O(n^2)$ Creates an NxN identity matrix.

Since: 1.1.0.0

diag :: (Unbox a, Num a) => Vector a -> Matrix a Source #

$O(n^2)$ Creates an NxN diagonal matrix.

Since: 1.1.0.0

Mapping

map :: (Unbox a, Unbox b) => (a -> b) -> Matrix a -> Matrix b Source #

$O(n^2)$ Maps the Matrix.

Since: 1.1.0.0

Multiplications

mulToCol :: (Num a, Unbox a) => Matrix a -> Col a -> Col a Source #

$O(hw)$ Multiplies HxW matrix to a Hx1 column vector.

Since: 1.1.0.0

mul :: forall e. (Num e, Unbox e) => Matrix e -> Matrix e -> Matrix e Source #

$O(h_1 K w_2)$ Multiplies H1xK matrix to a KxW2 matrix.

Since: 1.1.0.0

mulMod :: Int -> Matrix Int -> Matrix Int -> Matrix Int Source #

$O(h_1 w_2 K)$ Multiplies H1xK matrix to a KxW2 matrix, taking the mod.

Since: 1.1.0.0

mulMint :: forall a. KnownNat a => Matrix (ModInt a) -> Matrix (ModInt a) -> Matrix (ModInt a) Source #

$O(h_1 w_2 K)$ mul specialized to ModInt.

Since: 1.1.0.0

Powers

pow :: Int -> Matrix Int -> Matrix Int Source #

$O(w n^3)$ Returns $M^k$ .

Since: 1.1.0.0

powMod :: Int -> Int -> Matrix Int -> Matrix Int Source #

$O(w n^3)$ Returns $M^k$ , taking the mod.

Since: 1.1.0.0

powMint :: forall m. KnownNat m => Int -> Matrix (ModInt m) -> Matrix (ModInt m) Source #

$O(w n^3)$ Returns $M^k$ , specialized to ModInt.

Since: 1.1.0.0

Rank

rank :: (Fractional a, Eq a, Unbox a) => Matrix a -> Int Source #

$O(hw \min(h, w))$ Returns the rank of the matrix.

Since: 1.1.1.0

Inverse

inv :: forall a. (Fractional a, Eq a, Unbox a) => Matrix a -> Maybe (a, Matrix a) Source #

$O(n^3)$ Returns (det, invMatrix) or Nothing if the matrix does not have inverse (the determinant is zero).

Constraints

The input must be a square matrix.

Since: 1.1.1.0

invRaw :: forall a. (Fractional a, Eq a, Unbox a) => Matrix a -> Maybe (a, Vector (Vector a)) Source #

$O(n^3)$ Returns (det, invMatrix) or Nothing if the matrix does not have inverse (the determinant is zero).

Constraints

The input must be a square matrix.

Since: 1.1.1.0

Determinant

detMod :: Int -> Matrix Int -> Int Source #

$O(hw \min(h, w))$ Returns the rank of the matrix.

Since: 1.1.1.0

detMint :: forall a. KnownNat a => Matrix (ModInt a) -> ModInt a Source #

$O(hw \min(h, w))$ Returns the rank of the matrix.

Since: 1.1.1.0

Key	Shortcut
s	Open this search box
esc	Close this search box
↓,ctrl + j	Move down in search results
↑,ctrl + k	Move up in search results
↵	Go to active search result