AtCoder.ModInt

It is the struct that treats the modular arithmetic. All the remaining parts of AC Library works without modint, so you don't necessarily read this to use the remaining parts.

For most of the problems, it is sufficient to use ModInt998244353, ModInt1000000007, which can be used as follows.

>>> import AtCoder.ModInt qualified as M
>>> type Mint = M.ModInt998244353
>>> let modInt :: Int -> Mint; modInt = M.new
>>> modInt 1000000000
1755647

Major changes from the original ac-library

• DynamicModInt is removed.

Since: 1.0.0

Modulus

class KnownNat a => Modulus a where

KnownNat with meta information used for modulus.

Since: 1.0.0

Minimal complete definition

isPrimeModulus

Methods

isPrimeModulus :: Proxy# a -> Bool

Returns if the modulus is a prime value.

Since: 1.0.0

primitiveRootModulus :: Proxy# a -> Int

Returns the primitive root of the modulus value. Note that the default implementation is slow.

Since: 1.0.0

Instances

Modulus 167772161

\(2^{24} - 1\).

Since: 1.0.0

Defined in AtCoder.ModInt

Methods

isPrimeModulus :: Proxy# 167772161 -> Bool

primitiveRootModulus :: Proxy# 167772161 -> Int

Modulus 469762049

\(2^{25} - 1\).

Since: 1.0.0

Defined in AtCoder.ModInt

Methods

isPrimeModulus :: Proxy# 469762049 -> Bool

primitiveRootModulus :: Proxy# 469762049 -> Int

Modulus 754974721

\(2^{26} - 1\).

Since: 1.0.0

Defined in AtCoder.ModInt

Methods

isPrimeModulus :: Proxy# 754974721 -> Bool

primitiveRootModulus :: Proxy# 754974721 -> Int

Modulus 998244353

\(119 \times 2^{23} + 1\). It is often used in contest problems

Since: 1.0.0

Defined in AtCoder.ModInt

Methods

isPrimeModulus :: Proxy# 998244353 -> Bool

primitiveRootModulus :: Proxy# 998244353 -> Int

Modulus 1000000007

It used to be used in contest problems.

Since: 1.0.0

Defined in AtCoder.ModInt

Methods

isPrimeModulus :: Proxy# 1000000007 -> Bool

primitiveRootModulus :: Proxy# 1000000007 -> Int

Modulus 2147483647

\(2^{31} - 1\), suitable for boundary testing.

Since: 1.0.0

Defined in AtCoder.ModInt

Methods

isPrimeModulus :: Proxy# 2147483647 -> Bool

primitiveRootModulus :: Proxy# 2147483647 -> Int

type ModInt998244353 = ModInt 998244353

ModInt with modulus value 998244353.

Since: 1.0.0

type ModInt1000000007 = ModInt 1000000007

ModInt with modulus value 1000000007.

Since: 1.0.0

Helpers

modVal :: forall a. KnownNat a => Proxy a -> Int

Retrieves Int from KnownNat.

>>> import Data.Proxy (Proxy(..))
>>> modVal (Proxy @42)
42

Since: 1.0.0

modVal# :: forall a. KnownNat a => Proxy# a -> Int

Retrieves Int from KnownNat.

>>> :set -XMagicHash
>>> import GHC.Exts (proxy#)
>>> modVal# (proxy# @42)
42

Since: 1.0.0

ModInt

newtype ModInt a

Word32 value that treats the modula arithmetic.

Constructors

ModInt

Fields

• unModInt :: Word32

Instances

Vector Vector (ModInt a)

• - @since 1.0.0

Defined in AtCoder.ModInt

Methods

basicUnsafeFreeze :: Mutable Vector s (ModInt a) -> ST s (Vector (ModInt a))

basicUnsafeThaw :: Vector (ModInt a) -> ST s (Mutable Vector s (ModInt a))

basicLength :: Vector (ModInt a) -> Int

basicUnsafeSlice :: Int -> Int -> Vector (ModInt a) -> Vector (ModInt a)

basicUnsafeIndexM :: Vector (ModInt a) -> Int -> Box (ModInt a)

basicUnsafeCopy :: Mutable Vector s (ModInt a) -> Vector (ModInt a) -> ST s ()

elemseq :: Vector (ModInt a) -> ModInt a -> b -> b

MVector MVector (ModInt a)

• - @since 1.0.0

Defined in AtCoder.ModInt

Methods

basicLength :: MVector s (ModInt a) -> Int

basicUnsafeSlice :: Int -> Int -> MVector s (ModInt a) -> MVector s (ModInt a)

basicOverlaps :: MVector s (ModInt a) -> MVector s (ModInt a) -> Bool

basicUnsafeNew :: Int -> ST s (MVector s (ModInt a))

basicInitialize :: MVector s (ModInt a) -> ST s ()

basicUnsafeReplicate :: Int -> ModInt a -> ST s (MVector s (ModInt a))

basicUnsafeRead :: MVector s (ModInt a) -> Int -> ST s (ModInt a)

basicUnsafeWrite :: MVector s (ModInt a) -> Int -> ModInt a -> ST s ()

basicClear :: MVector s (ModInt a) -> ST s ()

basicSet :: MVector s (ModInt a) -> ModInt a -> ST s ()

basicUnsafeCopy :: MVector s (ModInt a) -> MVector s (ModInt a) -> ST s ()

basicUnsafeMove :: MVector s (ModInt a) -> MVector s (ModInt a) -> ST s ()

basicUnsafeGrow :: MVector s (ModInt a) -> Int -> ST s (MVector s (ModInt a))

KnownNat p => Bounded (ModInt p)

• - @since 1.0.0

Defined in AtCoder.ModInt

Methods

minBound :: ModInt p

maxBound :: ModInt p

KnownNat p => Enum (ModInt p)

• - @since 1.0.0

Defined in AtCoder.ModInt

Methods

succ :: ModInt p -> ModInt p

pred :: ModInt p -> ModInt p

toEnum :: Int -> ModInt p

fromEnum :: ModInt p -> Int

enumFrom :: ModInt p -> [ModInt p]

enumFromThen :: ModInt p -> ModInt p -> [ModInt p]

enumFromTo :: ModInt p -> ModInt p -> [ModInt p]

enumFromThenTo :: ModInt p -> ModInt p -> ModInt p -> [ModInt p]

KnownNat p => Num (ModInt p)

• - @since 1.0.0

Defined in AtCoder.ModInt

Methods

(+) :: ModInt p -> ModInt p -> ModInt p

(-) :: ModInt p -> ModInt p -> ModInt p

(*) :: ModInt p -> ModInt p -> ModInt p

negate :: ModInt p -> ModInt p

abs :: ModInt p -> ModInt p

signum :: ModInt p -> ModInt p

fromInteger :: Integer -> ModInt p

Read (ModInt a)

Defined in AtCoder.ModInt

Methods

readsPrec :: Int -> ReadS (ModInt a)

readList :: ReadS [ModInt a]

readPrec :: ReadPrec (ModInt a)

readListPrec :: ReadPrec [ModInt a]

Modulus p => Fractional (ModInt p)

• - @since 1.0.0

Defined in AtCoder.ModInt

Methods

(/) :: ModInt p -> ModInt p -> ModInt p

recip :: ModInt p -> ModInt p

fromRational :: Rational -> ModInt p

Modulus p => Integral (ModInt p)

• - @since 1.0.0

Defined in AtCoder.ModInt

Methods

quot :: ModInt p -> ModInt p -> ModInt p

rem :: ModInt p -> ModInt p -> ModInt p

div :: ModInt p -> ModInt p -> ModInt p

mod :: ModInt p -> ModInt p -> ModInt p

quotRem :: ModInt p -> ModInt p -> (ModInt p, ModInt p)

divMod :: ModInt p -> ModInt p -> (ModInt p, ModInt p)

toInteger :: ModInt p -> Integer

KnownNat p => Real (ModInt p)

• - @since 1.0.0

Defined in AtCoder.ModInt

Methods

toRational :: ModInt p -> Rational

Show (ModInt a)

Defined in AtCoder.ModInt

Methods

showsPrec :: Int -> ModInt a -> ShowS

show :: ModInt a -> String

showList :: [ModInt a] -> ShowS

Eq (ModInt a)

Defined in AtCoder.ModInt

Methods

(==) :: ModInt a -> ModInt a -> Bool

(/=) :: ModInt a -> ModInt a -> Bool

Ord (ModInt a)

Defined in AtCoder.ModInt

Methods

compare :: ModInt a -> ModInt a -> Ordering

(<) :: ModInt a -> ModInt a -> Bool

(<=) :: ModInt a -> ModInt a -> Bool

(>) :: ModInt a -> ModInt a -> Bool

(>=) :: ModInt a -> ModInt a -> Bool

max :: ModInt a -> ModInt a -> ModInt a

min :: ModInt a -> ModInt a -> ModInt a

Prim (ModInt a)

Defined in AtCoder.ModInt

Methods

sizeOfType# :: Proxy (ModInt a) -> Int#

sizeOf# :: ModInt a -> Int#

alignmentOfType# :: Proxy (ModInt a) -> Int#

alignment# :: ModInt a -> Int#

indexByteArray# :: ByteArray# -> Int# -> ModInt a

readByteArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, ModInt a #)

writeByteArray# :: MutableByteArray# s -> Int# -> ModInt a -> State# s -> State# s

setByteArray# :: MutableByteArray# s -> Int# -> Int# -> ModInt a -> State# s -> State# s

indexOffAddr# :: Addr# -> Int# -> ModInt a

readOffAddr# :: Addr# -> Int# -> State# s -> (# State# s, ModInt a #)

writeOffAddr# :: Addr# -> Int# -> ModInt a -> State# s -> State# s

setOffAddr# :: Addr# -> Int# -> Int# -> ModInt a -> State# s -> State# s

Unbox (ModInt a)

• - @since 1.0.0

Defined in AtCoder.ModInt

newtype MVector s (ModInt a)

• - @since 1.0.0

Defined in AtCoder.ModInt

newtype MVector s (ModInt a) = MV_ModInt (MVector s Word32)

newtype Vector (ModInt a)

• - @since 1.0.0

Defined in AtCoder.ModInt

newtype Vector (ModInt a) = V_ModInt (Vector Word32)

Constructors

Safe constructors

new :: forall a. KnownNat a => Int -> ModInt a

Creates ModInt from an Int value taking mod.

Since: 1.0.0

new32 :: forall a. KnownNat a => Word32 -> ModInt a

Creates ModInt from a Word32 value taking mod.

Since: 1.0.0

new64 :: forall a. KnownNat a => Word64 -> ModInt a

Creates ModInt from a Word64 value taking mod.

Since: 1.0.0

Unsafe constructor

unsafeNew :: KnownNat a => Word32 -> ModInt a

Creates ModInt without taking mod. It is the function for constant-factor speedup.

Constraints

• \(0 \leq x \lt \mathrm{mod}\) (not asserted at runtime)

Since: 1.0.0

Accessors

Modulus value

modulus :: forall a. KnownNat a => ModInt a -> Int

Retrieve the mod from a ModInt object.

Complecity

• \(O(1)\)

Since: 1.0.0

Internal value

val :: KnownNat a => ModInt a -> Int

Returns the internal value converted to Int.

Complecity

• \(O(1)\)

Since: 1.0.0

val32 :: KnownNat a => ModInt a -> Word32

Returns the internal value as Word32 without type conversion. It is the function for constant-factor speedup.

Complecity

• \(O(1)\)

Since: 1.0.0

val64 :: KnownNat a => ModInt a -> Word64

Returns the internal value converted to Word32.

Complecity

• \(O(1)\)

Since: 1.0.0

Operators

pow :: forall a. (HasCallStack, KnownNat a) => ModInt a -> Int -> ModInt a

Returns \(x^n\). The implementation is a bit more efficient than ^.

Constraints

• \(0 \le n\)

Complexity

• \(O(\log n)\)

Since: 1.0.0

inv :: forall a. (HasCallStack, Modulus a) => ModInt a -> ModInt a

Returns \(y\) with \(xy \equiv 1\).

Constraints

• gcd(val x, modulus x) == 1.

Complexity

• \(O(\log \mathrm{mod})\)

Since: 1.0.0