Struct DynamicModInt

pub struct DynamicModInt<I> { /* private fields */ }

Represents $\mathbb{Z}/m\mathbb{Z}$ where $m$ is a dynamic value.

Corresponds to atcoder::dynamic_modint in the original ACL.

Example

use ac_library::ModInt as Mint;
use proconio::{input, source::once::OnceSource};

input! {
    from OnceSource::from("3 3 7\n"),
    a: u32,
    b: u32,
    m: u32,
}

Mint::set_modulus(m);
let a = Mint::new(a);
let b = Mint::new(b);

println!("{}", a * b); // `2`

Implementations

impl<I: Id> DynamicModInt<I>

pub fn modulus() -> u32

Returns the modulus.

Corresponds to atcoder::dynamic_modint::mod in the original ACL.

Example

use ac_library::ModInt as Mint;

assert_eq!(998_244_353, Mint::modulus()); // default modulus

pub fn set_modulus(modulus: u32)

Sets a modulus.

Corresponds to atcoder::dynamic_modint::set_mod in the original ACL.

Constraints

• This function must be called earlier than any other operation of Self.

Example

use ac_library::ModInt as Mint;

Mint::set_modulus(7);
assert_eq!(7, Mint::modulus());

pub fn new<T: RemEuclidU32>(val: T) -> Self

Creates a new DynamicModInt.

Takes any primitive integer.

Corresponds to the constructor of atcoder::dynamic_modint in the original ACL.

pub fn raw(val: u32) -> Self

Constructs a DynamicModInt from a val < Self::modulus() without checking it.

Corresponds to atcoder::dynamic_modint::raw in the original ACL.

Constraints

• val is less than Self::modulus()

See ModIntBase::raw for more more details.

pub fn val(self) -> u32

Retruns the representative.

Corresponds to atcoder::static_modint::val in the original ACL.

pub fn pow(self, n: u64) -> Self

Returns self to the power of n.

Corresponds to atcoder::dynamic_modint::pow in the original ACL.

pub fn inv(self) -> Self

Retruns the multiplicative inverse of self.

Corresponds to atcoder::dynamic_modint::inv in the original ACL.

Panics

Panics if the multiplicative inverse does not exist.

Trait Implementations

impl<I: Id> Add<&DynamicModInt<I>> for &DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the + operator.

fn add(self, rhs: &DynamicModInt<I>) -> DynamicModInt<I>

Performs the + operation.

impl<I: Id> Add<&DynamicModInt<I>> for DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the + operator.

fn add(self, rhs: &DynamicModInt<I>) -> DynamicModInt<I>

Performs the + operation.

impl<I: Id> Add<DynamicModInt<I>> for &DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the + operator.

fn add(self, rhs: DynamicModInt<I>) -> DynamicModInt<I>

Performs the + operation.

impl<I: Id, T: RemEuclidU32> Add<T> for DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the + operator.

fn add(self, rhs: T) -> DynamicModInt<I>

Performs the + operation.

impl<I: Id> Add for DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the + operator.

fn add(self, rhs: DynamicModInt<I>) -> DynamicModInt<I>

Performs the + operation.

impl<I: Id> AddAssign<&DynamicModInt<I>> for DynamicModInt<I>

fn add_assign(&mut self, rhs: &DynamicModInt<I>)

Performs the += operation.

impl<I: Id, T: RemEuclidU32> AddAssign<T> for DynamicModInt<I>

fn add_assign(&mut self, rhs: T)

Performs the += operation.

impl<I: Id> AddAssign for DynamicModInt<I>

fn add_assign(&mut self, rhs: DynamicModInt<I>)

Performs the += operation.

impl<I: Clone> Clone for DynamicModInt<I>

fn clone(&self) -> DynamicModInt<I>

Returns a duplicate of the value.

const fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<I: Id> Debug for DynamicModInt<I>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<I: Id> Default for DynamicModInt<I>

fn default() -> Self

Returns the “default value” for a type.

impl<I: Id> Display for DynamicModInt<I>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<I: Id> Div<&DynamicModInt<I>> for &DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the / operator.

fn div(self, rhs: &DynamicModInt<I>) -> DynamicModInt<I>

Performs the / operation.

impl<I: Id> Div<&DynamicModInt<I>> for DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the / operator.

fn div(self, rhs: &DynamicModInt<I>) -> DynamicModInt<I>

Performs the / operation.

impl<I: Id> Div<DynamicModInt<I>> for &DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the / operator.

fn div(self, rhs: DynamicModInt<I>) -> DynamicModInt<I>

Performs the / operation.

impl<I: Id, T: RemEuclidU32> Div<T> for DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the / operator.

fn div(self, rhs: T) -> DynamicModInt<I>

Performs the / operation.

impl<I: Id> Div for DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the / operator.

fn div(self, rhs: DynamicModInt<I>) -> DynamicModInt<I>

Performs the / operation.

impl<I: Id> DivAssign<&DynamicModInt<I>> for DynamicModInt<I>

fn div_assign(&mut self, rhs: &DynamicModInt<I>)

Performs the /= operation.

impl<I: Id, T: RemEuclidU32> DivAssign<T> for DynamicModInt<I>

fn div_assign(&mut self, rhs: T)

Performs the /= operation.

impl<I: Id> DivAssign for DynamicModInt<I>

fn div_assign(&mut self, rhs: DynamicModInt<I>)

Performs the /= operation.

impl<I: Id, V: RemEuclidU32> From<V> for DynamicModInt<I>

fn from(from: V) -> Self

Converts to this type from the input type.

impl<I: Id> FromStr for DynamicModInt<I>

type Err = Infallible

The associated error which can be returned from parsing.

fn from_str(s: &str) -> Result<Self, Infallible>

Parses a string s to return a value of this type.

impl<I: Id> Hash for DynamicModInt<I>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<I: Id> ModIntBase for DynamicModInt<I>

These methods are implemented for the struct. You don’t need to use ModIntBase to call methods of DynamicModInt.

fn modulus() -> u32

Returns the modulus.

fn raw(val: u32) -> Self

Constructs a Self from a val < Self::modulus() without checking it.

fn val(self) -> u32

Retruns the representative.

fn inv(self) -> Self

Retruns the multiplicative inverse of self.

fn new<T: RemEuclidU32>(val: T) -> Self

Creates a new Self.

fn pow(self, n: u64) -> Self

Returns self to the power of n.

impl<I: Id> Mul<&DynamicModInt<I>> for &DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the * operator.

fn mul(self, rhs: &DynamicModInt<I>) -> DynamicModInt<I>

Performs the * operation.

impl<I: Id> Mul<&DynamicModInt<I>> for DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the * operator.

fn mul(self, rhs: &DynamicModInt<I>) -> DynamicModInt<I>

Performs the * operation.

impl<I: Id> Mul<DynamicModInt<I>> for &DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the * operator.

fn mul(self, rhs: DynamicModInt<I>) -> DynamicModInt<I>

Performs the * operation.

impl<I: Id, T: RemEuclidU32> Mul<T> for DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the * operator.

fn mul(self, rhs: T) -> DynamicModInt<I>

Performs the * operation.

impl<I: Id> Mul for DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the * operator.

fn mul(self, rhs: DynamicModInt<I>) -> DynamicModInt<I>

Performs the * operation.

impl<I: Id> MulAssign<&DynamicModInt<I>> for DynamicModInt<I>

fn mul_assign(&mut self, rhs: &DynamicModInt<I>)

Performs the *= operation.

impl<I: Id, T: RemEuclidU32> MulAssign<T> for DynamicModInt<I>

fn mul_assign(&mut self, rhs: T)

Performs the *= operation.

impl<I: Id> MulAssign for DynamicModInt<I>

fn mul_assign(&mut self, rhs: DynamicModInt<I>)

Performs the *= operation.

impl<I: Id> Neg for &DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the - operator.

fn neg(self) -> DynamicModInt<I>

Performs the unary - operation.

impl<I: Id> Neg for DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the - operator.

fn neg(self) -> DynamicModInt<I>

Performs the unary - operation.

impl<I: PartialEq> PartialEq for DynamicModInt<I>

fn eq(&self, other: &DynamicModInt<I>) -> bool

Tests for self and other values to be equal, and is used by ==.

const fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, I: Id> Product<&'a DynamicModInt<I>> for DynamicModInt<I>

fn product<S>(iter: S) -> Self

where S: Iterator<Item = &'a Self>,

Takes an iterator and generates Self from the elements by multiplying the items.

impl<I: Id> Product for DynamicModInt<I>

fn product<S>(iter: S) -> Self

where S: Iterator<Item = Self>,

Takes an iterator and generates Self from the elements by multiplying the items.

impl<I: Id> Sub<&DynamicModInt<I>> for &DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the - operator.

fn sub(self, rhs: &DynamicModInt<I>) -> DynamicModInt<I>

Performs the - operation.

impl<I: Id> Sub<&DynamicModInt<I>> for DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the - operator.

fn sub(self, rhs: &DynamicModInt<I>) -> DynamicModInt<I>

Performs the - operation.

impl<I: Id> Sub<DynamicModInt<I>> for &DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the - operator.

fn sub(self, rhs: DynamicModInt<I>) -> DynamicModInt<I>

Performs the - operation.

impl<I: Id, T: RemEuclidU32> Sub<T> for DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the - operator.

fn sub(self, rhs: T) -> DynamicModInt<I>

Performs the - operation.

impl<I: Id> Sub for DynamicModInt<I>

type Output = DynamicModInt<I>

The resulting type after applying the - operator.

fn sub(self, rhs: DynamicModInt<I>) -> DynamicModInt<I>

Performs the - operation.

impl<I: Id> SubAssign<&DynamicModInt<I>> for DynamicModInt<I>

fn sub_assign(&mut self, rhs: &DynamicModInt<I>)

Performs the -= operation.

impl<I: Id, T: RemEuclidU32> SubAssign<T> for DynamicModInt<I>

fn sub_assign(&mut self, rhs: T)

Performs the -= operation.

impl<I: Id> SubAssign for DynamicModInt<I>

fn sub_assign(&mut self, rhs: DynamicModInt<I>)

Performs the -= operation.

impl<'a, I: Id> Sum<&'a DynamicModInt<I>> for DynamicModInt<I>

fn sum<S>(iter: S) -> Self

where S: Iterator<Item = &'a Self>,

Takes an iterator and generates Self from the elements by “summing up” the items.

impl<I: Id> Sum for DynamicModInt<I>

fn sum<S>(iter: S) -> Self

where S: Iterator<Item = Self>,

Takes an iterator and generates Self from the elements by “summing up” the items.

impl<I: Copy> Copy for DynamicModInt<I>

impl<I: Eq> Eq for DynamicModInt<I>

impl<I> StructuralPartialEq for DynamicModInt<I>