ac-library-hs-0.1.0.0: Data structures and algorithms
Safe HaskellNone
LanguageGHC2021

AtCoder.ModInt

Description

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

Synopsis

Modulus

class KnownNat a => Modulus (a :: Nat) 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

Instances details
Modulus 167772161 #

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

Since: 1.0.0

Instance details

Defined in AtCoder.ModInt

Methods

isPrimeModulus :: Proxy# 167772161 -> Bool #

primitiveRootModulus :: Proxy# 167772161 -> Int #

Modulus 469762049 #

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

Since: 1.0.0

Instance details

Defined in AtCoder.ModInt

Methods

isPrimeModulus :: Proxy# 469762049 -> Bool #

primitiveRootModulus :: Proxy# 469762049 -> Int #

Modulus 754974721 #

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

Since: 1.0.0

Instance details

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

Instance details

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

Instance details

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

Instance details

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 :: Nat). KnownNat a => Proxy a -> Int #

Retrieves Int from KnownNat.

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

Since: 1.0.0

modVal# :: forall (a :: Nat). 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 :: k) #

Word32 value that treats the modula arithmetic.

Constructors

ModInt 

Fields

Instances

Instances details
Vector Vector (ModInt a) #
  • - @since 1.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) #
  • - @since 1.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) #
  • - @since 1.0.0
Instance details

Defined in AtCoder.ModInt

Methods

minBound :: ModInt p #

maxBound :: ModInt p #

KnownNat p => Enum (ModInt p) #
  • - @since 1.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) #
  • - @since 1.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) # 
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) #
  • - @since 1.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) #
  • - @since 1.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) #
  • - @since 1.0.0
Instance details

Defined in AtCoder.ModInt

Methods

toRational :: ModInt p -> Rational #

Show (ModInt a) # 
Instance details

Defined in AtCoder.ModInt

Methods

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

show :: ModInt a -> String #

showList :: [ModInt a] -> ShowS #

Eq (ModInt a) # 
Instance details

Defined in AtCoder.ModInt

Methods

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

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

Ord (ModInt a) # 
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) # 
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) #
  • - @since 1.0.0
Instance details

Defined in AtCoder.ModInt

newtype MVector s (ModInt a) #
  • - @since 1.0.0
Instance details

Defined in AtCoder.ModInt

newtype MVector s (ModInt a) = MV_ModInt (MVector s Word32)
newtype Vector (ModInt a) #
  • - @since 1.0.0
Instance details

Defined in AtCoder.ModInt

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

Constructors

Safe constructors

new :: forall (a :: Nat). KnownNat a => Int -> ModInt a #

Creates ModInt from an Int value taking mod.

Since: 1.0.0

new32 :: forall (a :: Nat). KnownNat a => Word32 -> ModInt a #

Creates ModInt from a Word32 value taking mod.

Since: 1.0.0

new64 :: forall (a :: Nat). KnownNat a => Word32 -> ModInt a #

Creates ModInt from a Word64 value taking mod.

Since: 1.0.0

Unsafe constructor

unsafeNew :: forall (a :: Nat). 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 :: Nat). KnownNat a => ModInt a -> Int #

Retrieve the mod from a ModInt object.

Complecity

  • \(O(1)\)

Since: 1.0.0

Internal value

val :: forall (a :: Nat). KnownNat a => ModInt a -> Int #

Returns the internal value converted to Int.

Complecity

  • \(O(1)\)

Since: 1.0.0

val32 :: forall (a :: Nat). 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 :: forall (a :: Nat). KnownNat a => ModInt a -> Word32 #

Returns the internal value converted to Word32.

Complecity

  • \(O(1)\)

Since: 1.0.0

Operators

pow :: forall (a :: Nat). (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 :: Nat). (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