Submission #28841591
Source Code Expand
use fenwicktree::*;
use modint::ModInt1000000007 as ModInt;
use std::collections::{BTreeMap, BTreeSet};
use proconio::input;
fn compress(a: &[usize]) -> BTreeMap<usize, usize> {
a.iter()
.copied()
.collect::<BTreeSet<_>>()
.into_iter()
.enumerate()
.fold(BTreeMap::new(), |mut m, (i, k)| {
m.insert(k, i);
m
})
}
fn main() {
input! {
n: usize,
a: [usize; n],
};
let c = compress(&a);
let mut count = FenwickTree::new(n, ModInt::new(0));
let mut sum_lt = FenwickTree::new(n, ModInt::new(0));
let mut sum_gt = FenwickTree::new(n, ModInt::new(0));
for a_i in a.iter().copied() {
let c_i = *c.get(&a_i).unwrap();
let count_lt = count.sum(0, c_i);
let count_gt = count.sum(c_i + 1, n);
let lt = sum_gt.sum(0, c_i) + count_lt;
let gt = sum_lt.sum(c_i + 1, n) + count_gt;
count.add(c_i, 1);
sum_lt.add(c_i, lt);
sum_gt.add(c_i, gt);
}
let mut ans = ModInt::new(0);
for (_, c_i) in c {
ans += sum_lt.sum(c_i, c_i + 1) + sum_gt.sum(c_i, c_i + 1);
}
println!("{}", ans);
}
//https://github.com/rust-lang-ja/ac-library-rs
pub mod fenwicktree {
// Reference: https://en.wikipedia.org/wiki/Fenwick_tree
pub struct FenwickTree<T> {
n: usize,
ary: Vec<T>,
e: T,
}
impl<T: Clone + std::ops::AddAssign<T>> FenwickTree<T> {
pub fn new(n: usize, e: T) -> Self {
FenwickTree {
n,
ary: vec![e.clone(); n],
e,
}
}
pub fn accum(&self, mut idx: usize) -> T {
let mut sum = self.e.clone();
while idx > 0 {
sum += self.ary[idx - 1].clone();
idx &= idx - 1;
}
sum
}
/// performs data[idx] += val;
pub fn add<U: Clone>(&mut self, mut idx: usize, val: U)
where
T: std::ops::AddAssign<U>,
{
let n = self.n;
idx += 1;
while idx <= n {
self.ary[idx - 1] += val.clone();
idx += idx & idx.wrapping_neg();
}
}
/// Returns data[l] + ... + data[r - 1].
pub fn sum(&self, l: usize, r: usize) -> T
where
T: std::ops::Sub<Output = T>,
{
self.accum(r) - self.accum(l)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn fenwick_tree_works() {
let mut bit = FenwickTree::new(5, 0i64);
// [1, 2, 3, 4, 5]
for i in 0..5 {
bit.add(i, i as i64 + 1);
}
assert_eq!(bit.sum(0, 5), 15);
assert_eq!(bit.sum(0, 4), 10);
assert_eq!(bit.sum(1, 3), 5);
}
}
}
//https://github.com/rust-lang-ja/ac-library-rs
pub mod internal_math {
// remove this after dependencies has been added
#![allow(dead_code)]
use std::mem::swap;
/// # Arguments
/// * `m` `1 <= m`
///
/// # Returns
/// x mod m
/* const */
pub(crate) fn safe_mod(mut x: i64, m: i64) -> i64 {
x %= m;
if x < 0 {
x += m;
}
x
}
/// Fast modular by barrett reduction
/// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
/// NOTE: reconsider after Ice Lake
pub(crate) struct Barrett {
pub(crate) _m: u32,
pub(crate) im: u64,
}
impl Barrett {
/// # Arguments
/// * `m` `1 <= m`
/// (Note: `m <= 2^31` should also hold, which is undocumented in the original library.
/// See the [pull reqeust commment](https://github.com/rust-lang-ja/ac-library-rs/pull/3#discussion_r484661007)
/// for more details.)
pub(crate) fn new(m: u32) -> Barrett {
Barrett {
_m: m,
im: (-1i64 as u64 / m as u64).wrapping_add(1),
}
}
/// # Returns
/// `m`
pub(crate) fn umod(&self) -> u32 {
self._m
}
/// # Parameters
/// * `a` `0 <= a < m`
/// * `b` `0 <= b < m`
///
/// # Returns
/// a * b % m
#[allow(clippy::many_single_char_names)]
pub(crate) fn mul(&self, a: u32, b: u32) -> u32 {
mul_mod(a, b, self._m, self.im)
}
}
/// Calculates `a * b % m`.
///
/// * `a` `0 <= a < m`
/// * `b` `0 <= b < m`
/// * `m` `1 <= m <= 2^31`
/// * `im` = ceil(2^64 / `m`)
#[allow(clippy::many_single_char_names)]
pub(crate) fn mul_mod(a: u32, b: u32, m: u32, im: u64) -> u32 {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
let mut z = a as u64;
z *= b as u64;
let x = (((z as u128) * (im as u128)) >> 64) as u64;
let mut v = z.wrapping_sub(x.wrapping_mul(m as u64)) as u32;
if m <= v {
v = v.wrapping_add(m);
}
v
}
/// # Parameters
/// * `n` `0 <= n`
/// * `m` `1 <= m`
///
/// # Returns
/// `(x ** n) % m`
/* const */
#[allow(clippy::many_single_char_names)]
pub(crate) fn pow_mod(x: i64, mut n: i64, m: i32) -> i64 {
if m == 1 {
return 0;
}
let _m = m as u32;
let mut r: u64 = 1;
let mut y: u64 = safe_mod(x, m as i64) as u64;
while n != 0 {
if (n & 1) > 0 {
r = (r * y) % (_m as u64);
}
y = (y * y) % (_m as u64);
n >>= 1;
}
r as i64
}
/// Reference:
/// M. Forisek and J. Jancina,
/// Fast Primality Testing for Integers That Fit into a Machine Word
///
/// # Parameters
/// * `n` `0 <= n`
/* const */
pub(crate) fn is_prime(n: i32) -> bool {
let n = n as i64;
match n {
_ if n <= 1 => return false,
2 | 7 | 61 => return true,
_ if n % 2 == 0 => return false,
_ => {}
}
let mut d = n - 1;
while d % 2 == 0 {
d /= 2;
}
for &a in &[2, 7, 61] {
let mut t = d;
let mut y = pow_mod(a, t, n as i32);
while t != n - 1 && y != 1 && y != n - 1 {
y = y * y % n;
t <<= 1;
}
if y != n - 1 && t % 2 == 0 {
return false;
}
}
true
}
// omitted
// template <int n> constexpr bool is_prime = is_prime_constexpr(n);
/// # Parameters
/// * `b` `1 <= b`
///
/// # Returns
/// (g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
/* const */
#[allow(clippy::many_single_char_names)]
pub(crate) fn inv_gcd(a: i64, b: i64) -> (i64, i64) {
let a = safe_mod(a, b);
if a == 0 {
return (b, 0);
}
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
let mut s = b;
let mut t = a;
let mut m0 = 0;
let mut m1 = 1;
while t != 0 {
let u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
swap(&mut s, &mut t);
swap(&mut m0, &mut m1);
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if m0 < 0 {
m0 += b / s;
}
(s, m0)
}
/// Compile time (currently not) primitive root
/// @param m must be prime
/// @return primitive root (and minimum in now)
/* const */
pub(crate) fn primitive_root(m: i32) -> i32 {
match m {
2 => return 1,
167_772_161 => return 3,
469_762_049 => return 3,
754_974_721 => return 11,
998_244_353 => return 3,
_ => {}
}
let mut divs = [0; 20];
divs[0] = 2;
let mut cnt = 1;
let mut x = (m - 1) / 2;
while x % 2 == 0 {
x /= 2;
}
for i in (3..std::i32::MAX).step_by(2) {
if i as i64 * i as i64 > x as i64 {
break;
}
if x % i == 0 {
divs[cnt] = i;
cnt += 1;
while x % i == 0 {
x /= i;
}
}
}
if x > 1 {
divs[cnt] = x;
cnt += 1;
}
let mut g = 2;
loop {
if (0..cnt).all(|i| pow_mod(g, ((m - 1) / divs[i]) as i64, m) != 1) {
break g as i32;
}
g += 1;
}
}
// omitted
// template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
#[cfg(test)]
mod tests {
#![allow(clippy::unreadable_literal)]
#![allow(clippy::cognitive_complexity)]
use crate::internal_math::{inv_gcd, is_prime, pow_mod, primitive_root, safe_mod, Barrett};
use std::collections::HashSet;
#[test]
fn test_safe_mod() {
assert_eq!(safe_mod(0, 3), 0);
assert_eq!(safe_mod(1, 3), 1);
assert_eq!(safe_mod(2, 3), 2);
assert_eq!(safe_mod(3, 3), 0);
assert_eq!(safe_mod(4, 3), 1);
assert_eq!(safe_mod(5, 3), 2);
assert_eq!(safe_mod(73, 11), 7);
assert_eq!(safe_mod(2306249155046129918, 6620319213327), 1374210749525);
assert_eq!(safe_mod(-1, 3), 2);
assert_eq!(safe_mod(-2, 3), 1);
assert_eq!(safe_mod(-3, 3), 0);
assert_eq!(safe_mod(-4, 3), 2);
assert_eq!(safe_mod(-5, 3), 1);
assert_eq!(safe_mod(-7170500492396019511, 777567337), 333221848);
}
#[test]
fn test_barrett() {
let b = Barrett::new(7);
assert_eq!(b.umod(), 7);
assert_eq!(b.mul(2, 3), 6);
assert_eq!(b.mul(4, 6), 3);
assert_eq!(b.mul(5, 0), 0);
let b = Barrett::new(998244353);
assert_eq!(b.umod(), 998244353);
assert_eq!(b.mul(2, 3), 6);
assert_eq!(b.mul(3141592, 653589), 919583920);
assert_eq!(b.mul(323846264, 338327950), 568012980);
// make `z - x * self._m as u64` overflow.
// Thanks @koba-e964 (at https://github.com/rust-lang-ja/ac-library-rs/pull/3#discussion_r484932161)
let b = Barrett::new(2147483647);
assert_eq!(b.umod(), 2147483647);
assert_eq!(b.mul(1073741824, 2147483645), 2147483646);
}
#[test]
fn test_pow_mod() {
assert_eq!(pow_mod(0, 0, 1), 0);
assert_eq!(pow_mod(0, 0, 3), 1);
assert_eq!(pow_mod(0, 0, 723), 1);
assert_eq!(pow_mod(0, 0, 998244353), 1);
assert_eq!(pow_mod(0, 0, i32::max_value()), 1);
assert_eq!(pow_mod(0, 1, 1), 0);
assert_eq!(pow_mod(0, 1, 3), 0);
assert_eq!(pow_mod(0, 1, 723), 0);
assert_eq!(pow_mod(0, 1, 998244353), 0);
assert_eq!(pow_mod(0, 1, i32::max_value()), 0);
assert_eq!(pow_mod(0, i64::max_value(), 1), 0);
assert_eq!(pow_mod(0, i64::max_value(), 3), 0);
assert_eq!(pow_mod(0, i64::max_value(), 723), 0);
assert_eq!(pow_mod(0, i64::max_value(), 998244353), 0);
assert_eq!(pow_mod(0, i64::max_value(), i32::max_value()), 0);
assert_eq!(pow_mod(1, 0, 1), 0);
assert_eq!(pow_mod(1, 0, 3), 1);
assert_eq!(pow_mod(1, 0, 723), 1);
assert_eq!(pow_mod(1, 0, 998244353), 1);
assert_eq!(pow_mod(1, 0, i32::max_value()), 1);
assert_eq!(pow_mod(1, 1, 1), 0);
assert_eq!(pow_mod(1, 1, 3), 1);
assert_eq!(pow_mod(1, 1, 723), 1);
assert_eq!(pow_mod(1, 1, 998244353), 1);
assert_eq!(pow_mod(1, 1, i32::max_value()), 1);
assert_eq!(pow_mod(1, i64::max_value(), 1), 0);
assert_eq!(pow_mod(1, i64::max_value(), 3), 1);
assert_eq!(pow_mod(1, i64::max_value(), 723), 1);
assert_eq!(pow_mod(1, i64::max_value(), 998244353), 1);
assert_eq!(pow_mod(1, i64::max_value(), i32::max_value()), 1);
assert_eq!(pow_mod(i64::max_value(), 0, 1), 0);
assert_eq!(pow_mod(i64::max_value(), 0, 3), 1);
assert_eq!(pow_mod(i64::max_value(), 0, 723), 1);
assert_eq!(pow_mod(i64::max_value(), 0, 998244353), 1);
assert_eq!(pow_mod(i64::max_value(), 0, i32::max_value()), 1);
assert_eq!(pow_mod(i64::max_value(), i64::max_value(), 1), 0);
assert_eq!(pow_mod(i64::max_value(), i64::max_value(), 3), 1);
assert_eq!(pow_mod(i64::max_value(), i64::max_value(), 723), 640);
assert_eq!(
pow_mod(i64::max_value(), i64::max_value(), 998244353),
683296792
);
assert_eq!(
pow_mod(i64::max_value(), i64::max_value(), i32::max_value()),
1
);
assert_eq!(pow_mod(2, 3, 1_000_000_007), 8);
assert_eq!(pow_mod(5, 7, 1_000_000_007), 78125);
assert_eq!(pow_mod(123, 456, 1_000_000_007), 565291922);
}
#[test]
fn test_is_prime() {
assert!(!is_prime(0));
assert!(!is_prime(1));
assert!(is_prime(2));
assert!(is_prime(3));
assert!(!is_prime(4));
assert!(is_prime(5));
assert!(!is_prime(6));
assert!(is_prime(7));
assert!(!is_prime(8));
assert!(!is_prime(9));
// assert!(is_prime(57));
assert!(!is_prime(57));
assert!(!is_prime(58));
assert!(is_prime(59));
assert!(!is_prime(60));
assert!(is_prime(61));
assert!(!is_prime(62));
assert!(!is_prime(701928443));
assert!(is_prime(998244353));
assert!(!is_prime(1_000_000_000));
assert!(is_prime(1_000_000_007));
assert!(is_prime(i32::max_value()));
}
#[test]
fn test_is_prime_sieve() {
let n = 1_000_000;
let mut prime = vec![true; n];
prime[0] = false;
prime[1] = false;
for i in 0..n {
assert_eq!(prime[i], is_prime(i as i32));
if prime[i] {
for j in (2 * i..n).step_by(i) {
prime[j] = false;
}
}
}
}
#[test]
fn test_inv_gcd() {
for &(a, b, g) in &[
(0, 1, 1),
(0, 4, 4),
(0, 7, 7),
(2, 3, 1),
(-2, 3, 1),
(4, 6, 2),
(-4, 6, 2),
(13, 23, 1),
(57, 81, 3),
(12345, 67890, 15),
(-3141592 * 6535, 3141592 * 8979, 3141592),
(i64::max_value(), i64::max_value(), i64::max_value()),
(i64::min_value(), i64::max_value(), 1),
] {
let (g_, x) = inv_gcd(a, b);
assert_eq!(g, g_);
let b_ = b as i128;
assert_eq!(((x as i128 * a as i128) % b_ + b_) % b_, g as i128 % b_);
}
}
#[test]
fn test_primitive_root() {
for &p in &[
2,
3,
5,
7,
233,
200003,
998244353,
1_000_000_007,
i32::max_value(),
] {
assert!(is_prime(p));
let g = primitive_root(p);
if p != 2 {
assert_ne!(g, 1);
}
let q = p - 1;
for i in (2..i32::max_value()).take_while(|i| i * i <= q) {
if q % i != 0 {
break;
}
for &r in &[i, q / i] {
assert_ne!(pow_mod(g as i64, r as i64, p), 1);
}
}
assert_eq!(pow_mod(g as i64, q as i64, p), 1);
if p < 1_000_000 {
assert_eq!(
(0..p - 1)
.scan(1, |i, _| {
*i = *i * g % p;
Some(*i)
})
.collect::<HashSet<_>>()
.len() as i32,
p - 1
);
}
}
}
}
}
pub mod 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_rs::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_rs::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>>`.
//!
//! [`ModInt1000000007`]: ./type.ModInt1000000007.html
//! [`ModInt998244353`]: ./type.ModInt998244353.html
//! [`ModInt`]: ./type.ModInt.html
use crate::internal_math;
use std::{
cell::RefCell,
convert::{Infallible, TryInto as _},
fmt,
hash::{Hash, Hasher},
iter::{Product, Sum},
marker::PhantomData,
ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
str::FromStr,
sync::atomic::{self, AtomicU32, AtomicU64},
thread::LocalKey,
};
pub type ModInt1000000007 = StaticModInt<Mod1000000007>;
pub type ModInt998244353 = StaticModInt<Mod998244353>;
pub type ModInt = DynamicModInt<DefaultId>;
/// Represents _ℤ/mℤ_ where _m_ is a constant value.
///
/// Corresponds to `atcoder::static_modint` in the original ACL.
///
/// # Example
///
/// ```
/// use ac_library_rs::ModInt1000000007 as Mint;
/// use proconio::{input, source::once::OnceSource};
///
/// input! {
/// from OnceSource::from("1000000006 2\n"),
/// a: Mint,
/// b: Mint,
/// }
///
/// println!("{}", a + b); // `1`
/// ```
#[derive(Copy, Clone, Eq, PartialEq)]
#[repr(transparent)]
pub struct StaticModInt<M> {
val: u32,
phantom: PhantomData<fn() -> M>,
}
impl<M: Modulus> StaticModInt<M> {
/// Returns the modulus, which is [`<M as Modulus>::VALUE`].
///
/// Corresponds to `atcoder::static_modint::mod` in the original ACL.
///
/// # Example
///
/// ```
/// use ac_library_rs::ModInt1000000007 as Mint;
///
/// assert_eq!(1_000_000_007, Mint::modulus());
/// ```
///
/// [`<M as Modulus>::VALUE`]: ../trait.Modulus.html#associatedconstant.VALUE
#[inline(always)]
pub fn modulus() -> u32 {
M::VALUE
}
/// Creates a new `StaticModInt`.
///
/// Takes [any primitive integer].
///
/// Corresponds to the constructor of `atcoder::static_modint` in the original ACL.
///
/// [any primitive integer]: ../trait.RemEuclidU32.html
#[inline]
pub fn new<T: RemEuclidU32>(val: T) -> Self {
Self::raw(val.rem_euclid_u32(M::VALUE))
}
/// Constructs a `StaticModInt` from a `val < Self::modulus()` without checking it.
///
/// Corresponds to `atcoder::static_modint::raw` in the original ACL.
///
/// # Constraints
///
/// - `val` is less than `Self::modulus()`
///
/// See [`ModIntBase::raw`] for more more details.
///
/// [`ModIntBase::raw`]: ./trait.ModIntBase.html#tymethod.raw
#[inline]
pub fn raw(val: u32) -> Self {
Self {
val,
phantom: PhantomData,
}
}
/// Retruns the representative.
///
/// Corresponds to `atcoder::static_modint::val` in the original ACL.
#[inline]
pub fn val(self) -> u32 {
self.val
}
/// Returns `self` to the power of `n`.
///
/// Corresponds to `atcoder::static_modint::pow` in the original ACL.
#[inline]
pub fn pow(self, n: u64) -> Self {
<Self as ModIntBase>::pow(self, n)
}
/// Retruns the multiplicative inverse of `self`.
///
/// Corresponds to `atcoder::static_modint::inv` in the original ACL.
///
/// # Panics
///
/// Panics if the multiplicative inverse does not exist.
#[inline]
pub fn inv(self) -> Self {
if M::HINT_VALUE_IS_PRIME {
if self.val() == 0 {
panic!("attempt to divide by zero");
}
debug_assert!(
internal_math::is_prime(M::VALUE.try_into().unwrap()),
"{} is not a prime number",
M::VALUE,
);
self.pow((M::VALUE - 2).into())
} else {
Self::inv_for_non_prime_modulus(self)
}
}
}
/// These methods are implemented for the struct.
/// You don't need to `use` `ModIntBase` to call methods of `StaticModInt`.
impl<M: Modulus> ModIntBase for StaticModInt<M> {
#[inline(always)]
fn modulus() -> u32 {
Self::modulus()
}
#[inline]
fn raw(val: u32) -> Self {
Self::raw(val)
}
#[inline]
fn val(self) -> u32 {
self.val()
}
#[inline]
fn inv(self) -> Self {
self.inv()
}
}
/// Represents a modulus.
///
/// # Example
///
/// ```
/// macro_rules! modulus {
/// ($($name:ident($value:expr, $is_prime:expr)),*) => {
/// $(
/// #[derive(Copy, Clone, Eq, PartialEq)]
/// enum $name {}
///
/// impl ac_library_rs::modint::Modulus for $name {
/// const VALUE: u32 = $value;
/// const HINT_VALUE_IS_PRIME: bool = $is_prime;
///
/// fn butterfly_cache() -> &'static ::std::thread::LocalKey<::std::cell::RefCell<::std::option::Option<ac_library_rs::modint::ButterflyCache<Self>>>> {
/// thread_local! {
/// static BUTTERFLY_CACHE: ::std::cell::RefCell<::std::option::Option<ac_library_rs::modint::ButterflyCache<$name>>> = ::std::default::Default::default();
/// }
/// &BUTTERFLY_CACHE
/// }
/// }
/// )*
/// };
/// }
///
/// use ac_library_rs::StaticModInt;
///
/// modulus!(Mod101(101, true), Mod103(103, true));
///
/// type Z101 = StaticModInt<Mod101>;
/// type Z103 = StaticModInt<Mod103>;
///
/// assert_eq!(Z101::new(101), Z101::new(0));
/// assert_eq!(Z103::new(103), Z103::new(0));
/// ```
pub trait Modulus: 'static + Copy + Eq {
const VALUE: u32;
const HINT_VALUE_IS_PRIME: bool;
fn butterfly_cache() -> &'static LocalKey<RefCell<Option<ButterflyCache<Self>>>>;
}
/// Represents _1000000007_.
#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash, Debug)]
pub enum Mod1000000007 {}
impl Modulus for Mod1000000007 {
const VALUE: u32 = 1_000_000_007;
const HINT_VALUE_IS_PRIME: bool = true;
fn butterfly_cache() -> &'static LocalKey<RefCell<Option<ButterflyCache<Self>>>> {
thread_local! {
static BUTTERFLY_CACHE: RefCell<Option<ButterflyCache<Mod1000000007>>> = RefCell::default();
}
&BUTTERFLY_CACHE
}
}
/// Represents _998244353_.
#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash, Debug)]
pub enum Mod998244353 {}
impl Modulus for Mod998244353 {
const VALUE: u32 = 998_244_353;
const HINT_VALUE_IS_PRIME: bool = true;
fn butterfly_cache() -> &'static LocalKey<RefCell<Option<ButterflyCache<Self>>>> {
thread_local! {
static BUTTERFLY_CACHE: RefCell<Option<ButterflyCache<Mod998244353>>> = RefCell::default();
}
&BUTTERFLY_CACHE
}
}
/// Cache for butterfly operations.
pub struct ButterflyCache<M> {
pub(crate) sum_e: Vec<StaticModInt<M>>,
pub(crate) sum_ie: Vec<StaticModInt<M>>,
}
/// Represents _ℤ/mℤ_ where _m_ is a dynamic value.
///
/// Corresponds to `atcoder::dynamic_modint` in the original ACL.
///
/// # Example
///
/// ```
/// use ac_library_rs::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`
/// ```
#[derive(Copy, Clone, Eq, PartialEq)]
#[repr(transparent)]
pub struct DynamicModInt<I> {
val: u32,
phantom: PhantomData<fn() -> I>,
}
impl<I: Id> DynamicModInt<I> {
/// Returns the modulus.
///
/// Corresponds to `atcoder::dynamic_modint::mod` in the original ACL.
///
/// # Example
///
/// ```
/// use ac_library_rs::ModInt as Mint;
///
/// assert_eq!(998_244_353, Mint::modulus()); // default modulus
/// ```
#[inline]
pub fn modulus() -> u32 {
I::companion_barrett().umod()
}
/// 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_rs::ModInt as Mint;
///
/// Mint::set_modulus(7);
/// assert_eq!(7, Mint::modulus());
/// ```
#[inline]
pub fn set_modulus(modulus: u32) {
if modulus == 0 {
panic!("the modulus must not be 0");
}
I::companion_barrett().update(modulus);
}
/// Creates a new `DynamicModInt`.
///
/// Takes [any primitive integer].
///
/// Corresponds to the constructor of `atcoder::dynamic_modint` in the original ACL.
///
/// [any primitive integer]: ../trait.RemEuclidU32.html
#[inline]
pub fn new<T: RemEuclidU32>(val: T) -> Self {
<Self as ModIntBase>::new(val)
}
/// 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.
///
/// [`ModIntBase::raw`]: ./trait.ModIntBase.html#tymethod.raw
#[inline]
pub fn raw(val: u32) -> Self {
Self {
val,
phantom: PhantomData,
}
}
/// Retruns the representative.
///
/// Corresponds to `atcoder::static_modint::val` in the original ACL.
#[inline]
pub fn val(self) -> u32 {
self.val
}
/// Returns `self` to the power of `n`.
///
/// Corresponds to `atcoder::dynamic_modint::pow` in the original ACL.
#[inline]
pub fn pow(self, n: u64) -> Self {
<Self as ModIntBase>::pow(self, n)
}
/// 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.
#[inline]
pub fn inv(self) -> Self {
Self::inv_for_non_prime_modulus(self)
}
}
/// These methods are implemented for the struct.
/// You don't need to `use` `ModIntBase` to call methods of `DynamicModInt`.
impl<I: Id> ModIntBase for DynamicModInt<I> {
#[inline]
fn modulus() -> u32 {
Self::modulus()
}
#[inline]
fn raw(val: u32) -> Self {
Self::raw(val)
}
#[inline]
fn val(self) -> u32 {
self.val()
}
#[inline]
fn inv(self) -> Self {
self.inv()
}
}
pub trait Id: 'static + Copy + Eq {
fn companion_barrett() -> &'static Barrett;
}
#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash, Debug)]
pub enum DefaultId {}
impl Id for DefaultId {
fn companion_barrett() -> &'static Barrett {
static BARRETT: Barrett = Barrett::default();
&BARRETT
}
}
/// Pair of _m_ and _ceil(2⁶⁴/m)_.
pub struct Barrett {
m: AtomicU32,
im: AtomicU64,
}
impl Barrett {
/// Creates a new `Barrett`.
#[inline]
pub const fn new(m: u32) -> Self {
Self {
m: AtomicU32::new(m),
im: AtomicU64::new((-1i64 as u64 / m as u64).wrapping_add(1)),
}
}
#[inline]
const fn default() -> Self {
Self::new(998_244_353)
}
#[inline]
fn update(&self, m: u32) {
let im = (-1i64 as u64 / m as u64).wrapping_add(1);
self.m.store(m, atomic::Ordering::SeqCst);
self.im.store(im, atomic::Ordering::SeqCst);
}
#[inline]
fn umod(&self) -> u32 {
self.m.load(atomic::Ordering::SeqCst)
}
#[inline]
fn mul(&self, a: u32, b: u32) -> u32 {
let m = self.m.load(atomic::Ordering::SeqCst);
let im = self.im.load(atomic::Ordering::SeqCst);
internal_math::mul_mod(a, b, m, im)
}
}
impl Default for Barrett {
#[inline]
fn default() -> Self {
Self::default()
}
}
/// A trait for [`StaticModInt`] and [`DynamicModInt`].
///
/// Corresponds to `atcoder::internal::modint_base` in the original ACL.
///
/// [`StaticModInt`]: ../struct.StaticModInt.html
/// [`DynamicModInt`]: ../struct.DynamicModInt.html
pub trait ModIntBase:
Default
+ FromStr
+ From<i8>
+ From<i16>
+ From<i32>
+ From<i64>
+ From<i128>
+ From<isize>
+ From<u8>
+ From<u16>
+ From<u32>
+ From<u64>
+ From<u128>
+ From<usize>
+ Copy
+ Eq
+ Hash
+ fmt::Display
+ fmt::Debug
+ Neg<Output = Self>
+ Add<Output = Self>
+ Sub<Output = Self>
+ Mul<Output = Self>
+ Div<Output = Self>
+ AddAssign
+ SubAssign
+ MulAssign
+ DivAssign
{
/// Returns the modulus.
///
/// Corresponds to `atcoder::static_modint::mod` and `atcoder::dynamic_modint::mod` in the original ACL.
///
/// # Example
///
/// ```
/// use ac_library_rs::modint::ModIntBase;
///
/// fn f<Z: ModIntBase>() {
/// let _: u32 = Z::modulus();
/// }
/// ```
fn modulus() -> u32;
/// Constructs a `Self` from a `val < Self::modulus()` without checking it.
///
/// Corresponds to `atcoder::static_modint::raw` and `atcoder::dynamic_modint::raw` in the original ACL.
///
/// # Constraints
///
/// - `val` is less than `Self::modulus()`
///
/// **Note that all operations assume that inner values are smaller than the modulus.**
/// If `val` is greater than or equal to `Self::modulus()`, the behaviors are not defined.
///
/// ```should_panic
/// use ac_library_rs::ModInt1000000007 as Mint;
///
/// let x = Mint::raw(1_000_000_007);
/// let y = x + x;
/// assert_eq!(0, y.val());
/// ```
///
/// ```text
/// thread 'main' panicked at 'assertion failed: `(left == right)`
/// left: `0`,
/// right: `1000000007`', src/modint.rs:8:1
/// note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
/// ```
///
/// # Example
///
/// ```
/// use ac_library_rs::modint::ModIntBase;
///
/// fn f<Z: ModIntBase>() -> Z {
/// debug_assert!(Z::modulus() >= 100);
///
/// let mut acc = Z::new(0);
/// for i in 0..100 {
/// if i % 3 == 0 {
/// // I know `i` is smaller than the modulus!
/// acc += Z::raw(i);
/// }
/// }
/// acc
/// }
/// ```
fn raw(val: u32) -> Self;
/// Retruns the representative.
///
/// Corresponds to `atcoder::static_modint::val` and `atcoder::dynamic_modint::val` in the original ACL.
///
/// # Example
///
/// ```
/// use ac_library_rs::modint::ModIntBase;
///
/// fn f<Z: ModIntBase>(x: Z) {
/// let _: u32 = x.val();
/// }
/// ```
fn val(self) -> u32;
/// Retruns the multiplicative inverse of `self`.
///
/// Corresponds to `atcoder::static_modint::inv` and `atcoder::dynamic_modint::inv` in the original ACL.
///
/// # Panics
///
/// Panics if the multiplicative inverse does not exist.
///
/// # Example
///
/// ```
/// use ac_library_rs::modint::ModIntBase;
///
/// fn f<Z: ModIntBase>(x: Z) {
/// let _: Z = x.inv();
/// }
/// ```
fn inv(self) -> Self;
/// Creates a new `Self`.
///
/// Takes [any primitive integer].
///
/// # Example
///
/// ```
/// use ac_library_rs::modint::ModIntBase;
///
/// fn f<Z: ModIntBase>() {
/// let _ = Z::new(1u32);
/// let _ = Z::new(1usize);
/// let _ = Z::new(-1i64);
/// }
/// ```
///
/// [any primitive integer]: ../trait.RemEuclidU32.html
#[inline]
fn new<T: RemEuclidU32>(val: T) -> Self {
Self::raw(val.rem_euclid_u32(Self::modulus()))
}
/// Returns `self` to the power of `n`.
///
/// Corresponds to `atcoder::static_modint::pow` and `atcoder::dynamic_modint::pow` in the original ACL.
///
/// # Example
///
/// ```
/// use ac_library_rs::modint::ModIntBase;
///
/// fn f<Z: ModIntBase>() {
/// let _: Z = Z::new(2).pow(3);
/// }
/// ```
#[inline]
fn pow(self, mut n: u64) -> Self {
let mut x = self;
let mut r = Self::raw(1);
while n > 0 {
if n & 1 == 1 {
r *= x;
}
x *= x;
n >>= 1;
}
r
}
}
/// A trait for `{StaticModInt, DynamicModInt, ModIntBase}::new`.
pub trait RemEuclidU32 {
/// Calculates `self` _mod_ `modulus` losslessly.
fn rem_euclid_u32(self, modulus: u32) -> u32;
}
macro_rules! impl_rem_euclid_u32_for_small_signed {
($($ty:tt),*) => {
$(
impl RemEuclidU32 for $ty {
#[inline]
fn rem_euclid_u32(self, modulus: u32) -> u32 {
(self as i64).rem_euclid(i64::from(modulus)) as _
}
}
)*
}
}
impl_rem_euclid_u32_for_small_signed!(i8, i16, i32, i64, isize);
impl RemEuclidU32 for i128 {
#[inline]
fn rem_euclid_u32(self, modulus: u32) -> u32 {
self.rem_euclid(i128::from(modulus)) as _
}
}
macro_rules! impl_rem_euclid_u32_for_small_unsigned {
($($ty:tt),*) => {
$(
impl RemEuclidU32 for $ty {
#[inline]
fn rem_euclid_u32(self, modulus: u32) -> u32 {
self as u32 % modulus
}
}
)*
}
}
macro_rules! impl_rem_euclid_u32_for_large_unsigned {
($($ty:tt),*) => {
$(
impl RemEuclidU32 for $ty {
#[inline]
fn rem_euclid_u32(self, modulus: u32) -> u32 {
(self % (modulus as $ty)) as _
}
}
)*
}
}
impl_rem_euclid_u32_for_small_unsigned!(u8, u16, u32);
impl_rem_euclid_u32_for_large_unsigned!(u64, u128);
#[cfg(target_pointer_width = "32")]
impl_rem_euclid_u32_for_small_unsigned!(usize);
#[cfg(target_pointer_width = "64")]
impl_rem_euclid_u32_for_large_unsigned!(usize);
trait InternalImplementations: ModIntBase {
#[inline]
fn inv_for_non_prime_modulus(this: Self) -> Self {
let (gcd, x) = internal_math::inv_gcd(this.val().into(), Self::modulus().into());
if gcd != 1 {
panic!("the multiplicative inverse does not exist");
}
Self::new(x)
}
#[inline]
fn default_impl() -> Self {
Self::raw(0)
}
#[inline]
fn from_str_impl(s: &str) -> Result<Self, Infallible> {
Ok(s.parse::<i64>()
.map(Self::new)
.unwrap_or_else(|_| todo!("parsing as an arbitrary precision integer?")))
}
#[inline]
fn hash_impl(this: &Self, state: &mut impl Hasher) {
this.val().hash(state)
}
#[inline]
fn display_impl(this: &Self, f: &mut fmt::Formatter) -> fmt::Result {
fmt::Display::fmt(&this.val(), f)
}
#[inline]
fn debug_impl(this: &Self, f: &mut fmt::Formatter) -> fmt::Result {
fmt::Debug::fmt(&this.val(), f)
}
#[inline]
fn neg_impl(this: Self) -> Self {
Self::sub_impl(Self::raw(0), this)
}
#[inline]
fn add_impl(lhs: Self, rhs: Self) -> Self {
let modulus = Self::modulus();
let mut val = lhs.val() + rhs.val();
if val >= modulus {
val -= modulus;
}
Self::raw(val)
}
#[inline]
fn sub_impl(lhs: Self, rhs: Self) -> Self {
let modulus = Self::modulus();
let mut val = lhs.val().wrapping_sub(rhs.val());
if val >= modulus {
val = val.wrapping_add(modulus)
}
Self::raw(val)
}
fn mul_impl(lhs: Self, rhs: Self) -> Self;
#[inline]
fn div_impl(lhs: Self, rhs: Self) -> Self {
Self::mul_impl(lhs, rhs.inv())
}
}
impl<M: Modulus> InternalImplementations for StaticModInt<M> {
#[inline]
fn mul_impl(lhs: Self, rhs: Self) -> Self {
Self::raw((u64::from(lhs.val()) * u64::from(rhs.val()) % u64::from(M::VALUE)) as u32)
}
}
impl<I: Id> InternalImplementations for DynamicModInt<I> {
#[inline]
fn mul_impl(lhs: Self, rhs: Self) -> Self {
Self::raw(I::companion_barrett().mul(lhs.val, rhs.val))
}
}
macro_rules! impl_basic_traits {
() => {};
(impl <$generic_param:ident : $generic_param_bound:tt> _ for $self:ty; $($rest:tt)*) => {
impl <$generic_param: $generic_param_bound> Default for $self {
#[inline]
fn default() -> Self {
Self::default_impl()
}
}
impl <$generic_param: $generic_param_bound> FromStr for $self {
type Err = Infallible;
#[inline]
fn from_str(s: &str) -> Result<Self, Infallible> {
Self::from_str_impl(s)
}
}
impl<$generic_param: $generic_param_bound, V: RemEuclidU32> From<V> for $self {
#[inline]
fn from(from: V) -> Self {
Self::new(from)
}
}
#[allow(clippy::derive_hash_xor_eq)]
impl<$generic_param: $generic_param_bound> Hash for $self {
#[inline]
fn hash<H: Hasher>(&self, state: &mut H) {
Self::hash_impl(self, state)
}
}
impl<$generic_param: $generic_param_bound> fmt::Display for $self {
#[inline]
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
Self::display_impl(self, f)
}
}
impl<$generic_param: $generic_param_bound> fmt::Debug for $self {
#[inline]
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
Self::debug_impl(self, f)
}
}
impl<$generic_param: $generic_param_bound> Neg for $self {
type Output = $self;
#[inline]
fn neg(self) -> $self {
Self::neg_impl(self)
}
}
impl<$generic_param: $generic_param_bound> Neg for &'_ $self {
type Output = $self;
#[inline]
fn neg(self) -> $self {
<$self>::neg_impl(*self)
}
}
impl_basic_traits!($($rest)*);
};
}
impl_basic_traits! {
impl <M: Modulus> _ for StaticModInt<M> ;
impl <I: Id > _ for DynamicModInt<I>;
}
macro_rules! impl_bin_ops {
() => {};
(for<$($generic_param:ident : $generic_param_bound:tt),*> <$lhs_ty:ty> ~ <$rhs_ty:ty> -> $output:ty { { $lhs_body:expr } ~ { $rhs_body:expr } } $($rest:tt)*) => {
impl <$($generic_param: $generic_param_bound),*> Add<$rhs_ty> for $lhs_ty {
type Output = $output;
#[inline]
fn add(self, rhs: $rhs_ty) -> $output {
<$output>::add_impl(apply($lhs_body, self), apply($rhs_body, rhs))
}
}
impl <$($generic_param: $generic_param_bound),*> Sub<$rhs_ty> for $lhs_ty {
type Output = $output;
#[inline]
fn sub(self, rhs: $rhs_ty) -> $output {
<$output>::sub_impl(apply($lhs_body, self), apply($rhs_body, rhs))
}
}
impl <$($generic_param: $generic_param_bound),*> Mul<$rhs_ty> for $lhs_ty {
type Output = $output;
#[inline]
fn mul(self, rhs: $rhs_ty) -> $output {
<$output>::mul_impl(apply($lhs_body, self), apply($rhs_body, rhs))
}
}
impl <$($generic_param: $generic_param_bound),*> Div<$rhs_ty> for $lhs_ty {
type Output = $output;
#[inline]
fn div(self, rhs: $rhs_ty) -> $output {
<$output>::div_impl(apply($lhs_body, self), apply($rhs_body, rhs))
}
}
impl_bin_ops!($($rest)*);
};
}
macro_rules! impl_assign_ops {
() => {};
(for<$($generic_param:ident : $generic_param_bound:tt),*> <$lhs_ty:ty> ~= <$rhs_ty:ty> { _ ~= { $rhs_body:expr } } $($rest:tt)*) => {
impl <$($generic_param: $generic_param_bound),*> AddAssign<$rhs_ty> for $lhs_ty {
#[inline]
fn add_assign(&mut self, rhs: $rhs_ty) {
*self = *self + apply($rhs_body, rhs);
}
}
impl <$($generic_param: $generic_param_bound),*> SubAssign<$rhs_ty> for $lhs_ty {
#[inline]
fn sub_assign(&mut self, rhs: $rhs_ty) {
*self = *self - apply($rhs_body, rhs);
}
}
impl <$($generic_param: $generic_param_bound),*> MulAssign<$rhs_ty> for $lhs_ty {
#[inline]
fn mul_assign(&mut self, rhs: $rhs_ty) {
*self = *self * apply($rhs_body, rhs);
}
}
impl <$($generic_param: $generic_param_bound),*> DivAssign<$rhs_ty> for $lhs_ty {
#[inline]
fn div_assign(&mut self, rhs: $rhs_ty) {
*self = *self / apply($rhs_body, rhs);
}
}
impl_assign_ops!($($rest)*);
};
}
#[inline]
fn apply<F: FnOnce(X) -> O, X, O>(f: F, x: X) -> O {
f(x)
}
impl_bin_ops! {
for<M: Modulus> <StaticModInt<M> > ~ <StaticModInt<M> > -> StaticModInt<M> { { |x| x } ~ { |x| x } }
for<M: Modulus> <StaticModInt<M> > ~ <&'_ StaticModInt<M> > -> StaticModInt<M> { { |x| x } ~ { |&x| x } }
for<M: Modulus> <&'_ StaticModInt<M> > ~ <StaticModInt<M> > -> StaticModInt<M> { { |&x| x } ~ { |x| x } }
for<M: Modulus> <&'_ StaticModInt<M> > ~ <&'_ StaticModInt<M> > -> StaticModInt<M> { { |&x| x } ~ { |&x| x } }
for<I: Id > <DynamicModInt<I> > ~ <DynamicModInt<I> > -> DynamicModInt<I> { { |x| x } ~ { |x| x } }
for<I: Id > <DynamicModInt<I> > ~ <&'_ DynamicModInt<I>> -> DynamicModInt<I> { { |x| x } ~ { |&x| x } }
for<I: Id > <&'_ DynamicModInt<I>> ~ <DynamicModInt<I> > -> DynamicModInt<I> { { |&x| x } ~ { |x| x } }
for<I: Id > <&'_ DynamicModInt<I>> ~ <&'_ DynamicModInt<I>> -> DynamicModInt<I> { { |&x| x } ~ { |&x| x } }
for<M: Modulus, T: RemEuclidU32> <StaticModInt<M> > ~ <T> -> StaticModInt<M> { { |x| x } ~ { StaticModInt::<M>::new } }
for<I: Id , T: RemEuclidU32> <DynamicModInt<I> > ~ <T> -> DynamicModInt<I> { { |x| x } ~ { DynamicModInt::<I>::new } }
}
impl_assign_ops! {
for<M: Modulus> <StaticModInt<M> > ~= <StaticModInt<M> > { _ ~= { |x| x } }
for<M: Modulus> <StaticModInt<M> > ~= <&'_ StaticModInt<M> > { _ ~= { |&x| x } }
for<I: Id > <DynamicModInt<I>> ~= <DynamicModInt<I> > { _ ~= { |x| x } }
for<I: Id > <DynamicModInt<I>> ~= <&'_ DynamicModInt<I>> { _ ~= { |&x| x } }
for<M: Modulus, T: RemEuclidU32> <StaticModInt<M> > ~= <T> { _ ~= { StaticModInt::<M>::new } }
for<I: Id, T: RemEuclidU32> <DynamicModInt<I>> ~= <T> { _ ~= { DynamicModInt::<I>::new } }
}
macro_rules! impl_folding {
() => {};
(impl<$generic_param:ident : $generic_param_bound:tt> $trait:ident<_> for $self:ty { fn $method:ident(_) -> _ { _($unit:expr, $op:expr) } } $($rest:tt)*) => {
impl<$generic_param: $generic_param_bound> $trait<Self> for $self {
#[inline]
fn $method<S>(iter: S) -> Self
where
S: Iterator<Item = Self>,
{
iter.fold($unit, $op)
}
}
impl<'a, $generic_param: $generic_param_bound> $trait<&'a Self> for $self {
#[inline]
fn $method<S>(iter: S) -> Self
where
S: Iterator<Item = &'a Self>,
{
iter.fold($unit, $op)
}
}
impl_folding!($($rest)*);
};
}
impl_folding! {
impl<M: Modulus> Sum<_> for StaticModInt<M> { fn sum(_) -> _ { _(Self::raw(0), Add::add) } }
impl<M: Modulus> Product<_> for StaticModInt<M> { fn product(_) -> _ { _(Self::raw(1), Mul::mul) } }
impl<I: Id > Sum<_> for DynamicModInt<I> { fn sum(_) -> _ { _(Self::raw(0), Add::add) } }
impl<I: Id > Product<_> for DynamicModInt<I> { fn product(_) -> _ { _(Self::raw(1), Mul::mul) } }
}
#[cfg(test)]
mod tests {
use crate::modint::ModInt1000000007;
#[test]
fn static_modint_new() {
assert_eq!(0, ModInt1000000007::new(0u32).val);
assert_eq!(1, ModInt1000000007::new(1u32).val);
assert_eq!(1, ModInt1000000007::new(1_000_000_008u32).val);
assert_eq!(0, ModInt1000000007::new(0u64).val);
assert_eq!(1, ModInt1000000007::new(1u64).val);
assert_eq!(1, ModInt1000000007::new(1_000_000_008u64).val);
assert_eq!(0, ModInt1000000007::new(0usize).val);
assert_eq!(1, ModInt1000000007::new(1usize).val);
assert_eq!(1, ModInt1000000007::new(1_000_000_008usize).val);
assert_eq!(0, ModInt1000000007::new(0i64).val);
assert_eq!(1, ModInt1000000007::new(1i64).val);
assert_eq!(1, ModInt1000000007::new(1_000_000_008i64).val);
assert_eq!(1_000_000_006, ModInt1000000007::new(-1i64).val);
}
#[test]
fn static_modint_add() {
fn add(lhs: u32, rhs: u32) -> u32 {
(ModInt1000000007::new(lhs) + ModInt1000000007::new(rhs)).val
}
assert_eq!(2, add(1, 1));
assert_eq!(1, add(1_000_000_006, 2));
}
#[test]
fn static_modint_sub() {
fn sub(lhs: u32, rhs: u32) -> u32 {
(ModInt1000000007::new(lhs) - ModInt1000000007::new(rhs)).val
}
assert_eq!(1, sub(2, 1));
assert_eq!(1_000_000_006, sub(0, 1));
}
#[test]
fn static_modint_mul() {
fn mul(lhs: u32, rhs: u32) -> u32 {
(ModInt1000000007::new(lhs) * ModInt1000000007::new(rhs)).val
}
assert_eq!(1, mul(1, 1));
assert_eq!(4, mul(2, 2));
assert_eq!(999_999_937, mul(100_000, 100_000));
}
#[test]
fn static_modint_prime_div() {
fn div(lhs: u32, rhs: u32) -> u32 {
(ModInt1000000007::new(lhs) / ModInt1000000007::new(rhs)).val
}
assert_eq!(0, div(0, 1));
assert_eq!(1, div(1, 1));
assert_eq!(1, div(2, 2));
assert_eq!(23_809_524, div(1, 42));
}
#[test]
fn static_modint_sum() {
fn sum(values: &[i64]) -> ModInt1000000007 {
values.iter().copied().map(ModInt1000000007::new).sum()
}
assert_eq!(ModInt1000000007::new(-3), sum(&[-1, 2, -3, 4, -5]));
}
#[test]
fn static_modint_product() {
fn product(values: &[i64]) -> ModInt1000000007 {
values.iter().copied().map(ModInt1000000007::new).product()
}
assert_eq!(ModInt1000000007::new(-120), product(&[-1, 2, -3, 4, -5]));
}
#[test]
fn static_modint_binop_coercion() {
let f = ModInt1000000007::new;
let a = 10_293_812_usize;
let b = 9_083_240_982_usize;
assert_eq!(f(a) + f(b), f(a) + b);
assert_eq!(f(a) - f(b), f(a) - b);
assert_eq!(f(a) * f(b), f(a) * b);
assert_eq!(f(a) / f(b), f(a) / b);
}
#[test]
fn static_modint_assign_coercion() {
let f = ModInt1000000007::new;
let a = f(10_293_812_usize);
let b = 9_083_240_982_usize;
let expected = (((a + b) * b) - b) / b;
let mut c = a;
c += b;
c *= b;
c -= b;
c /= b;
assert_eq!(expected, c);
}
}
}
Submission Info
Submission Time
2022-01-28 21:16:34+0900
Task
N - Zigzag Sequences
User
bouzuya
Language
Rust (1.42.0)
Score
6
Code Size
53838 Byte
Status
AC
Exec Time
173 ms
Memory
15860 KiB
Compile Error
warning: field is never read: `sum_e`
--> src/main.rs:861:9
|
861 | pub(crate) sum_e: Vec<StaticModInt<M>>,
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: field is never read: `sum_ie`
--> src/main.rs:862:9
|
862 | pub(crate) sum_ie: Vec<StaticModInt<M>>,
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
6 / 6
Status
Set Name
Test Cases
Sample
example0.txt, example1.txt, example2.txt, example3.txt
All
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, example0.txt, example1.txt, example2.txt, example3.txt
Case Name
Status
Exec Time
Memory
000.txt
AC 10 ms
2008 KiB
001.txt
AC 2 ms
2052 KiB
002.txt
AC 173 ms
15692 KiB
003.txt
AC 172 ms
15688 KiB
004.txt
AC 172 ms
15656 KiB
005.txt
AC 172 ms
15696 KiB
006.txt
AC 67 ms
7360 KiB
007.txt
AC 64 ms
7144 KiB
008.txt
AC 166 ms
15668 KiB
009.txt
AC 17 ms
3204 KiB
010.txt
AC 51 ms
7680 KiB
011.txt
AC 49 ms
7188 KiB
012.txt
AC 55 ms
7592 KiB
013.txt
AC 63 ms
7756 KiB
014.txt
AC 61 ms
7660 KiB
015.txt
AC 112 ms
15848 KiB
016.txt
AC 117 ms
15860 KiB
017.txt
AC 2 ms
2052 KiB
018.txt
AC 1 ms
2036 KiB
019.txt
AC 2 ms
2056 KiB
020.txt
AC 3 ms
2040 KiB
021.txt
AC 2 ms
2164 KiB
022.txt
AC 2 ms
2124 KiB
023.txt
AC 2 ms
2068 KiB
024.txt
AC 1 ms
2052 KiB
025.txt
AC 109 ms
10752 KiB
026.txt
AC 106 ms
10868 KiB
027.txt
AC 103 ms
10808 KiB
028.txt
AC 103 ms
10768 KiB
029.txt
AC 101 ms
10820 KiB
example0.txt
AC 1 ms
2020 KiB
example1.txt
AC 3 ms
2112 KiB
example2.txt
AC 1 ms
2108 KiB
example3.txt
AC 2 ms
2124 KiB