AtCoder.Extra.Semigroup.Matrix

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

Matrix

data Matrix a

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

(Num a, Unbox a) => Semigroup (Matrix a)

Since: 1.1.0.0

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)

Since: 1.1.0.0

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)

Since: 1.1.0.0

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

\(O(hw)\) Creates an HxW matrix.

Since: 1.1.0.0

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

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

Since: 1.1.1.0

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

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

Since: 1.1.0.0

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

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

Since: 1.1.0.0

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

\(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

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

Since: 1.1.0.0

Multiplications

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

\(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

\(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

\(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)

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

Since: 1.1.0.0

Powers

pow :: Int -> Matrix Int -> Matrix Int

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

Since: 1.1.0.0

powMod :: Int -> Int -> Matrix Int -> Matrix Int

\(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)

\(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

\(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)

\(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))

\(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

\(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

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

Since: 1.1.1.0