ac-library-hs-1.1.0.0: Data structures and algorithms
Safe HaskellSafe-Inferred
LanguageGHC2021

AtCoder.ModInt

Description

It is the structure 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.

Example

Expand

It is often convenient to define a type alias of ModInt for a specific modulus value:

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

>>> modInt 1000000000 / modInt 3
666081451

Major changes from the original ac-library

  • StaticModInt is renamed to ModInt.
  • DynamicModInt is removed.

Since: 1.0.0.0

Synopsis

Modulus

class KnownNat a => Modulus a where Source #

KnownNat with meta information used for modulus.

Since: 1.0.0.0

Minimal complete definition

isPrimeModulus

Methods

isPrimeModulus :: Proxy# a -> Bool Source #

Returns if the modulus is a prime value.

Since: 1.0.0.0

primitiveRootModulus :: Proxy# a -> Int Source #

Returns the primitive root of the modulus value. Note that the default implementation is slow and the value should be hard-coded.

Since: 1.0.0.0

Instances

Instances details
Modulus 167772161 Source #

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

Since: 1.0.0.0

Instance details

Defined in AtCoder.ModInt

Methods

isPrimeModulus :: Proxy# 167772161 -> Bool Source #

primitiveRootModulus :: Proxy# 167772161 -> Int Source #

Modulus 469762049 Source #

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

Since: 1.0.0.0

Instance details

Defined in AtCoder.ModInt

Methods

isPrimeModulus :: Proxy# 469762049 -> Bool Source #

primitiveRootModulus :: Proxy# 469762049 -> Int Source #

Modulus 754974721 Source #

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

Since: 1.0.0.0

Instance details

Defined in AtCoder.ModInt

Methods

isPrimeModulus :: Proxy# 754974721 -> Bool Source #

primitiveRootModulus :: Proxy# 754974721 -> Int Source #

Modulus 998244353 Source #

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

Since: 1.0.0.0

Instance details

Defined in AtCoder.ModInt

Methods

isPrimeModulus :: Proxy# 998244353 -> Bool Source #

primitiveRootModulus :: Proxy# 998244353 -> Int Source #

Modulus 1000000007 Source #

It used to be used in contest problems.

Since: 1.0.0.0

Instance details

Defined in AtCoder.ModInt

Methods

isPrimeModulus :: Proxy# 1000000007 -> Bool Source #

primitiveRootModulus :: Proxy# 1000000007 -> Int Source #

Modulus 2147483647 Source #

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

Since: 1.0.0.0

Instance details

Defined in AtCoder.ModInt

Methods

isPrimeModulus :: Proxy# 2147483647 -> Bool Source #

primitiveRootModulus :: Proxy# 2147483647 -> Int Source #

type ModInt998244353 = ModInt 998244353 Source #

Since: 1.0.0.0

type ModInt1000000007 = ModInt 1000000007 Source #

Since: 1.0.0.0

Helpers

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

Retrieves the Int value from a KnownNat.

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

Since: 1.0.0.0

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

Retrieves the Int value from a KnownNat.

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

Since: 1.0.0.0

ModInt

newtype ModInt a Source #

Word32 value that treats the modular arithmetic.

Constructors

ModInt 

Fields

Instances

Instances details
Vector Vector (ModInt a) Source #

Since: 1.0.0.0

Instance details

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) Source #

Since: 1.0.0.0

Instance details

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) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.ModInt

Methods

minBound :: ModInt p #

maxBound :: ModInt p #

KnownNat p => Enum (ModInt p) Source #

Since: 1.0.0.0

Instance details

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) Source #

Since: 1.0.0.0

Instance details

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) Source #

Since: 1.0.0.0

Instance details

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) Source #

Since: 1.0.0.0

Instance details

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) Source #

Since: 1.0.0.0

Instance details

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) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.ModInt

Methods

toRational :: ModInt p -> Rational #

Show (ModInt a) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.ModInt

Methods

showsPrec :: Int -> ModInt a -> ShowS #

show :: ModInt a -> String #

showList :: [ModInt a] -> ShowS #

Eq (ModInt a) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.ModInt

Methods

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

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

Ord (ModInt a) Source #

Since: 1.0.0.0

Instance details

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) Source #

Since: 1.0.0.0

Instance details

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) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.ModInt

newtype MVector s (ModInt a) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.ModInt

newtype MVector s (ModInt a) = MV_ModInt (MVector s Word32)
newtype Vector (ModInt a) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.ModInt

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

Constructors

Safe constructors

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

Creates a ModInt from an Int value taking the mod.

Since: 1.0.0.0

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

Creates a ModInt from a Word32 value taking the mod.

Since: 1.0.0.0

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

Creates a ModInt from a Word64 value taking the mod.

Since: 1.0.0.0

Unsafe constructor

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

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

Constraints

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

Since: 1.0.0.0

Accessors

Modulus value

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

Retrieve the mod from a ModInt object.

Complecity

  • \(O(1)\)

Since: 1.0.0.0

Internal value

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

Returns the internal value converted to Int.

Complecity

  • \(O(1)\)

Since: 1.0.0.0

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

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

Complecity

  • \(O(1)\)

Since: 1.0.0.0

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

Returns the internal value converted to Word32.

Complecity

  • \(O(1)\)

Since: 1.0.0.0

Operators

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

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

Constraints

  • \(0 \le n\)

Complexity

  • \(O(\log n)\)

Since: 1.0.0.0

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

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

Constraints

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

Complexity

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

Since: 1.0.0.0