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

AtCoder.Extra.ModInt64

Description

ModInt for 64 bit modulus values with Montgomery modular multiplication.

Constraints

  • The modulus value must be an odd number.

Since: 1.2.6.0

Synopsis

ModInt64

newtype ModInt64 (a :: k) Source #

Word64 value that treats the modular arithmetic.

Constraints

  • The modulus value must be an odd number.

Since: 1.2.6.0

Constructors

ModInt64 

Fields

Instances

Instances details
Vector Vector (ModInt64 a) Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.ModInt64

Methods

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

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

basicLength :: Vector (ModInt64 a) -> Int

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

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

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

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

MVector MVector (ModInt64 a) Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.ModInt64

Methods

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

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

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

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

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

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

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

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

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

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

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

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

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

KnownNat p => Bounded (ModInt64 p) Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.ModInt64

Methods

minBound :: ModInt64 p #

maxBound :: ModInt64 p #

KnownNat p => Enum (ModInt64 p) Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.ModInt64

Methods

succ :: ModInt64 p -> ModInt64 p #

pred :: ModInt64 p -> ModInt64 p #

toEnum :: Int -> ModInt64 p #

fromEnum :: ModInt64 p -> Int #

enumFrom :: ModInt64 p -> [ModInt64 p] #

enumFromThen :: ModInt64 p -> ModInt64 p -> [ModInt64 p] #

enumFromTo :: ModInt64 p -> ModInt64 p -> [ModInt64 p] #

enumFromThenTo :: ModInt64 p -> ModInt64 p -> ModInt64 p -> [ModInt64 p] #

KnownNat p => Num (ModInt64 p) Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.ModInt64

Methods

(+) :: ModInt64 p -> ModInt64 p -> ModInt64 p #

(-) :: ModInt64 p -> ModInt64 p -> ModInt64 p #

(*) :: ModInt64 p -> ModInt64 p -> ModInt64 p #

negate :: ModInt64 p -> ModInt64 p #

abs :: ModInt64 p -> ModInt64 p #

signum :: ModInt64 p -> ModInt64 p #

fromInteger :: Integer -> ModInt64 p #

KnownNat a => Read (ModInt64 a) Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.ModInt64

Methods

readsPrec :: Int -> ReadS (ModInt64 a) #

readList :: ReadS [ModInt64 a] #

readPrec :: ReadPrec (ModInt64 a) #

readListPrec :: ReadPrec [ModInt64 a] #

KnownNat p => Fractional (ModInt64 p) Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.ModInt64

Methods

(/) :: ModInt64 p -> ModInt64 p -> ModInt64 p #

recip :: ModInt64 p -> ModInt64 p #

fromRational :: Rational -> ModInt64 p #

KnownNat p => Integral (ModInt64 p) Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.ModInt64

Methods

quot :: ModInt64 p -> ModInt64 p -> ModInt64 p #

rem :: ModInt64 p -> ModInt64 p -> ModInt64 p #

div :: ModInt64 p -> ModInt64 p -> ModInt64 p #

mod :: ModInt64 p -> ModInt64 p -> ModInt64 p #

quotRem :: ModInt64 p -> ModInt64 p -> (ModInt64 p, ModInt64 p) #

divMod :: ModInt64 p -> ModInt64 p -> (ModInt64 p, ModInt64 p) #

toInteger :: ModInt64 p -> Integer #

KnownNat p => Real (ModInt64 p) Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.ModInt64

Methods

toRational :: ModInt64 p -> Rational #

KnownNat a => Show (ModInt64 a) Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.ModInt64

Methods

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

show :: ModInt64 a -> String #

showList :: [ModInt64 a] -> ShowS #

KnownNat a => Eq (ModInt64 a) Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.ModInt64

Methods

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

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

KnownNat a => Ord (ModInt64 a) Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.ModInt64

Methods

compare :: ModInt64 a -> ModInt64 a -> Ordering #

(<) :: ModInt64 a -> ModInt64 a -> Bool #

(<=) :: ModInt64 a -> ModInt64 a -> Bool #

(>) :: ModInt64 a -> ModInt64 a -> Bool #

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

max :: ModInt64 a -> ModInt64 a -> ModInt64 a #

min :: ModInt64 a -> ModInt64 a -> ModInt64 a #

Prim (ModInt64 a) Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.ModInt64

Methods

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

sizeOf# :: ModInt64 a -> Int# #

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

alignment# :: ModInt64 a -> Int# #

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

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

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

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

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

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

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

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

Unbox (ModInt64 a) Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.ModInt64

newtype MVector s (ModInt64 a) Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.ModInt64

newtype MVector s (ModInt64 a) = MV_ModInt64 (MVector s Word64)
newtype Vector (ModInt64 a) Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.ModInt64

newtype Vector (ModInt64 a) = V_ModInt64 (Vector Word64)

Constructors

Safe constructors

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

\(O(1)\) Creates a ModInt64 from an Int value taking the mod.

Since: 1.2.6.0

new64 :: forall (a :: Nat). KnownNat a => Word64 -> ModInt64 a Source #

\(O(1)\) Creates a ModInt64 from a Word64 value taking the mod.

Since: 1.2.6.0

Unsafe constructor

unsafeNew :: forall (a :: Nat). KnownNat a => Word64 -> ModInt64 a Source #

\(O(1)\) Creates ModInt64 from a Montgomery form with no validation.

Since: 1.2.6.0

Accessors

Modulus value

modulus :: forall (a :: Nat). KnownNat a => ModInt64 a -> Int Source #

\(O(1)\) Retrieve the modulus from a ModInt64 object.

Complexity

  • \(O(1)\)

Since: 1.2.6.0

Internal value

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

\(O(1)\) Returns the internal value as an Int.

Complexity

  • \(O(1)\)

Since: 1.2.6.0

val64 :: forall (a :: Nat). KnownNat a => ModInt64 a -> Word64 Source #

\(O(1)\) Returns the internal value as a Word64.

Complexity

  • \(O(1)\)

Since: 1.2.6.0

Operators

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

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

Constraints

  • \(0 \le n\)

Since: 1.2.6.0

inv :: forall (a :: Nat). (HasCallStack, KnownNat a) => ModInt64 a -> ModInt64 a Source #

Returns \(y\) such that \(xy \equiv 1 \bmod m\) holds.

Constraints

  • The value must not be zero.

Since: 1.2.6.0