Module modint

Structs that treat the modular arithmetic.

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

use ac_library::ModInt1000000007 as Mint; // rename to whatever you want
use proconio::{input, source::once::OnceSource};

input! {
    from OnceSource::from("1000000006 2\n"),
    a: Mint,
    b: Mint,
}

println!("{}", a + b); // `1`

If the modulus is not fixed, you can use ModInt as follows.

use ac_library::ModInt as Mint; // rename to whatever you want
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`

Major changes from the original ACL

• Converted the struct names to PascalCase.
• Renamed mod → modulus.
• Moduli are u32, not i32.
• Each Id does not have a identifier number. Instead, they explicitly own &'static LocalKey<RefCell<Barrett>>.
• The type of the argument of pow is u64, not i64.
• Modints implement FromStr and Display. Modints in the original ACL don’t have operator<< or operator>>.

Structs

Barrett

Pair of $m$ and $\lceil 2^{64}/m \rceil$.

ButterflyCache

Cache for butterfly operations.

DynamicModInt

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

StaticModInt

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

Enums

DefaultId

Mod998244353

Represents $998244353$.

Mod1000000007

Represents $1000000007$.

Traits

Id

ModIntBase

A trait for StaticModInt and DynamicModInt.

Modulus

Represents a modulus.

RemEuclidU32

A trait for {StaticModInt, DynamicModInt, ModIntBase}::new.

Type Aliases

ModInt

ModInt998244353

ModInt1000000007