Struct MInt 

#[repr(transparent)]
pub struct MInt<M>
where
    M: MIntBase,
{
    x: M::Inner,
    _marker: PhantomData<fn() -> M>,
}

Fields

x: M::Inner

_marker: PhantomData<fn() -> M>

Implementations

impl<M> MInt<M>

where M: MIntConvert<u32>,

pub fn sqrt(self) -> Option<Self>

Examples found in repository

crates/competitive/src/math/formal_power_series/mod.rs (line 100)

    fn sqrt_coefficient(&self) -> Option<Self> {
        self.sqrt()
    }

crates/library_checker/src/number_theory/sqrt_mod.rs (line 10)

pub fn sqrt_mod(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(q, yp: [(u32, u32); iter q]);
    for (y, p) in yp {
        DynMIntU32::set_mod(p);
        if let Some(x) = DynMIntU32::from(y).sqrt() {
            pp!(x);
        } else {
            pp!("-1");
        }
    }
}

impl<M> MInt<M>

where M: MIntConvert,

pub fn new(x: M::Inner) -> Self

Examples found in repository

crates/library_checker/src/number_theory/sum_of_totient_function.rs (line 15)

pub fn sum_of_totient_function(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n: u64);
    let mut s = 1;
    let mut pp = 0;
    let mut pc = 0;
    let inv2 = M::new(2).inv();
    let qa = QuotientArray::from_fn(n, |i| [M::from(i), M::from(i) * M::from(i + 1) * inv2])
        .map(|[x, y]| [x - M::one(), y - M::one()])
        .lucy_dp::<ArrayOperation<AdditiveOperation<_>, 2>>(|[x, y], p| [x, y * M::from(p)])
        .map(|[x, y]| y - x)
        .min_25_sieve::<AddMulOperation<_>>(|p, c| {
            if pp != p || pc > c {
                pp = p;
                pc = 1;
                s = p - 1;
            }
            while pc < c {
                pc += 1;
                s *= p;
            }
            M::from(s)
        });
    pp!(qa[n]);
}

crates/competitive/src/math/number_theoretic_transform.rs (line 778)

fn reconstruct_mint_crt<M, N1, N2, N3>(f: (MVec<N1>, MVec<N2>, MVec<N3>)) -> MVec<M>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    let t1 = MInt::<N2>::new(N1::get_mod()).inv();
    let m1_3 = MInt::<N3>::new(N1::get_mod());
    let t2 = (m1_3 * MInt::<N3>::new(N2::get_mod())).inv();
    let modulus = <M as MIntConvert<u32>>::mod_into() as u64;
    let m1 = N1::get_mod() as u64;
    let m2 = m1 * N2::get_mod() as u64 % modulus;
    let fits_u64 = (N1::get_mod() - 1) as u128
        + (N2::get_mod() - 1) as u128 * m1 as u128
        + (N3::get_mod() - 1) as u128 * m2 as u128
        <= u64::MAX as u128;
    f.0.into_iter()
        .zip(f.1)
        .zip(f.2)
        .map(|((c1, c2), c3)| {
            let d1 = c1.inner();
            let d2 = ((c2 - MInt::<N2>::from(d1)) * t1).inner();
            let x = MInt::<N3>::new(d1) + MInt::<N3>::new(d2) * m1_3;
            let d3 = ((c3 - x) * t2).inner();
            let value = if fits_u64 {
                (d1 as u64 + d2 as u64 * m1 + d3 as u64 * m2) % modulus
            } else {
                ((d1 as u128 + d2 as u128 * m1 as u128 + d3 as u128 * m2 as u128) % modulus as u128)
                    as u64
            };
            MInt::<M>::from(value as u32)
        })
        .collect()
}

impl<M, N1, N2, N3> ConvolveSteps for Convolve<(M, (N1, N2, N3))>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    type T = MVec<M>;
    type F = (MVec<N1>, MVec<N2>, MVec<N3>);
    fn length(t: &Self::T) -> usize {
        t.len()
    }
    fn transform(t: Self::T, len: usize) -> Self::F {
        let npot = len.max(1).next_power_of_two();
        let f = convert_crt_input(t, npot);
        (
            Convolve::<N1>::transform(f.0, npot),
            Convolve::<N2>::transform(f.1, npot),
            Convolve::<N3>::transform(f.2, npot),
        )
    }
    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        reconstruct_mint_crt((
            Convolve::<N1>::inverse_transform(f.0, len),
            Convolve::<N2>::inverse_transform(f.1, len),
            Convolve::<N3>::inverse_transform(f.2, len),
        ))
    }
    fn multiply(f: &mut Self::F, g: &Self::F) {
        Convolve::<N1>::multiply(&mut f.0, &g.0);
        Convolve::<N2>::multiply(&mut f.1, &g.1);
        Convolve::<N3>::multiply(&mut f.2, &g.2);
    }
    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        let max_len = Self::length(&a).max(Self::length(&b));
        let min_len = Self::length(&a).min(Self::length(&b));
        let (balanced, short) = crate::avx_helper!(@dispatch_avx2_fma (30, 10), (384, 128));
        if max_len <= balanced || min_len <= short {
            return convolve_karatsuba(&a, &b);
        }
        // Limit coefficient growth to leave headroom for FFT roundoff.
        let fft_limit = crate::avx_helper!(@dispatch_avx2_fma
            1usize << ((1u64 << 50) / <M as MIntConvert<u32>>::mod_into() as u64).ilog2().min(20), 0);
        let convolve = |a: Self::T, b: Self::T| {
            let fft_len = (a.len() + b.len() - 1).next_power_of_two();
            if fft_len <= 256 && a.len() * b.len() <= fft_len * 8 {
                return convolve_karatsuba(&a, &b);
            }
            if fft_len <= fft_limit {
                crate::avx_helper!(@dispatch_avx2_fma return unsafe {
                    convolve_mint_avx2(a, b)
                }, ());
            }
            convolve_mint_crt::<M, N1, N2, N3>(a, b)
        };
        let block_len = min_len.next_power_of_two() * 8 - min_len + 1;
        let block_len = if min_len <= fft_limit / 2 {
            block_len.min(fft_limit - min_len + 1)
        } else {
            block_len
        };
        if max_len <= block_len {
            return convolve(a, b);
        }
        let (a, b) = if a.len() >= b.len() { (a, b) } else { (b, a) };
        let mut result = vec![MInt::<M>::zero(); a.len() + b.len() - 1];
        for (i, a) in a.chunks(block_len).enumerate() {
            let product = convolve(a.to_vec(), b.clone());
            for (value, product) in result[i * block_len..].iter_mut().zip(product) {
                *value += product;
            }
        }
        result
    }
}

fn convolve_mint_crt<M, N1, N2, N3>(a: MVec<M>, b: MVec<M>) -> MVec<M>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    let convolve = |a: MVec<M>, b: MVec<M>| {
        let a_len = a.len();
        let b_len = b.len();
        let a = convert_crt_input(a, a_len);
        let b = convert_crt_input(b, b_len);
        reconstruct_mint_crt((
            Convolve::<N1>::convolve(a.0, b.0),
            Convolve::<N2>::convolve(a.1, b.1),
            Convolve::<N3>::convolve(a.2, b.2),
        ))
    };
    let modulus = <M as MIntConvert<u32>>::mod_into() as u128;
    let capacity = N1::MOD as u128 * N2::MOD as u128 * N3::MOD as u128;
    if a.len().min(b.len()) as u128 * (modulus - 1).pow(2) < capacity {
        return convolve(a, b);
    }
    let block_len = ((capacity - 1) / (modulus - 1).pow(2)) as usize;
    if block_len == 0 {
        return convolve_naive(&a, &b);
    }
    let mut result = vec![MInt::<M>::zero(); a.len() + b.len() - 1];
    for (i, a) in a.chunks(block_len).enumerate() {
        for (j, b) in b.chunks(block_len).enumerate() {
            let product = convolve(a.to_vec(), b.to_vec());
            for (value, product) in result[(i + j) * block_len..].iter_mut().zip(product) {
                *value += product;
            }
        }
    }
    result
}

impl<N1, N2, N3> ConvolveSteps for Convolve<(u64, (N1, N2, N3))>
where
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    type T = Vec<u64>;
    type F = ([MVec<N1>; 3], [MVec<N2>; 3], [MVec<N3>; 3]);

    fn length(t: &Self::T) -> usize {
        t.len()
    }

    fn transform(t: Self::T, len: usize) -> Self::F {
        let npot = len.max(1).next_power_of_two();
        assert!(npot <= 1usize << N1::RANK.min(N2::RANK).min(N3::RANK));
        // The 22-bit fallback needs room for three limb products per coefficient.
        assert!(
            3 * npot as u128 * ((1u128 << 22) - 1).pow(2)
                < N1::MOD as u128 * N2::MOD as u128 * N3::MOD as u128
        );
        let bits = if 2 * npot as u128 * (u32::MAX as u128).pow(2)
            < N1::MOD as u128 * N2::MOD as u128 * N3::MOD as u128
        {
            32
        } else {
            22
        };
        let parts = if bits == 32 && t.iter().all(|&value| value <= u32::MAX as u64) {
            1
        } else {
            64usize.div_ceil(bits)
        };
        fn split<M: Montgomery32NttModulus>(
            t: &[u64],
            len: usize,
            bits: usize,
            parts: usize,
        ) -> [MVec<M>; 3] {
            std::array::from_fn(|part| {
                if part >= parts {
                    return Vec::new();
                }
                Convolve::<M>::transform(
                    t.iter()
                        .map(|&t| MInt::from((t >> (part * bits)) & ((1u64 << bits) - 1)))
                        .collect(),
                    len,
                )
            })
        }
        (
            split(&t, npot, bits, parts),
            split(&t, npot, bits, parts),
            split(&t, npot, bits, parts),
        )
    }

    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        let bits = if f.0[2].is_empty() { 32 } else { 22 };
        let t1 = MInt::<N2>::new(N1::get_mod()).inv();
        let m1 = N1::get_mod() as u64;
        let m1_3 = MInt::<N3>::new(N1::get_mod());
        let t2 = (m1_3 * MInt::<N3>::new(N2::get_mod())).inv();
        let m2 = m1 * N2::get_mod() as u64;
        let mut result = vec![0u64; len.min(f.0[0].len())];
        for (part, ((f1, f2), f3)) in f.0.into_iter().zip(f.1).zip(f.2).enumerate() {
            if f1.is_empty() {
                continue;
            }
            for (value, ((c1, c2), c3)) in result.iter_mut().zip(
                Convolve::<N1>::inverse_transform(f1, len)
                    .into_iter()
                    .zip(Convolve::<N2>::inverse_transform(f2, len))
                    .zip(Convolve::<N3>::inverse_transform(f3, len)),
            ) {
                let d1 = c1.inner();
                let d2 = ((c2 - MInt::<N2>::from(d1)) * t1).inner();
                let x = MInt::<N3>::new(d1) + MInt::<N3>::new(d2) * m1_3;
                let d3 = ((c3 - x) * t2).inner();
                let limb = (d1 as u64)
                    .wrapping_add((d2 as u64).wrapping_mul(m1))
                    .wrapping_add((d3 as u64).wrapping_mul(m2));
                *value = value.wrapping_add(limb << (part * bits));
            }
        }
        result
    }

    fn multiply(f: &mut Self::F, g: &Self::F) {
        fn multiply<M: Montgomery32NttModulus>(f: &mut [MVec<M>; 3], g: &[MVec<M>; 3]) {
            assert_eq!(f[0].len(), g[0].len());
            if f[1].is_empty() || g[1].is_empty() {
                if f[1].is_empty() && !g[1].is_empty() {
                    f[1] = f[0].clone();
                    Convolve::<M>::multiply(&mut f[1], &g[1]);
                } else if !f[1].is_empty() {
                    Convolve::<M>::multiply(&mut f[1], &g[0]);
                }
                Convolve::<M>::multiply(&mut f[0], &g[0]);
                return;
            }
            #[cfg(target_arch = "x86_64")]
            if use_block_ntt::<M>(f[0].len()) {
                for part in (1..if f[2].is_empty() { 2 } else { 3 }).rev() {
                    let mut sum = f[0].clone();
                    Convolve::<M>::multiply(&mut sum, &g[part]);
                    for left in 1..=part {
                        let mut product = f[left].clone();
                        Convolve::<M>::multiply(&mut product, &g[part - left]);
                        for (value, product) in sum.iter_mut().zip(product) {
                            // Block products contain lazy Montgomery residues.
                            *value = MInt::new(value.inner() + product.inner());
                        }
                    }
                    f[part] = sum;
                }
                Convolve::<M>::multiply(&mut f[0], &g[0]);
                return;
            }
            if f[2].is_empty() {
                for i in 0..f[0].len() {
                    f[1][i] = f[0][i] * g[1][i] + f[1][i] * g[0][i];
                    f[0][i] *= g[0][i];
                }
                return;
            }
            for i in 0..f[0].len() {
                f[2][i] = f[0][i] * g[2][i] + f[1][i] * g[1][i] + f[2][i] * g[0][i];
                f[1][i] = f[0][i] * g[1][i] + f[1][i] * g[0][i];
                f[0][i] *= g[0][i];
            }
        }
        multiply(&mut f.0, &g.0);
        multiply(&mut f.1, &g.1);
        multiply(&mut f.2, &g.2);
    }

    fn square(t: Self::T, len: usize) -> Self::T {
        let mut f = Self::transform(t, len);
        let g = f.clone();
        Self::multiply(&mut f, &g);
        Self::inverse_transform(f, len)
    }

    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        let max_len = Self::length(&a).max(Self::length(&b));
        let min_len = Self::length(&a).min(Self::length(&b));
        let (balanced, short) = crate::avx_helper!(@dispatch_avx2_fma (300, 64), (1536, 512));
        if max_len <= balanced || min_len <= short {
            let a_wrapping: &[Wrapping<u64>] =
                unsafe { std::slice::from_raw_parts(a.as_ptr().cast(), a.len()) };
            let b_wrapping: &[Wrapping<u64>] =
                unsafe { std::slice::from_raw_parts(b.as_ptr().cast(), b.len()) };
            let mut c = std::mem::ManuallyDrop::new(if max_len <= 300 || min_len > 60 {
                convolve_karatsuba(a_wrapping, b_wrapping)
            } else {
                convolve_naive(a_wrapping, b_wrapping)
            });
            return unsafe { Vec::from_raw_parts(c.as_mut_ptr().cast(), c.len(), c.capacity()) };
        }
        let len = (Self::length(&a) + Self::length(&b)).saturating_sub(1);
        let block_len = if min_len >= 1 << 20 {
            1 << 20
        } else {
            (min_len.next_power_of_two() * 8).min(1 << 21) - min_len + 1
        };
        if max_len <= block_len {
            return convolve_u64_fft(a, b);
        }
        let mut result = vec![0u64; len];
        for (i, a) in a.chunks(block_len).enumerate() {
            for (j, b) in b.chunks(block_len).enumerate() {
                if a.len().min(b.len()) <= 60 {
                    for (x, &a) in a.iter().enumerate() {
                        for (y, &b) in b.iter().enumerate() {
                            let value = &mut result[(i + j) * block_len + x + y];
                            *value = value.wrapping_add(a.wrapping_mul(b));
                        }
                    }
                    continue;
                }
                let product = convolve_u64_fft(a.to_vec(), b.to_vec());
                for (value, product) in result[(i + j) * block_len..].iter_mut().zip(product) {
                    *value = value.wrapping_add(product);
                }
            }
        }
        result
    }
}

fn convolve_u64_fft(a: Vec<u64>, b: Vec<u64>) -> Vec<u64> {
    // Keep limb convolutions below 2^47 at the 2^21 FFT limit.
    crate::avx_helper!(@dispatch_avx2_fma return unsafe {
        convolve_u64_avx2(a, b)
    }, ());
    convolve_u64_fft_scalar(a, b)
}

fn convolve_u64_fft_scalar(a: Vec<u64>, b: Vec<u64>) -> Vec<u64> {
    fn split(values: &[u64]) -> [Vec<i64>; 5] {
        let mut result = std::array::from_fn(|_| Vec::with_capacity(values.len()));
        for mut value in values.iter().copied() {
            for part in &mut result {
                let digit = ((value << 51) as i64) >> 51;
                part.push(digit);
                value = (value >> 13).wrapping_add(u64::from(digit < 0));
            }
        }
        result
    }

    let len = a.len() + b.len() - 1;
    let transform = |values: &[u64]| {
        if values.iter().any(|&value| value > u32::MAX as u64) {
            return split(values).map(|part| ConvolveRealFft::transform(part, len));
        }
        let [a, b, c, _, _] = split(values);
        let a = ConvolveRealFft::transform(a, len);
        let size = a.len();
        [
            a,
            ConvolveRealFft::transform(b, len),
            ConvolveRealFft::transform(c, len),
            vec![Zero::zero(); size],
            vec![Zero::zero(); size],
        ]
    };
    let fa = transform(&a);
    drop(a);
    let fb = transform(&b);
    drop(b);
    let values: [Vec<i64>; 5] = std::array::from_fn(|part| {
        let mut sum = fa[0].clone();
        ConvolveRealFft::multiply(&mut sum, &fb[part]);
        for left in 1..=part {
            let mut product = fa[left].clone();
            ConvolveRealFft::multiply(&mut product, &fb[part - left]);
            for (sum, product) in sum.iter_mut().zip(product) {
                *sum += product;
            }
        }
        ConvolveRealFft::inverse_transform(sum, len)
    });
    (0..len)
        .map(|i| {
            (values[0][i] as u64)
                .wrapping_add((values[1][i] as u64) << 13)
                .wrapping_add((values[2][i] as u64) << 26)
                .wrapping_add((values[3][i] as u64) << 39)
                .wrapping_add((values[4][i] as u64) << 52)
        })
        .collect()
}

pub trait NttReuse: ConvolveSteps {
    const MULTIPLE: bool = true;

    /// Transforms coefficients into the usual NTT frequency order.
    fn transform_ntt(t: Self::T, len: usize) -> Self::F {
        Self::transform(t, len)
    }

    /// Inverts a value produced by `transform_ntt`.
    fn inverse_transform_ntt(f: Self::F, len: usize) -> Self::T {
        Self::inverse_transform(f, len)
    }

    /// Extends a value produced by `transform_ntt` to twice its length.
    /// If `monic`, the input represents a monic degree-`n` polynomial modulo
    /// `x^n - 1`, where `n` is the transform length.
    fn ntt_doubling(f: Self::F, monic: bool) -> Self::F;

    /// Extracts the even coefficients of `a(x) * b(-x)` in the usual NTT frequency order.
    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F;

    /// Extracts the odd coefficients of `a(x) * b(-x)` in the usual NTT frequency order.
    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F;

    /// Multiplies a usual NTT transform by the corresponding prefix of another one.
    fn multiply_prefix(f: &mut Self::F, g: &Self::F);

    /// Adds the pointwise product of two usual NTT transforms to `sum`.
    fn multiply_add(sum: &mut Self::F, f: &Self::F, g: &Self::F);

    /// Maximum number of products that can be summed before reconstruction.
    /// Both factors must transform canonical coefficients at the supplied transform's length,
    /// and each cyclic product must itself be reconstructible.
    fn max_product_sum_count(_f: &Self::F) -> usize {
        if Self::MULTIPLE { 1 } else { usize::MAX }
    }

    fn power_projection_step(
        p_flat: Self::T,
        q_flat: Self::T,
        n: usize,
        py: usize,
        qy: usize,
    ) -> (Self::T, Self::T) {
        let base = n * 2;
        let len_p = base * py;
        let len_q = base * qy;
        let len = (len_p + len_q - 1).max(len_q + len_q - 1);
        let half = len.max(1).next_power_of_two() / 2;

        let p_fft = Self::transform_ntt(p_flat, len);
        let q_fft = Self::transform_ntt(q_flat, len);
        let pr_fft = Self::odd_mul_normal_neg(&p_fft, &q_fft);
        let qr_fft = Self::even_mul_normal_neg(&q_fft, &q_fft);
        (
            Self::inverse_transform_ntt(pr_fft, half),
            Self::inverse_transform_ntt(qr_fft, half),
        )
    }
}

thread_local!(
    static BIT_REVERSE: UnsafeCell<Vec<Vec<usize>>> = const { UnsafeCell::new(vec![]) };
);

impl<M> NttReuse for Convolve<M>
where
    M: Montgomery32NttModulus,
{
    const MULTIPLE: bool = false;

    fn transform_ntt(mut t: Self::T, len: usize) -> Self::F {
        t.resize_with(len.max(1).next_power_of_two(), Zero::zero);
        ntt(&mut t);
        t
    }

    fn inverse_transform_ntt(mut f: Self::F, len: usize) -> Self::T {
        intt(&mut f);
        f.truncate(len);
        f
    }

    fn ntt_doubling(mut f: Self::F, monic: bool) -> Self::F {
        let n = f.len();
        let k = n.trailing_zeros() as usize;
        let mut a = Self::inverse_transform_ntt(f.clone(), n);
        if monic {
            a[0] -= MInt::<M>::from(2);
        }
        let zeta = MInt::<M>::new_unchecked(M::INFO.root[k + 1]);
        let zeta2 = zeta * zeta;
        let mut rot = [MInt::one(), zeta, zeta2, zeta2 * zeta];
        let step = zeta2 * zeta2;
        for a in a.chunks_mut(4) {
            for (a, rot) in a.iter_mut().zip(&mut rot) {
                *a *= *rot;
                *rot *= step;
            }
        }
        f.extend(Self::transform_ntt(a, n));
        f
    }

    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        assert_eq!(f.len(), g.len());
        assert!(f.len().is_power_of_two());
        assert!(f.len() >= 2);
        if std::ptr::eq(f, g) {
            return f.as_chunks::<2>().0.iter().map(|a| a[0] * a[1]).collect();
        }
        let inv2 = MInt::<M>::from(2).inv();
        let n = f.len() / 2;
        (0..n)
            .map(|i| (f[i << 1] * g[i << 1 | 1] + f[i << 1 | 1] * g[i << 1]) * inv2)
            .collect()
    }

    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        assert_eq!(f.len(), g.len());
        assert!(f.len().is_power_of_two());
        assert!(f.len() >= 2);
        let mut inv2 = MInt::<M>::from(2).inv();
        let n = f.len() / 2;
        let k = f.len().trailing_zeros() as usize;
        let mut h = vec![MInt::<M>::zero(); n];
        let w = MInt::<M>::new_unchecked(M::INFO.inv_root[k]);
        BIT_REVERSE.with(|br| {
            let br = unsafe { &mut *br.get() };
            if br.len() < k {
                br.resize_with(k, Default::default);
            }
            let k = k - 1;
            if br[k].is_empty() {
                let mut v = vec![0; 1 << k];
                for i in 0..1 << k {
                    v[i] = (v[i >> 1] >> 1) | ((i & 1) << k.saturating_sub(1));
                }
                br[k] = v;
            }
            for &i in &br[k] {
                h[i] = (f[i << 1] * g[i << 1 | 1] - f[i << 1 | 1] * g[i << 1]) * inv2;
                inv2 *= w;
            }
        });
        h
    }

    fn multiply_prefix(f: &mut Self::F, g: &Self::F) {
        pointwise_multiply(f, g);
    }

    fn multiply_add(sum: &mut Self::F, f: &Self::F, g: &Self::F) {
        assert!(sum.len() == f.len() && sum.len() == g.len());
        pointwise_multiply_add(sum, f, g);
    }

    fn power_projection_step(
        p_flat: Vec<MInt<M>>,
        q_flat: Vec<MInt<M>>,
        n: usize,
        py: usize,
        qy: usize,
    ) -> (Vec<MInt<M>>, Vec<MInt<M>>) {
        let high_degree = (qy - 1) * 2;
        let rows = (py + qy - 1).max(high_degree).next_power_of_two();
        let cols = n * 2;
        let size = rows * cols;
        let mut p = p_flat;
        p.resize_with(size, MInt::<M>::zero);
        ntt_rows(&mut p, cols);
        ntt_batch(&mut p, cols);

        let mut q = q_flat;
        q.resize_with(size, MInt::<M>::zero);
        ntt_rows(&mut q, cols);
        let q_high = (rows == high_degree).then(|| q[(qy - 1) * cols..qy * cols].to_vec());
        ntt_batch(&mut q, cols);

        let half = cols / 2;
        let mut odd_factor = vec![MInt::<M>::zero(); half];
        let mut factor = MInt::<M>::from(2).inv();
        let k = cols.trailing_zeros() as usize;
        let w = MInt::<M>::new_unchecked(M::INFO.inv_root[k]);
        BIT_REVERSE.with(|br| {
            let br = unsafe { &mut *br.get() };
            if br.len() < k {
                br.resize_with(k, Default::default);
            }
            let k = k - 1;
            if br[k].is_empty() {
                let mut v = vec![0; 1 << k];
                for i in 0..1 << k {
                    v[i] = (v[i >> 1] >> 1) | ((i & 1) << k.saturating_sub(1));
                }
                br[k] = v;
            }
            for &i in &br[k] {
                odd_factor[i] = factor;
                factor *= w;
            }
        });

        let mut pr = vec![MInt::<M>::zero(); rows * half];
        let mut qr = vec![MInt::<M>::zero(); rows * half];
        for i in 0..pr.len() {
            pr[i] = (p[i << 1] * q[i << 1 | 1] - p[i << 1 | 1] * q[i << 1])
                * odd_factor[i & (half - 1)];
            qr[i] = q[i << 1] * q[i << 1 | 1];
        }
        intt_batch(&mut pr, half);
        intt_rows(&mut pr, half);
        intt_batch(&mut qr, half);
        intt_rows(&mut qr, half);

        if let Some(q_high) = q_high {
            let mut q_high_even = vec![MInt::<M>::zero(); half];
            for i in 0..half {
                q_high_even[i] = q_high[i << 1] * q_high[i << 1 | 1];
            }
            intt(&mut q_high_even);
            for (value, high) in qr.iter_mut().zip(&q_high_even) {
                *value -= *high;
            }
            qr.extend_from_slice(&q_high_even);
        }
        (pr, qr)
    }
}

impl<M, N1, N2, N3> NttReuse for Convolve<(M, (N1, N2, N3))>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    fn max_product_sum_count(f: &Self::F) -> usize {
        let modulus = <M as MIntConvert<u32>>::mod_into() as u128;
        if modulus == 1 {
            return usize::MAX;
        }
        let capacity = N1::MOD as u128 * N2::MOD as u128 * N3::MOD as u128;
        ((capacity - 1) / ((modulus - 1) * (modulus - 1)) / f.0.len() as u128)
            .clamp(1, usize::MAX as u128) as usize
    }

    fn transform_ntt(t: Self::T, len: usize) -> Self::F {
        let npot = len.max(1).next_power_of_two();
        let f = convert_crt_input(t, npot);
        (
            Convolve::<N1>::transform_ntt(f.0, npot),
            Convolve::<N2>::transform_ntt(f.1, npot),
            Convolve::<N3>::transform_ntt(f.2, npot),
        )
    }

    fn inverse_transform_ntt(f: Self::F, len: usize) -> Self::T {
        reconstruct_mint_crt((
            Convolve::<N1>::inverse_transform_ntt(f.0, len),
            Convolve::<N2>::inverse_transform_ntt(f.1, len),
            Convolve::<N3>::inverse_transform_ntt(f.2, len),
        ))
    }

    fn ntt_doubling(f: Self::F, monic: bool) -> Self::F {
        if monic {
            let n = f.0.len();
            let mut coefficients = Self::inverse_transform_ntt(f, n);
            coefficients[0] -= MInt::<M>::one();
            coefficients.push(MInt::<M>::one());
            Self::transform_ntt(coefficients, n * 2)
        } else {
            (
                Convolve::<N1>::ntt_doubling(f.0, false),
                Convolve::<N2>::ntt_doubling(f.1, false),
                Convolve::<N3>::ntt_doubling(f.2, false),
            )
        }
    }

    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        fn even_mul_normal_neg_corrected<M>(f: &[MInt<M>], g: &[MInt<M>], m: u32) -> Vec<MInt<M>>
        where
            M: Montgomery32NttModulus,
        {
            let n = f.len();
            assert_eq!(f.len(), g.len());
            assert!(f.len().is_power_of_two());
            assert!(f.len() >= 2);
            let inv2 = MInt::<M>::from(2).inv();
            let u = MInt::<M>::new(m) * MInt::<M>::from(n as u32);
            let n = f.len() / 2;
            (0..n)
                .map(|i| {
                    (f[i << 1]
                        * if i == 0 {
                            g[i << 1 | 1] + u
                        } else {
                            g[i << 1 | 1]
                        }
                        + f[i << 1 | 1] * g[i << 1])
                        * inv2
                })
                .collect()
        }

        let m = M::mod_into();
        (
            even_mul_normal_neg_corrected(&f.0, &g.0, m),
            even_mul_normal_neg_corrected(&f.1, &g.1, m),
            even_mul_normal_neg_corrected(&f.2, &g.2, m),
        )
    }

    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        fn odd_mul_normal_neg_corrected<M>(f: &[MInt<M>], g: &[MInt<M>], m: u32) -> Vec<MInt<M>>
        where
            M: Montgomery32NttModulus,
        {
            assert_eq!(f.len(), g.len());
            assert!(f.len().is_power_of_two());
            assert!(f.len() >= 2);
            let mut inv2 = MInt::<M>::from(2).inv();
            let u = MInt::<M>::new(m) * MInt::<M>::from(f.len() as u32);
            let n = f.len() / 2;
            let k = f.len().trailing_zeros() as usize;
            let mut h = vec![MInt::<M>::zero(); n];
            let w = MInt::<M>::new_unchecked(M::INFO.inv_root[k]);
            BIT_REVERSE.with(|br| {
                let br = unsafe { &mut *br.get() };
                if br.len() < k {
                    br.resize_with(k, Default::default);
                }
                let k = k - 1;
                if br[k].is_empty() {
                    let mut v = vec![0; 1 << k];
                    for i in 0..1 << k {
                        v[i] = (v[i >> 1] >> 1) | ((i & 1) << k.saturating_sub(1));
                    }
                    br[k] = v;
                }
                for &i in &br[k] {
                    h[i] = (f[i << 1]
                        * if i == 0 {
                            g[i << 1 | 1] + u
                        } else {
                            g[i << 1 | 1]
                        }
                        - f[i << 1 | 1] * g[i << 1])
                        * inv2;
                    inv2 *= w;
                }
            });
            h
        }

impl<M> MInt<M>

where M: MIntBase,

pub const fn new_unchecked(x: M::Inner) -> Self

Examples found in repository

crates/competitive/src/num/mint/mint_base.rs (line 60)

    pub fn new(x: M::Inner) -> Self {
        Self::new_unchecked(<M as MIntConvert<M::Inner>>::from(x))
    }
}
impl<M> MInt<M>
where
    M: MIntBase,
{
    #[inline]
    pub const fn new_unchecked(x: M::Inner) -> Self {
        Self {
            x,
            _marker: PhantomData,
        }
    }
    #[inline]
    pub fn get_mod() -> M::Inner {
        M::get_mod()
    }
    #[inline]
    pub fn pow(self, y: usize) -> Self {
        Self::new_unchecked(M::mod_pow(self.x, y))
    }
    #[inline]
    pub fn inv(self) -> Self {
        Self::new_unchecked(M::mod_inv(self.x))
    }
    #[inline]
    pub fn inner(self) -> M::Inner {
        M::mod_inner(self.x)
    }
}

impl<M> Clone for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn clone(&self) -> Self {
        *self
    }
}
impl<M> Copy for MInt<M> where M: MIntBase {}
impl<M> Debug for MInt<M>
where
    M: MIntBase,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        Debug::fmt(&self.inner(), f)
    }
}
impl<M> Default for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn default() -> Self {
        <Self as Zero>::zero()
    }
}
impl<M> PartialEq for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn eq(&self, other: &Self) -> bool {
        PartialEq::eq(&self.x, &other.x)
    }
}
impl<M> Eq for MInt<M> where M: MIntBase {}
impl<M> Hash for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&self.x, state)
    }
}
macro_rules! impl_mint_from {
    ($($t:ty),*) => {
        $(impl<M> From<$t> for MInt<M>
        where
            M: MIntConvert<$t>,
        {
            #[inline]
            fn from(x: $t) -> Self {
                Self::new_unchecked(<M as MIntConvert<$t>>::from(x))
            }
        }
        impl<M> From<MInt<M>> for $t
        where
            M: MIntConvert<$t>,
        {
            #[inline]
            fn from(x: MInt<M>) -> $t {
                <M as MIntConvert<$t>>::into(x.x)
            }
        })*
    };
}
impl_mint_from!(
    u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize
);
impl<M> Zero for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn zero() -> Self {
        Self::new_unchecked(M::mod_zero())
    }
}
impl<M> One for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn one() -> Self {
        Self::new_unchecked(M::mod_one())
    }
}

impl<M> Add for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn add(self, rhs: Self) -> Self::Output {
        Self::new_unchecked(M::mod_add(self.x, rhs.x))
    }
}
impl<M> Sub for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn sub(self, rhs: Self) -> Self::Output {
        Self::new_unchecked(M::mod_sub(self.x, rhs.x))
    }
}
impl<M> Mul for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn mul(self, rhs: Self) -> Self::Output {
        Self::new_unchecked(M::mod_mul(self.x, rhs.x))
    }
}
impl<M> Div for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn div(self, rhs: Self) -> Self::Output {
        Self::new_unchecked(M::mod_div(self.x, rhs.x))
    }
}
impl<M> Neg for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn neg(self) -> Self::Output {
        Self::new_unchecked(M::mod_neg(self.x))
    }

crates/competitive/src/num/mint/mod.rs (line 81)

    fn deserialize<I>(iter: &mut I) -> Self
    where
        I: Iterator<Item = u8>,
    {
        Self::new_unchecked(M::Inner::deserialize(iter))
    }
}

#[cfg_attr(nightly, codesnip::entry(when("MIntBase", "random_generator")))]
mod random_spec {
    use super::*;
    use std::ops::{RangeFull, RangeTo};

    impl<M> RandomSpec<MInt<M>> for RangeFull
    where
        M: MIntBase,
        RangeTo<M::Inner>: RandomSpec<M::Inner>,
    {
        fn rand(&self, rng: &mut Xorshift) -> MInt<M> {
            MInt::<M>::new_unchecked(rng.random(..M::get_mod()))
        }

crates/library_checker/src/tree/point_set_tree_path_composite_sum.rs (line 50)

    fn operate(x: &Self::T, y: &Self::T) -> Self::T {
        Path {
            a: x.a * y.a,
            b: x.b + x.a * y.b,
            sum: x.sum + x.a * y.sum + x.b * M::new_unchecked(y.cnt),
            cnt: x.cnt + y.cnt,
        }
    }
}
impl Unital for PathMonoid {
    fn unit() -> Self::T {
        Path {
            a: M::one(),
            b: M::zero(),
            sum: M::zero(),
            cnt: 0,
        }
    }
}
impl Associative for PathMonoid {}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct PathPair {
    forward: Path,
    reverse: Path,
}

struct PathPairMonoid;
impl Magma for PathPairMonoid {
    type T = PathPair;
    fn operate(x: &Self::T, y: &Self::T) -> Self::T {
        PathPair {
            forward: PathMonoid::operate(&x.forward, &y.forward),
            reverse: PathMonoid::operate(&y.reverse, &x.reverse),
        }
    }
}
impl Unital for PathPairMonoid {
    fn unit() -> Self::T {
        PathPair {
            forward: PathMonoid::unit(),
            reverse: PathMonoid::unit(),
        }
    }
}
impl Associative for PathPairMonoid {}

struct Dp;

impl MonoidCluster for Dp {
    type Vertex = M;
    type Edge = (M, M);
    type PointMonoid = PointMonoid;
    type PathMonoid = PathPairMonoid;

    fn add_vertex(point: &Point, vertex: &M, parent_edge: Option<&(M, M)>) -> PathPair {
        let cnt = point.cnt + 1;
        let subtotal = point.sum + *vertex;
        let (a, b) = parent_edge.copied().unwrap_or((M::one(), M::zero()));
        PathPair {
            forward: Path {
                a,
                b,
                sum: a * subtotal + b * M::new_unchecked(cnt),
                cnt,
            },
            reverse: Path {
                a,
                b,
                sum: subtotal,
                cnt,
            },
        }
    }

crates/library_checker/src/tree/point_set_tree_path_composite_sum_fixed_root.rs (line 50)

    fn operate(x: &Self::T, y: &Self::T) -> Self::T {
        Path {
            a: x.a * y.a,
            b: x.b + x.a * y.b,
            sum: x.sum + x.a * y.sum + x.b * M::new_unchecked(y.cnt),
            cnt: x.cnt + y.cnt,
        }
    }
}
impl Unital for PathMonoid {
    fn unit() -> Self::T {
        Path {
            a: M::one(),
            b: M::zero(),
            sum: M::zero(),
            cnt: 0,
        }
    }
}
impl Associative for PathMonoid {}

struct Dp;

impl MonoidCluster for Dp {
    type Vertex = M;
    type Edge = (M, M);
    type PointMonoid = PointMonoid;
    type PathMonoid = PathMonoid;

    fn add_vertex(point: &Point, vertex: &M, parent_edge: Option<&(M, M)>) -> Path {
        let cnt = point.cnt + 1;
        let subtotal = point.sum + *vertex;
        let (a, b) = parent_edge.copied().unwrap_or((M::one(), M::zero()));
        Path {
            a,
            b,
            sum: a * subtotal + b * M::new_unchecked(cnt),
            cnt,
        }
    }

crates/competitive/src/num/mint/mint_dot_product.rs (line 15)

    fn dot_product(x: &[MInt<Self>], y: &[MInt<Self>]) -> MInt<Self> {
        assert_eq!(x.len(), y.len());
        x.iter()
            .zip(y)
            .fold(MInt::new_unchecked(Self::mod_zero()), |sum, (&x, &y)| {
                sum + x * y
            })
    }

crates/library_checker/src/tree/tree_path_composite_sum.rs (line 18)

pub fn tree_path_composite_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, values: [M; n], (graph, edges): @TreeGraphScanner::<usize, (M, M)>::new(n));
    let dp = ReRooting::<(AdditiveOperation<M>, AdditiveOperation<i32>), _>::new_with_inverse(
        &graph,
        |&(sum, count), v, edge| {
            let sum = sum + values[v];
            let count = count + 1;
            if let Some(edge) = edge {
                let (a, b) = edges[edge];
                (a * sum + b * M::new_unchecked(count as u32), count)
            } else {
                (sum, count)
            }
        },
    );
    pp!(@it dp.dp.iter().map(|value| value.0));
}

Additional examples can be found in:

• crates/competitive/src/num/mint/montgomery_dot_product.rs
• crates/competitive/src/math/number_theoretic_transform.rs
• crates/competitive/src/num/mint/simd_matrix.rs

pub fn get_mod() -> M::Inner

pub fn pow(self, y: usize) -> Self

Examples found in repository

crates/competitive/src/math/formal_power_series/mod.rs (line 78)

    fn pow(self, exp: usize) -> Self {
        Self::pow(self, exp)
    }

crates/competitive/src/math/mint_matrix.rs (line 237)

    fn x_pow_mod(&self, k: usize) -> Self {
        let d = self.0.len() - 1;
        if d == 1 {
            return Self(vec![(-self.0[0]).pow(k)]);
        }
        let mut r = Self(vec![MInt::zero(); d]);
        r.0[0] = MInt::one();
        for bit in (0..usize::BITS - k.leading_zeros()).rev() {
            r = r.square_mod(self);
            if k >> bit & 1 != 0 {
                let x = r.0[d - 1];
                for i in (1..d).rev() {
                    r.0[i] = r.0[i - 1] - x * self.0[i];
                }
                r.0[0] = -x * self.0[0];
            }
        }
        r
    }

pub fn inv(self) -> Self

Examples found in repository

crates/competitive/src/math/factorial.rs (line 22)

    pub fn new(max_n: usize) -> Self {
        let mut fact = vec![MInt::one(); max_n + 1];
        let mut inv_fact = vec![MInt::one(); max_n + 1];
        for i in 2..=max_n {
            fact[i] = fact[i - 1] * MInt::from(i);
        }
        inv_fact[max_n] = fact[max_n].inv();
        for i in (3..=max_n).rev() {
            inv_fact[i - 1] = inv_fact[i] * MInt::from(i);
        }
        Self { fact, inv_fact }
    }

crates/competitive/src/math/black_box_mint_matrix.rs (line 80)

    fn black_box_linear_equation(&self, mut b: Vec<MInt<M>>) -> Option<Vec<MInt<M>>> {
        assert_eq!(self.shape().0, self.shape().1);
        assert_eq!(self.shape().1, b.len());
        let n = self.shape().0;
        let p = self.minimal_polynomial();
        if p.is_empty() || p[0].is_zero() {
            return None;
        }
        let p0_inv = p[0].inv();
        let mut x = vec![MInt::zero(); n];
        for p in p.into_iter().skip(1) {
            let p = -p * p0_inv;
            for i in 0..n {
                x[i] += p * b[i];
            }
            b = self.apply(&b);
        }
        Some(x)
    }

crates/library_checker/src/number_theory/sum_of_totient_function.rs (line 15)

pub fn sum_of_totient_function(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n: u64);
    let mut s = 1;
    let mut pp = 0;
    let mut pc = 0;
    let inv2 = M::new(2).inv();
    let qa = QuotientArray::from_fn(n, |i| [M::from(i), M::from(i) * M::from(i + 1) * inv2])
        .map(|[x, y]| [x - M::one(), y - M::one()])
        .lucy_dp::<ArrayOperation<AdditiveOperation<_>, 2>>(|[x, y], p| [x, y * M::from(p)])
        .map(|[x, y]| y - x)
        .min_25_sieve::<AddMulOperation<_>>(|p, c| {
            if pp != p || pc > c {
                pp = p;
                pc = 1;
                s = p - 1;
            }
            while pc < c {
                pc += 1;
                s *= p;
            }
            M::from(s)
        });
    pp!(qa[n]);
}

crates/competitive/src/math/binomial_prefix_sum.rs (line 75)

    pub fn for_each<F>(self, mut f: F)
    where
        F: FnMut(usize, MInt<M>),
    {
        let query = &self.query;
        if query.is_empty() {
            return;
        }
        let max_n = query.iter().map(|&(_, n)| n).max().unwrap_or(0);
        let modulus = M::mod_into();
        debug_assert!(modulus > 2 && modulus % 2 == 1);
        debug_assert!(max_n < modulus);
        debug_assert!(query.iter().all(|&(m, n)| m <= n));

        let fact = MemorizedFactorial::<M>::new(max_n);
        let inv2 = MInt::<M>::from(2usize).inv();
        let mut cur = MInt::<M>::one();
        crate::mo_algorithm!(
            query,
            (m, n),
            |old_m| cur += fact.combination(n, old_m + 1),
            |new_m| cur -= fact.combination(n, new_m + 1),
            |old_n| cur = cur + cur - fact.combination(old_n, m),
            |new_n| cur = (cur + fact.combination(new_n, m)) * inv2,
            |i| f(i, cur),
        );
    }

crates/competitive/src/math/lagrange_interpolation.rs (line 78)

pub fn lagrange_interpolation_polynomial<M>(x: &[MInt<M>], y: &[MInt<M>]) -> Vec<MInt<M>>
where
    M: MIntBase,
{
    let n = x.len() - 1;
    let mut dp = vec![MInt::zero(); n + 2];
    let mut ndp = vec![MInt::zero(); n + 2];
    dp[0] = -x[0];
    dp[1] = MInt::one();
    for x in x.iter().skip(1) {
        for j in 0..=n + 1 {
            ndp[j] = -dp[j] * x + if j >= 1 { dp[j - 1] } else { MInt::zero() };
        }
        std::mem::swap(&mut dp, &mut ndp);
    }
    let mut res = vec![MInt::zero(); n + 1];
    for i in 0..=n {
        let t = y[i]
            / (0..=n)
                .map(|j| if i != j { x[i] - x[j] } else { MInt::one() })
                .product::<MInt<M>>();
        if t.is_zero() {
            continue;
        } else if x[i].is_zero() {
            for j in 0..=n {
                res[j] += dp[j + 1] * t;
            }
        } else {
            let xinv = x[i].inv();
            let mut pre = MInt::zero();
            for j in 0..=n {
                let d = -(dp[j] - pre) * xinv;
                res[j] += d * t;
                pre = d;
            }
        }
    }
    res
}

crates/competitive/src/math/number_theoretic_transform.rs (line 778)

fn reconstruct_mint_crt<M, N1, N2, N3>(f: (MVec<N1>, MVec<N2>, MVec<N3>)) -> MVec<M>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    let t1 = MInt::<N2>::new(N1::get_mod()).inv();
    let m1_3 = MInt::<N3>::new(N1::get_mod());
    let t2 = (m1_3 * MInt::<N3>::new(N2::get_mod())).inv();
    let modulus = <M as MIntConvert<u32>>::mod_into() as u64;
    let m1 = N1::get_mod() as u64;
    let m2 = m1 * N2::get_mod() as u64 % modulus;
    let fits_u64 = (N1::get_mod() - 1) as u128
        + (N2::get_mod() - 1) as u128 * m1 as u128
        + (N3::get_mod() - 1) as u128 * m2 as u128
        <= u64::MAX as u128;
    f.0.into_iter()
        .zip(f.1)
        .zip(f.2)
        .map(|((c1, c2), c3)| {
            let d1 = c1.inner();
            let d2 = ((c2 - MInt::<N2>::from(d1)) * t1).inner();
            let x = MInt::<N3>::new(d1) + MInt::<N3>::new(d2) * m1_3;
            let d3 = ((c3 - x) * t2).inner();
            let value = if fits_u64 {
                (d1 as u64 + d2 as u64 * m1 + d3 as u64 * m2) % modulus
            } else {
                ((d1 as u128 + d2 as u128 * m1 as u128 + d3 as u128 * m2 as u128) % modulus as u128)
                    as u64
            };
            MInt::<M>::from(value as u32)
        })
        .collect()
}

impl<M, N1, N2, N3> ConvolveSteps for Convolve<(M, (N1, N2, N3))>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    type T = MVec<M>;
    type F = (MVec<N1>, MVec<N2>, MVec<N3>);
    fn length(t: &Self::T) -> usize {
        t.len()
    }
    fn transform(t: Self::T, len: usize) -> Self::F {
        let npot = len.max(1).next_power_of_two();
        let f = convert_crt_input(t, npot);
        (
            Convolve::<N1>::transform(f.0, npot),
            Convolve::<N2>::transform(f.1, npot),
            Convolve::<N3>::transform(f.2, npot),
        )
    }
    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        reconstruct_mint_crt((
            Convolve::<N1>::inverse_transform(f.0, len),
            Convolve::<N2>::inverse_transform(f.1, len),
            Convolve::<N3>::inverse_transform(f.2, len),
        ))
    }
    fn multiply(f: &mut Self::F, g: &Self::F) {
        Convolve::<N1>::multiply(&mut f.0, &g.0);
        Convolve::<N2>::multiply(&mut f.1, &g.1);
        Convolve::<N3>::multiply(&mut f.2, &g.2);
    }
    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        let max_len = Self::length(&a).max(Self::length(&b));
        let min_len = Self::length(&a).min(Self::length(&b));
        let (balanced, short) = crate::avx_helper!(@dispatch_avx2_fma (30, 10), (384, 128));
        if max_len <= balanced || min_len <= short {
            return convolve_karatsuba(&a, &b);
        }
        // Limit coefficient growth to leave headroom for FFT roundoff.
        let fft_limit = crate::avx_helper!(@dispatch_avx2_fma
            1usize << ((1u64 << 50) / <M as MIntConvert<u32>>::mod_into() as u64).ilog2().min(20), 0);
        let convolve = |a: Self::T, b: Self::T| {
            let fft_len = (a.len() + b.len() - 1).next_power_of_two();
            if fft_len <= 256 && a.len() * b.len() <= fft_len * 8 {
                return convolve_karatsuba(&a, &b);
            }
            if fft_len <= fft_limit {
                crate::avx_helper!(@dispatch_avx2_fma return unsafe {
                    convolve_mint_avx2(a, b)
                }, ());
            }
            convolve_mint_crt::<M, N1, N2, N3>(a, b)
        };
        let block_len = min_len.next_power_of_two() * 8 - min_len + 1;
        let block_len = if min_len <= fft_limit / 2 {
            block_len.min(fft_limit - min_len + 1)
        } else {
            block_len
        };
        if max_len <= block_len {
            return convolve(a, b);
        }
        let (a, b) = if a.len() >= b.len() { (a, b) } else { (b, a) };
        let mut result = vec![MInt::<M>::zero(); a.len() + b.len() - 1];
        for (i, a) in a.chunks(block_len).enumerate() {
            let product = convolve(a.to_vec(), b.clone());
            for (value, product) in result[i * block_len..].iter_mut().zip(product) {
                *value += product;
            }
        }
        result
    }
}

fn convolve_mint_crt<M, N1, N2, N3>(a: MVec<M>, b: MVec<M>) -> MVec<M>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    let convolve = |a: MVec<M>, b: MVec<M>| {
        let a_len = a.len();
        let b_len = b.len();
        let a = convert_crt_input(a, a_len);
        let b = convert_crt_input(b, b_len);
        reconstruct_mint_crt((
            Convolve::<N1>::convolve(a.0, b.0),
            Convolve::<N2>::convolve(a.1, b.1),
            Convolve::<N3>::convolve(a.2, b.2),
        ))
    };
    let modulus = <M as MIntConvert<u32>>::mod_into() as u128;
    let capacity = N1::MOD as u128 * N2::MOD as u128 * N3::MOD as u128;
    if a.len().min(b.len()) as u128 * (modulus - 1).pow(2) < capacity {
        return convolve(a, b);
    }
    let block_len = ((capacity - 1) / (modulus - 1).pow(2)) as usize;
    if block_len == 0 {
        return convolve_naive(&a, &b);
    }
    let mut result = vec![MInt::<M>::zero(); a.len() + b.len() - 1];
    for (i, a) in a.chunks(block_len).enumerate() {
        for (j, b) in b.chunks(block_len).enumerate() {
            let product = convolve(a.to_vec(), b.to_vec());
            for (value, product) in result[(i + j) * block_len..].iter_mut().zip(product) {
                *value += product;
            }
        }
    }
    result
}

impl<N1, N2, N3> ConvolveSteps for Convolve<(u64, (N1, N2, N3))>
where
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    type T = Vec<u64>;
    type F = ([MVec<N1>; 3], [MVec<N2>; 3], [MVec<N3>; 3]);

    fn length(t: &Self::T) -> usize {
        t.len()
    }

    fn transform(t: Self::T, len: usize) -> Self::F {
        let npot = len.max(1).next_power_of_two();
        assert!(npot <= 1usize << N1::RANK.min(N2::RANK).min(N3::RANK));
        // The 22-bit fallback needs room for three limb products per coefficient.
        assert!(
            3 * npot as u128 * ((1u128 << 22) - 1).pow(2)
                < N1::MOD as u128 * N2::MOD as u128 * N3::MOD as u128
        );
        let bits = if 2 * npot as u128 * (u32::MAX as u128).pow(2)
            < N1::MOD as u128 * N2::MOD as u128 * N3::MOD as u128
        {
            32
        } else {
            22
        };
        let parts = if bits == 32 && t.iter().all(|&value| value <= u32::MAX as u64) {
            1
        } else {
            64usize.div_ceil(bits)
        };
        fn split<M: Montgomery32NttModulus>(
            t: &[u64],
            len: usize,
            bits: usize,
            parts: usize,
        ) -> [MVec<M>; 3] {
            std::array::from_fn(|part| {
                if part >= parts {
                    return Vec::new();
                }
                Convolve::<M>::transform(
                    t.iter()
                        .map(|&t| MInt::from((t >> (part * bits)) & ((1u64 << bits) - 1)))
                        .collect(),
                    len,
                )
            })
        }
        (
            split(&t, npot, bits, parts),
            split(&t, npot, bits, parts),
            split(&t, npot, bits, parts),
        )
    }

    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        let bits = if f.0[2].is_empty() { 32 } else { 22 };
        let t1 = MInt::<N2>::new(N1::get_mod()).inv();
        let m1 = N1::get_mod() as u64;
        let m1_3 = MInt::<N3>::new(N1::get_mod());
        let t2 = (m1_3 * MInt::<N3>::new(N2::get_mod())).inv();
        let m2 = m1 * N2::get_mod() as u64;
        let mut result = vec![0u64; len.min(f.0[0].len())];
        for (part, ((f1, f2), f3)) in f.0.into_iter().zip(f.1).zip(f.2).enumerate() {
            if f1.is_empty() {
                continue;
            }
            for (value, ((c1, c2), c3)) in result.iter_mut().zip(
                Convolve::<N1>::inverse_transform(f1, len)
                    .into_iter()
                    .zip(Convolve::<N2>::inverse_transform(f2, len))
                    .zip(Convolve::<N3>::inverse_transform(f3, len)),
            ) {
                let d1 = c1.inner();
                let d2 = ((c2 - MInt::<N2>::from(d1)) * t1).inner();
                let x = MInt::<N3>::new(d1) + MInt::<N3>::new(d2) * m1_3;
                let d3 = ((c3 - x) * t2).inner();
                let limb = (d1 as u64)
                    .wrapping_add((d2 as u64).wrapping_mul(m1))
                    .wrapping_add((d3 as u64).wrapping_mul(m2));
                *value = value.wrapping_add(limb << (part * bits));
            }
        }
        result
    }

    fn multiply(f: &mut Self::F, g: &Self::F) {
        fn multiply<M: Montgomery32NttModulus>(f: &mut [MVec<M>; 3], g: &[MVec<M>; 3]) {
            assert_eq!(f[0].len(), g[0].len());
            if f[1].is_empty() || g[1].is_empty() {
                if f[1].is_empty() && !g[1].is_empty() {
                    f[1] = f[0].clone();
                    Convolve::<M>::multiply(&mut f[1], &g[1]);
                } else if !f[1].is_empty() {
                    Convolve::<M>::multiply(&mut f[1], &g[0]);
                }
                Convolve::<M>::multiply(&mut f[0], &g[0]);
                return;
            }
            #[cfg(target_arch = "x86_64")]
            if use_block_ntt::<M>(f[0].len()) {
                for part in (1..if f[2].is_empty() { 2 } else { 3 }).rev() {
                    let mut sum = f[0].clone();
                    Convolve::<M>::multiply(&mut sum, &g[part]);
                    for left in 1..=part {
                        let mut product = f[left].clone();
                        Convolve::<M>::multiply(&mut product, &g[part - left]);
                        for (value, product) in sum.iter_mut().zip(product) {
                            // Block products contain lazy Montgomery residues.
                            *value = MInt::new(value.inner() + product.inner());
                        }
                    }
                    f[part] = sum;
                }
                Convolve::<M>::multiply(&mut f[0], &g[0]);
                return;
            }
            if f[2].is_empty() {
                for i in 0..f[0].len() {
                    f[1][i] = f[0][i] * g[1][i] + f[1][i] * g[0][i];
                    f[0][i] *= g[0][i];
                }
                return;
            }
            for i in 0..f[0].len() {
                f[2][i] = f[0][i] * g[2][i] + f[1][i] * g[1][i] + f[2][i] * g[0][i];
                f[1][i] = f[0][i] * g[1][i] + f[1][i] * g[0][i];
                f[0][i] *= g[0][i];
            }
        }
        multiply(&mut f.0, &g.0);
        multiply(&mut f.1, &g.1);
        multiply(&mut f.2, &g.2);
    }

    fn square(t: Self::T, len: usize) -> Self::T {
        let mut f = Self::transform(t, len);
        let g = f.clone();
        Self::multiply(&mut f, &g);
        Self::inverse_transform(f, len)
    }

    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        let max_len = Self::length(&a).max(Self::length(&b));
        let min_len = Self::length(&a).min(Self::length(&b));
        let (balanced, short) = crate::avx_helper!(@dispatch_avx2_fma (300, 64), (1536, 512));
        if max_len <= balanced || min_len <= short {
            let a_wrapping: &[Wrapping<u64>] =
                unsafe { std::slice::from_raw_parts(a.as_ptr().cast(), a.len()) };
            let b_wrapping: &[Wrapping<u64>] =
                unsafe { std::slice::from_raw_parts(b.as_ptr().cast(), b.len()) };
            let mut c = std::mem::ManuallyDrop::new(if max_len <= 300 || min_len > 60 {
                convolve_karatsuba(a_wrapping, b_wrapping)
            } else {
                convolve_naive(a_wrapping, b_wrapping)
            });
            return unsafe { Vec::from_raw_parts(c.as_mut_ptr().cast(), c.len(), c.capacity()) };
        }
        let len = (Self::length(&a) + Self::length(&b)).saturating_sub(1);
        let block_len = if min_len >= 1 << 20 {
            1 << 20
        } else {
            (min_len.next_power_of_two() * 8).min(1 << 21) - min_len + 1
        };
        if max_len <= block_len {
            return convolve_u64_fft(a, b);
        }
        let mut result = vec![0u64; len];
        for (i, a) in a.chunks(block_len).enumerate() {
            for (j, b) in b.chunks(block_len).enumerate() {
                if a.len().min(b.len()) <= 60 {
                    for (x, &a) in a.iter().enumerate() {
                        for (y, &b) in b.iter().enumerate() {
                            let value = &mut result[(i + j) * block_len + x + y];
                            *value = value.wrapping_add(a.wrapping_mul(b));
                        }
                    }
                    continue;
                }
                let product = convolve_u64_fft(a.to_vec(), b.to_vec());
                for (value, product) in result[(i + j) * block_len..].iter_mut().zip(product) {
                    *value = value.wrapping_add(product);
                }
            }
        }
        result
    }
}

fn convolve_u64_fft(a: Vec<u64>, b: Vec<u64>) -> Vec<u64> {
    // Keep limb convolutions below 2^47 at the 2^21 FFT limit.
    crate::avx_helper!(@dispatch_avx2_fma return unsafe {
        convolve_u64_avx2(a, b)
    }, ());
    convolve_u64_fft_scalar(a, b)
}

fn convolve_u64_fft_scalar(a: Vec<u64>, b: Vec<u64>) -> Vec<u64> {
    fn split(values: &[u64]) -> [Vec<i64>; 5] {
        let mut result = std::array::from_fn(|_| Vec::with_capacity(values.len()));
        for mut value in values.iter().copied() {
            for part in &mut result {
                let digit = ((value << 51) as i64) >> 51;
                part.push(digit);
                value = (value >> 13).wrapping_add(u64::from(digit < 0));
            }
        }
        result
    }

    let len = a.len() + b.len() - 1;
    let transform = |values: &[u64]| {
        if values.iter().any(|&value| value > u32::MAX as u64) {
            return split(values).map(|part| ConvolveRealFft::transform(part, len));
        }
        let [a, b, c, _, _] = split(values);
        let a = ConvolveRealFft::transform(a, len);
        let size = a.len();
        [
            a,
            ConvolveRealFft::transform(b, len),
            ConvolveRealFft::transform(c, len),
            vec![Zero::zero(); size],
            vec![Zero::zero(); size],
        ]
    };
    let fa = transform(&a);
    drop(a);
    let fb = transform(&b);
    drop(b);
    let values: [Vec<i64>; 5] = std::array::from_fn(|part| {
        let mut sum = fa[0].clone();
        ConvolveRealFft::multiply(&mut sum, &fb[part]);
        for left in 1..=part {
            let mut product = fa[left].clone();
            ConvolveRealFft::multiply(&mut product, &fb[part - left]);
            for (sum, product) in sum.iter_mut().zip(product) {
                *sum += product;
            }
        }
        ConvolveRealFft::inverse_transform(sum, len)
    });
    (0..len)
        .map(|i| {
            (values[0][i] as u64)
                .wrapping_add((values[1][i] as u64) << 13)
                .wrapping_add((values[2][i] as u64) << 26)
                .wrapping_add((values[3][i] as u64) << 39)
                .wrapping_add((values[4][i] as u64) << 52)
        })
        .collect()
}

pub trait NttReuse: ConvolveSteps {
    const MULTIPLE: bool = true;

    /// Transforms coefficients into the usual NTT frequency order.
    fn transform_ntt(t: Self::T, len: usize) -> Self::F {
        Self::transform(t, len)
    }

    /// Inverts a value produced by `transform_ntt`.
    fn inverse_transform_ntt(f: Self::F, len: usize) -> Self::T {
        Self::inverse_transform(f, len)
    }

    /// Extends a value produced by `transform_ntt` to twice its length.
    /// If `monic`, the input represents a monic degree-`n` polynomial modulo
    /// `x^n - 1`, where `n` is the transform length.
    fn ntt_doubling(f: Self::F, monic: bool) -> Self::F;

    /// Extracts the even coefficients of `a(x) * b(-x)` in the usual NTT frequency order.
    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F;

    /// Extracts the odd coefficients of `a(x) * b(-x)` in the usual NTT frequency order.
    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F;

    /// Multiplies a usual NTT transform by the corresponding prefix of another one.
    fn multiply_prefix(f: &mut Self::F, g: &Self::F);

    /// Adds the pointwise product of two usual NTT transforms to `sum`.
    fn multiply_add(sum: &mut Self::F, f: &Self::F, g: &Self::F);

    /// Maximum number of products that can be summed before reconstruction.
    /// Both factors must transform canonical coefficients at the supplied transform's length,
    /// and each cyclic product must itself be reconstructible.
    fn max_product_sum_count(_f: &Self::F) -> usize {
        if Self::MULTIPLE { 1 } else { usize::MAX }
    }

    fn power_projection_step(
        p_flat: Self::T,
        q_flat: Self::T,
        n: usize,
        py: usize,
        qy: usize,
    ) -> (Self::T, Self::T) {
        let base = n * 2;
        let len_p = base * py;
        let len_q = base * qy;
        let len = (len_p + len_q - 1).max(len_q + len_q - 1);
        let half = len.max(1).next_power_of_two() / 2;

        let p_fft = Self::transform_ntt(p_flat, len);
        let q_fft = Self::transform_ntt(q_flat, len);
        let pr_fft = Self::odd_mul_normal_neg(&p_fft, &q_fft);
        let qr_fft = Self::even_mul_normal_neg(&q_fft, &q_fft);
        (
            Self::inverse_transform_ntt(pr_fft, half),
            Self::inverse_transform_ntt(qr_fft, half),
        )
    }
}

thread_local!(
    static BIT_REVERSE: UnsafeCell<Vec<Vec<usize>>> = const { UnsafeCell::new(vec![]) };
);

impl<M> NttReuse for Convolve<M>
where
    M: Montgomery32NttModulus,
{
    const MULTIPLE: bool = false;

    fn transform_ntt(mut t: Self::T, len: usize) -> Self::F {
        t.resize_with(len.max(1).next_power_of_two(), Zero::zero);
        ntt(&mut t);
        t
    }

    fn inverse_transform_ntt(mut f: Self::F, len: usize) -> Self::T {
        intt(&mut f);
        f.truncate(len);
        f
    }

    fn ntt_doubling(mut f: Self::F, monic: bool) -> Self::F {
        let n = f.len();
        let k = n.trailing_zeros() as usize;
        let mut a = Self::inverse_transform_ntt(f.clone(), n);
        if monic {
            a[0] -= MInt::<M>::from(2);
        }
        let zeta = MInt::<M>::new_unchecked(M::INFO.root[k + 1]);
        let zeta2 = zeta * zeta;
        let mut rot = [MInt::one(), zeta, zeta2, zeta2 * zeta];
        let step = zeta2 * zeta2;
        for a in a.chunks_mut(4) {
            for (a, rot) in a.iter_mut().zip(&mut rot) {
                *a *= *rot;
                *rot *= step;
            }
        }
        f.extend(Self::transform_ntt(a, n));
        f
    }

    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        assert_eq!(f.len(), g.len());
        assert!(f.len().is_power_of_two());
        assert!(f.len() >= 2);
        if std::ptr::eq(f, g) {
            return f.as_chunks::<2>().0.iter().map(|a| a[0] * a[1]).collect();
        }
        let inv2 = MInt::<M>::from(2).inv();
        let n = f.len() / 2;
        (0..n)
            .map(|i| (f[i << 1] * g[i << 1 | 1] + f[i << 1 | 1] * g[i << 1]) * inv2)
            .collect()
    }

    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        assert_eq!(f.len(), g.len());
        assert!(f.len().is_power_of_two());
        assert!(f.len() >= 2);
        let mut inv2 = MInt::<M>::from(2).inv();
        let n = f.len() / 2;
        let k = f.len().trailing_zeros() as usize;
        let mut h = vec![MInt::<M>::zero(); n];
        let w = MInt::<M>::new_unchecked(M::INFO.inv_root[k]);
        BIT_REVERSE.with(|br| {
            let br = unsafe { &mut *br.get() };
            if br.len() < k {
                br.resize_with(k, Default::default);
            }
            let k = k - 1;
            if br[k].is_empty() {
                let mut v = vec![0; 1 << k];
                for i in 0..1 << k {
                    v[i] = (v[i >> 1] >> 1) | ((i & 1) << k.saturating_sub(1));
                }
                br[k] = v;
            }
            for &i in &br[k] {
                h[i] = (f[i << 1] * g[i << 1 | 1] - f[i << 1 | 1] * g[i << 1]) * inv2;
                inv2 *= w;
            }
        });
        h
    }

    fn multiply_prefix(f: &mut Self::F, g: &Self::F) {
        pointwise_multiply(f, g);
    }

    fn multiply_add(sum: &mut Self::F, f: &Self::F, g: &Self::F) {
        assert!(sum.len() == f.len() && sum.len() == g.len());
        pointwise_multiply_add(sum, f, g);
    }

    fn power_projection_step(
        p_flat: Vec<MInt<M>>,
        q_flat: Vec<MInt<M>>,
        n: usize,
        py: usize,
        qy: usize,
    ) -> (Vec<MInt<M>>, Vec<MInt<M>>) {
        let high_degree = (qy - 1) * 2;
        let rows = (py + qy - 1).max(high_degree).next_power_of_two();
        let cols = n * 2;
        let size = rows * cols;
        let mut p = p_flat;
        p.resize_with(size, MInt::<M>::zero);
        ntt_rows(&mut p, cols);
        ntt_batch(&mut p, cols);

        let mut q = q_flat;
        q.resize_with(size, MInt::<M>::zero);
        ntt_rows(&mut q, cols);
        let q_high = (rows == high_degree).then(|| q[(qy - 1) * cols..qy * cols].to_vec());
        ntt_batch(&mut q, cols);

        let half = cols / 2;
        let mut odd_factor = vec![MInt::<M>::zero(); half];
        let mut factor = MInt::<M>::from(2).inv();
        let k = cols.trailing_zeros() as usize;
        let w = MInt::<M>::new_unchecked(M::INFO.inv_root[k]);
        BIT_REVERSE.with(|br| {
            let br = unsafe { &mut *br.get() };
            if br.len() < k {
                br.resize_with(k, Default::default);
            }
            let k = k - 1;
            if br[k].is_empty() {
                let mut v = vec![0; 1 << k];
                for i in 0..1 << k {
                    v[i] = (v[i >> 1] >> 1) | ((i & 1) << k.saturating_sub(1));
                }
                br[k] = v;
            }
            for &i in &br[k] {
                odd_factor[i] = factor;
                factor *= w;
            }
        });

        let mut pr = vec![MInt::<M>::zero(); rows * half];
        let mut qr = vec![MInt::<M>::zero(); rows * half];
        for i in 0..pr.len() {
            pr[i] = (p[i << 1] * q[i << 1 | 1] - p[i << 1 | 1] * q[i << 1])
                * odd_factor[i & (half - 1)];
            qr[i] = q[i << 1] * q[i << 1 | 1];
        }
        intt_batch(&mut pr, half);
        intt_rows(&mut pr, half);
        intt_batch(&mut qr, half);
        intt_rows(&mut qr, half);

        if let Some(q_high) = q_high {
            let mut q_high_even = vec![MInt::<M>::zero(); half];
            for i in 0..half {
                q_high_even[i] = q_high[i << 1] * q_high[i << 1 | 1];
            }
            intt(&mut q_high_even);
            for (value, high) in qr.iter_mut().zip(&q_high_even) {
                *value -= *high;
            }
            qr.extend_from_slice(&q_high_even);
        }
        (pr, qr)
    }
}

impl<M, N1, N2, N3> NttReuse for Convolve<(M, (N1, N2, N3))>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    fn max_product_sum_count(f: &Self::F) -> usize {
        let modulus = <M as MIntConvert<u32>>::mod_into() as u128;
        if modulus == 1 {
            return usize::MAX;
        }
        let capacity = N1::MOD as u128 * N2::MOD as u128 * N3::MOD as u128;
        ((capacity - 1) / ((modulus - 1) * (modulus - 1)) / f.0.len() as u128)
            .clamp(1, usize::MAX as u128) as usize
    }

    fn transform_ntt(t: Self::T, len: usize) -> Self::F {
        let npot = len.max(1).next_power_of_two();
        let f = convert_crt_input(t, npot);
        (
            Convolve::<N1>::transform_ntt(f.0, npot),
            Convolve::<N2>::transform_ntt(f.1, npot),
            Convolve::<N3>::transform_ntt(f.2, npot),
        )
    }

    fn inverse_transform_ntt(f: Self::F, len: usize) -> Self::T {
        reconstruct_mint_crt((
            Convolve::<N1>::inverse_transform_ntt(f.0, len),
            Convolve::<N2>::inverse_transform_ntt(f.1, len),
            Convolve::<N3>::inverse_transform_ntt(f.2, len),
        ))
    }

    fn ntt_doubling(f: Self::F, monic: bool) -> Self::F {
        if monic {
            let n = f.0.len();
            let mut coefficients = Self::inverse_transform_ntt(f, n);
            coefficients[0] -= MInt::<M>::one();
            coefficients.push(MInt::<M>::one());
            Self::transform_ntt(coefficients, n * 2)
        } else {
            (
                Convolve::<N1>::ntt_doubling(f.0, false),
                Convolve::<N2>::ntt_doubling(f.1, false),
                Convolve::<N3>::ntt_doubling(f.2, false),
            )
        }
    }

    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        fn even_mul_normal_neg_corrected<M>(f: &[MInt<M>], g: &[MInt<M>], m: u32) -> Vec<MInt<M>>
        where
            M: Montgomery32NttModulus,
        {
            let n = f.len();
            assert_eq!(f.len(), g.len());
            assert!(f.len().is_power_of_two());
            assert!(f.len() >= 2);
            let inv2 = MInt::<M>::from(2).inv();
            let u = MInt::<M>::new(m) * MInt::<M>::from(n as u32);
            let n = f.len() / 2;
            (0..n)
                .map(|i| {
                    (f[i << 1]
                        * if i == 0 {
                            g[i << 1 | 1] + u
                        } else {
                            g[i << 1 | 1]
                        }
                        + f[i << 1 | 1] * g[i << 1])
                        * inv2
                })
                .collect()
        }

        let m = M::mod_into();
        (
            even_mul_normal_neg_corrected(&f.0, &g.0, m),
            even_mul_normal_neg_corrected(&f.1, &g.1, m),
            even_mul_normal_neg_corrected(&f.2, &g.2, m),
        )
    }

    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        fn odd_mul_normal_neg_corrected<M>(f: &[MInt<M>], g: &[MInt<M>], m: u32) -> Vec<MInt<M>>
        where
            M: Montgomery32NttModulus,
        {
            assert_eq!(f.len(), g.len());
            assert!(f.len().is_power_of_two());
            assert!(f.len() >= 2);
            let mut inv2 = MInt::<M>::from(2).inv();
            let u = MInt::<M>::new(m) * MInt::<M>::from(f.len() as u32);
            let n = f.len() / 2;
            let k = f.len().trailing_zeros() as usize;
            let mut h = vec![MInt::<M>::zero(); n];
            let w = MInt::<M>::new_unchecked(M::INFO.inv_root[k]);
            BIT_REVERSE.with(|br| {
                let br = unsafe { &mut *br.get() };
                if br.len() < k {
                    br.resize_with(k, Default::default);
                }
                let k = k - 1;
                if br[k].is_empty() {
                    let mut v = vec![0; 1 << k];
                    for i in 0..1 << k {
                        v[i] = (v[i >> 1] >> 1) | ((i & 1) << k.saturating_sub(1));
                    }
                    br[k] = v;
                }
                for &i in &br[k] {
                    h[i] = (f[i << 1]
                        * if i == 0 {
                            g[i << 1 | 1] + u
                        } else {
                            g[i << 1 | 1]
                        }
                        - f[i << 1 | 1] * g[i << 1])
                        * inv2;
                    inv2 *= w;
                }
            });
            h
        }

Additional examples can be found in:

• crates/competitive/src/math/mint_matrix.rs

pub fn inner(self) -> M::Inner

Examples found in repository

crates/competitive/src/num/mint/mint_base.rs (line 107)

    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        Debug::fmt(&self.inner(), f)
    }
}
impl<M> Default for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn default() -> Self {
        <Self as Zero>::zero()
    }
}
impl<M> PartialEq for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn eq(&self, other: &Self) -> bool {
        PartialEq::eq(&self.x, &other.x)
    }
}
impl<M> Eq for MInt<M> where M: MIntBase {}
impl<M> Hash for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&self.x, state)
    }
}
macro_rules! impl_mint_from {
    ($($t:ty),*) => {
        $(impl<M> From<$t> for MInt<M>
        where
            M: MIntConvert<$t>,
        {
            #[inline]
            fn from(x: $t) -> Self {
                Self::new_unchecked(<M as MIntConvert<$t>>::from(x))
            }
        }
        impl<M> From<MInt<M>> for $t
        where
            M: MIntConvert<$t>,
        {
            #[inline]
            fn from(x: MInt<M>) -> $t {
                <M as MIntConvert<$t>>::into(x.x)
            }
        })*
    };
}
impl_mint_from!(
    u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize
);
impl<M> Zero for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn zero() -> Self {
        Self::new_unchecked(M::mod_zero())
    }
}
impl<M> One for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn one() -> Self {
        Self::new_unchecked(M::mod_one())
    }
}

impl<M> Add for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn add(self, rhs: Self) -> Self::Output {
        Self::new_unchecked(M::mod_add(self.x, rhs.x))
    }
}
impl<M> Sub for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn sub(self, rhs: Self) -> Self::Output {
        Self::new_unchecked(M::mod_sub(self.x, rhs.x))
    }
}
impl<M> Mul for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn mul(self, rhs: Self) -> Self::Output {
        Self::new_unchecked(M::mod_mul(self.x, rhs.x))
    }
}
impl<M> Div for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn div(self, rhs: Self) -> Self::Output {
        Self::new_unchecked(M::mod_div(self.x, rhs.x))
    }
}
impl<M> Neg for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn neg(self) -> Self::Output {
        Self::new_unchecked(M::mod_neg(self.x))
    }
}
impl<M> Sum for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
        iter.fold(<Self as Zero>::zero(), Add::add)
    }
}
impl<M> Product for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
        iter.fold(<Self as One>::one(), Mul::mul)
    }
}
impl<'a, M: 'a> Sum<&'a MInt<M>> for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
        iter.fold(<Self as Zero>::zero(), Add::add)
    }
}
impl<'a, M: 'a> Product<&'a MInt<M>> for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
        iter.fold(<Self as One>::one(), Mul::mul)
    }
}
impl<M> Display for MInt<M>
where
    M: MIntBase<Inner: Display>,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
        write!(f, "{}", self.inner())
    }

crates/competitive/src/num/mint/mod.rs (line 64)

    fn fast_print<W: std::io::Write>(&self, writer: &mut FastOutput<W>) {
        self.inner().fast_print(writer);
    }
}

#[codesnip::entry(when("MIntBase", "coding"))]
impl<M> SerdeByteStr for MInt<M>
where
    M: MIntBase<Inner: SerdeByteStr>,
{
    fn serialize(&self, buf: &mut Vec<u8>) {
        self.inner().serialize(buf)
    }

crates/competitive/src/math/number_theoretic_transform.rs (line 792)

fn reconstruct_mint_crt<M, N1, N2, N3>(f: (MVec<N1>, MVec<N2>, MVec<N3>)) -> MVec<M>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    let t1 = MInt::<N2>::new(N1::get_mod()).inv();
    let m1_3 = MInt::<N3>::new(N1::get_mod());
    let t2 = (m1_3 * MInt::<N3>::new(N2::get_mod())).inv();
    let modulus = <M as MIntConvert<u32>>::mod_into() as u64;
    let m1 = N1::get_mod() as u64;
    let m2 = m1 * N2::get_mod() as u64 % modulus;
    let fits_u64 = (N1::get_mod() - 1) as u128
        + (N2::get_mod() - 1) as u128 * m1 as u128
        + (N3::get_mod() - 1) as u128 * m2 as u128
        <= u64::MAX as u128;
    f.0.into_iter()
        .zip(f.1)
        .zip(f.2)
        .map(|((c1, c2), c3)| {
            let d1 = c1.inner();
            let d2 = ((c2 - MInt::<N2>::from(d1)) * t1).inner();
            let x = MInt::<N3>::new(d1) + MInt::<N3>::new(d2) * m1_3;
            let d3 = ((c3 - x) * t2).inner();
            let value = if fits_u64 {
                (d1 as u64 + d2 as u64 * m1 + d3 as u64 * m2) % modulus
            } else {
                ((d1 as u128 + d2 as u128 * m1 as u128 + d3 as u128 * m2 as u128) % modulus as u128)
                    as u64
            };
            MInt::<M>::from(value as u32)
        })
        .collect()
}

impl<M, N1, N2, N3> ConvolveSteps for Convolve<(M, (N1, N2, N3))>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    type T = MVec<M>;
    type F = (MVec<N1>, MVec<N2>, MVec<N3>);
    fn length(t: &Self::T) -> usize {
        t.len()
    }
    fn transform(t: Self::T, len: usize) -> Self::F {
        let npot = len.max(1).next_power_of_two();
        let f = convert_crt_input(t, npot);
        (
            Convolve::<N1>::transform(f.0, npot),
            Convolve::<N2>::transform(f.1, npot),
            Convolve::<N3>::transform(f.2, npot),
        )
    }
    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        reconstruct_mint_crt((
            Convolve::<N1>::inverse_transform(f.0, len),
            Convolve::<N2>::inverse_transform(f.1, len),
            Convolve::<N3>::inverse_transform(f.2, len),
        ))
    }
    fn multiply(f: &mut Self::F, g: &Self::F) {
        Convolve::<N1>::multiply(&mut f.0, &g.0);
        Convolve::<N2>::multiply(&mut f.1, &g.1);
        Convolve::<N3>::multiply(&mut f.2, &g.2);
    }
    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        let max_len = Self::length(&a).max(Self::length(&b));
        let min_len = Self::length(&a).min(Self::length(&b));
        let (balanced, short) = crate::avx_helper!(@dispatch_avx2_fma (30, 10), (384, 128));
        if max_len <= balanced || min_len <= short {
            return convolve_karatsuba(&a, &b);
        }
        // Limit coefficient growth to leave headroom for FFT roundoff.
        let fft_limit = crate::avx_helper!(@dispatch_avx2_fma
            1usize << ((1u64 << 50) / <M as MIntConvert<u32>>::mod_into() as u64).ilog2().min(20), 0);
        let convolve = |a: Self::T, b: Self::T| {
            let fft_len = (a.len() + b.len() - 1).next_power_of_two();
            if fft_len <= 256 && a.len() * b.len() <= fft_len * 8 {
                return convolve_karatsuba(&a, &b);
            }
            if fft_len <= fft_limit {
                crate::avx_helper!(@dispatch_avx2_fma return unsafe {
                    convolve_mint_avx2(a, b)
                }, ());
            }
            convolve_mint_crt::<M, N1, N2, N3>(a, b)
        };
        let block_len = min_len.next_power_of_two() * 8 - min_len + 1;
        let block_len = if min_len <= fft_limit / 2 {
            block_len.min(fft_limit - min_len + 1)
        } else {
            block_len
        };
        if max_len <= block_len {
            return convolve(a, b);
        }
        let (a, b) = if a.len() >= b.len() { (a, b) } else { (b, a) };
        let mut result = vec![MInt::<M>::zero(); a.len() + b.len() - 1];
        for (i, a) in a.chunks(block_len).enumerate() {
            let product = convolve(a.to_vec(), b.clone());
            for (value, product) in result[i * block_len..].iter_mut().zip(product) {
                *value += product;
            }
        }
        result
    }
}

fn convolve_mint_crt<M, N1, N2, N3>(a: MVec<M>, b: MVec<M>) -> MVec<M>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    let convolve = |a: MVec<M>, b: MVec<M>| {
        let a_len = a.len();
        let b_len = b.len();
        let a = convert_crt_input(a, a_len);
        let b = convert_crt_input(b, b_len);
        reconstruct_mint_crt((
            Convolve::<N1>::convolve(a.0, b.0),
            Convolve::<N2>::convolve(a.1, b.1),
            Convolve::<N3>::convolve(a.2, b.2),
        ))
    };
    let modulus = <M as MIntConvert<u32>>::mod_into() as u128;
    let capacity = N1::MOD as u128 * N2::MOD as u128 * N3::MOD as u128;
    if a.len().min(b.len()) as u128 * (modulus - 1).pow(2) < capacity {
        return convolve(a, b);
    }
    let block_len = ((capacity - 1) / (modulus - 1).pow(2)) as usize;
    if block_len == 0 {
        return convolve_naive(&a, &b);
    }
    let mut result = vec![MInt::<M>::zero(); a.len() + b.len() - 1];
    for (i, a) in a.chunks(block_len).enumerate() {
        for (j, b) in b.chunks(block_len).enumerate() {
            let product = convolve(a.to_vec(), b.to_vec());
            for (value, product) in result[(i + j) * block_len..].iter_mut().zip(product) {
                *value += product;
            }
        }
    }
    result
}

impl<N1, N2, N3> ConvolveSteps for Convolve<(u64, (N1, N2, N3))>
where
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    type T = Vec<u64>;
    type F = ([MVec<N1>; 3], [MVec<N2>; 3], [MVec<N3>; 3]);

    fn length(t: &Self::T) -> usize {
        t.len()
    }

    fn transform(t: Self::T, len: usize) -> Self::F {
        let npot = len.max(1).next_power_of_two();
        assert!(npot <= 1usize << N1::RANK.min(N2::RANK).min(N3::RANK));
        // The 22-bit fallback needs room for three limb products per coefficient.
        assert!(
            3 * npot as u128 * ((1u128 << 22) - 1).pow(2)
                < N1::MOD as u128 * N2::MOD as u128 * N3::MOD as u128
        );
        let bits = if 2 * npot as u128 * (u32::MAX as u128).pow(2)
            < N1::MOD as u128 * N2::MOD as u128 * N3::MOD as u128
        {
            32
        } else {
            22
        };
        let parts = if bits == 32 && t.iter().all(|&value| value <= u32::MAX as u64) {
            1
        } else {
            64usize.div_ceil(bits)
        };
        fn split<M: Montgomery32NttModulus>(
            t: &[u64],
            len: usize,
            bits: usize,
            parts: usize,
        ) -> [MVec<M>; 3] {
            std::array::from_fn(|part| {
                if part >= parts {
                    return Vec::new();
                }
                Convolve::<M>::transform(
                    t.iter()
                        .map(|&t| MInt::from((t >> (part * bits)) & ((1u64 << bits) - 1)))
                        .collect(),
                    len,
                )
            })
        }
        (
            split(&t, npot, bits, parts),
            split(&t, npot, bits, parts),
            split(&t, npot, bits, parts),
        )
    }

    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        let bits = if f.0[2].is_empty() { 32 } else { 22 };
        let t1 = MInt::<N2>::new(N1::get_mod()).inv();
        let m1 = N1::get_mod() as u64;
        let m1_3 = MInt::<N3>::new(N1::get_mod());
        let t2 = (m1_3 * MInt::<N3>::new(N2::get_mod())).inv();
        let m2 = m1 * N2::get_mod() as u64;
        let mut result = vec![0u64; len.min(f.0[0].len())];
        for (part, ((f1, f2), f3)) in f.0.into_iter().zip(f.1).zip(f.2).enumerate() {
            if f1.is_empty() {
                continue;
            }
            for (value, ((c1, c2), c3)) in result.iter_mut().zip(
                Convolve::<N1>::inverse_transform(f1, len)
                    .into_iter()
                    .zip(Convolve::<N2>::inverse_transform(f2, len))
                    .zip(Convolve::<N3>::inverse_transform(f3, len)),
            ) {
                let d1 = c1.inner();
                let d2 = ((c2 - MInt::<N2>::from(d1)) * t1).inner();
                let x = MInt::<N3>::new(d1) + MInt::<N3>::new(d2) * m1_3;
                let d3 = ((c3 - x) * t2).inner();
                let limb = (d1 as u64)
                    .wrapping_add((d2 as u64).wrapping_mul(m1))
                    .wrapping_add((d3 as u64).wrapping_mul(m2));
                *value = value.wrapping_add(limb << (part * bits));
            }
        }
        result
    }

    fn multiply(f: &mut Self::F, g: &Self::F) {
        fn multiply<M: Montgomery32NttModulus>(f: &mut [MVec<M>; 3], g: &[MVec<M>; 3]) {
            assert_eq!(f[0].len(), g[0].len());
            if f[1].is_empty() || g[1].is_empty() {
                if f[1].is_empty() && !g[1].is_empty() {
                    f[1] = f[0].clone();
                    Convolve::<M>::multiply(&mut f[1], &g[1]);
                } else if !f[1].is_empty() {
                    Convolve::<M>::multiply(&mut f[1], &g[0]);
                }
                Convolve::<M>::multiply(&mut f[0], &g[0]);
                return;
            }
            #[cfg(target_arch = "x86_64")]
            if use_block_ntt::<M>(f[0].len()) {
                for part in (1..if f[2].is_empty() { 2 } else { 3 }).rev() {
                    let mut sum = f[0].clone();
                    Convolve::<M>::multiply(&mut sum, &g[part]);
                    for left in 1..=part {
                        let mut product = f[left].clone();
                        Convolve::<M>::multiply(&mut product, &g[part - left]);
                        for (value, product) in sum.iter_mut().zip(product) {
                            // Block products contain lazy Montgomery residues.
                            *value = MInt::new(value.inner() + product.inner());
                        }
                    }
                    f[part] = sum;
                }
                Convolve::<M>::multiply(&mut f[0], &g[0]);
                return;
            }
            if f[2].is_empty() {
                for i in 0..f[0].len() {
                    f[1][i] = f[0][i] * g[1][i] + f[1][i] * g[0][i];
                    f[0][i] *= g[0][i];
                }
                return;
            }
            for i in 0..f[0].len() {
                f[2][i] = f[0][i] * g[2][i] + f[1][i] * g[1][i] + f[2][i] * g[0][i];
                f[1][i] = f[0][i] * g[1][i] + f[1][i] * g[0][i];
                f[0][i] *= g[0][i];
            }
        }

impl MInt<DynModuloU32>

pub fn set_mod(m: u32)

Examples found in repository

crates/library_checker/src/number_theory/sqrt_mod.rs (line 9)

pub fn sqrt_mod(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(q, yp: [(u32, u32); iter q]);
    for (y, p) in yp {
        DynMIntU32::set_mod(p);
        if let Some(x) = DynMIntU32::from(y).sqrt() {
            pp!(x);
        } else {
            pp!("-1");
        }
    }
}

crates/library_checker/src/enumerative_combinatorics/binomial_coefficient_prime_mod.rs (line 8)

pub fn binomial_coefficient_prime_mod(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(t, m: u32, nk: [(usize, usize); t]);
    DynMIntU32::set_mod(m);
    let max_n = nk.iter().map(|(n, _)| n).max().cloned().unwrap_or_default();
    let f = MemorizedFactorial::new(max_n);
    for (n, k) in nk {
        let ans: DynMIntU32 = f.combination(n, k);
        pp!(ans);
    }
}

impl MInt<DynModuloU64>

pub fn set_mod(m: u64)

impl<M> MInt<M>

where M: MIntBase<Inner = u32>,

pub unsafe fn matrix_product_avx2( a: &[Vec<Self>], b: &[Vec<Self>], scale: u32, ) -> Vec<Vec<Self>>

Safety

AVX2 must be available. The modulus must be odd, greater than one and below 2^30. scale must be below the modulus; entries must have canonical raw representations.

Examples found in repository

crates/competitive/src/num/mint/montgomery_dot_product.rs (line 22)

    fn try_matrix_product(
        _a: &[Vec<MInt<Self>>],
        _b: &[Vec<MInt<Self>>],
    ) -> Option<Vec<Vec<MInt<Self>>>> {
        #[cfg(target_arch = "x86_64")]
        if _a.len() >= 32
            && _b.len() >= 32
            && _b[0].len() >= 32
            && <Self as MontgomeryReduction32>::MOD > 1
            && <Self as MontgomeryReduction32>::MOD < 1 << 30
            && <Self as MontgomeryReduction32>::MOD % 2 == 1
            && is_x86_feature_detected!("avx2")
        {
            return Some(unsafe { MInt::matrix_product_avx2(_a, _b, 1) });
        }
        None
    }

Trait Implementations

impl<M> Add for MInt<M>

where M: MIntBase,

type Output = MInt<M>

The resulting type after applying the + operator.

fn add(self, rhs: Self) -> Self::Output

Performs the + operation.

impl<M> Add<&MInt<M>> for MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Add>::Output

The resulting type after applying the + operator.

fn add(self, other: &MInt<M>) -> <MInt<M> as Add<MInt<M>>>::Output

Performs the + operation.

impl<M> Add<&MInt<M>> for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Add>::Output

The resulting type after applying the + operator.

fn add(self, other: &MInt<M>) -> <MInt<M> as Add<MInt<M>>>::Output

Performs the + operation.

impl<M> Add<MInt<M>> for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Add>::Output

The resulting type after applying the + operator.

fn add(self, other: MInt<M>) -> <MInt<M> as Add<MInt<M>>>::Output

Performs the + operation.

impl<M> AddAssign for MInt<M>

where M: MIntBase,

fn add_assign(&mut self, rhs: MInt<M>)

Performs the += operation.

impl<M> AddAssign<&MInt<M>> for MInt<M>

where M: MIntBase,

fn add_assign(&mut self, other: &MInt<M>)

Performs the += operation.

impl<M> Clone for MInt<M>

where M: MIntBase,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<M> Copy for MInt<M>

where M: MIntBase,

impl<M> Debug for MInt<M>

where M: MIntBase,

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

Formats the value using the given formatter.

impl<M> Default for MInt<M>

where M: MIntBase,

fn default() -> Self

Returns the “default value” for a type.

impl<M> Display for MInt<M>

where M: MIntBase<Inner: Display>,

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

Formats the value using the given formatter.

impl<M> Div for MInt<M>

where M: MIntBase,

type Output = MInt<M>

The resulting type after applying the / operator.

fn div(self, rhs: Self) -> Self::Output

Performs the / operation.

impl<M> Div<&MInt<M>> for MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Div>::Output

The resulting type after applying the / operator.

fn div(self, other: &MInt<M>) -> <MInt<M> as Div<MInt<M>>>::Output

Performs the / operation.

impl<M> Div<&MInt<M>> for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Div>::Output

The resulting type after applying the / operator.

fn div(self, other: &MInt<M>) -> <MInt<M> as Div<MInt<M>>>::Output

Performs the / operation.

impl<M> Div<MInt<M>> for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Div>::Output

The resulting type after applying the / operator.

fn div(self, other: MInt<M>) -> <MInt<M> as Div<MInt<M>>>::Output

Performs the / operation.

impl<M> DivAssign for MInt<M>

where M: MIntBase,

fn div_assign(&mut self, rhs: MInt<M>)

Performs the /= operation.

impl<M> DivAssign<&MInt<M>> for MInt<M>

where M: MIntBase,

fn div_assign(&mut self, other: &MInt<M>)

Performs the /= operation.

impl<M> DotProduct for MInt<M>

where M: MIntDotProduct,

fn try_matrix_product( a: &[Vec<Self>], b: &[Vec<Self>], ) -> Option<Vec<Vec<Self>>>

fn dot_product(x: &[Self], y: &[Self]) -> Self

fn add_scaled_assign(x: &mut [Self], y: &[Self], a: &Self)

impl<M> Eq for MInt<M>

where M: MIntBase,

impl<M> FastPrint for MInt<M>

where M: MIntBase<Inner: FastPrint>,

fn fast_print<W: Write>(&self, writer: &mut FastOutput<W>)

impl<M> FormalPowerSeriesCoefficient for MInt<M>

where M: MIntConvert<usize> + MIntConvert<isize>,

type Base = M

fn pow(self, exp: usize) -> Self

fn memorized_fact(mf: &MemorizedFactorial<Self::Base>) -> &[Self]

fn memorized_inv_fact(mf: &MemorizedFactorial<Self::Base>) -> &[Self]

fn memorized_inv(mf: &MemorizedFactorial<Self::Base>, n: usize) -> Self

fn signed_pow(self, exp: isize) -> Self

fn memorized_factorial(n: usize) -> MemorizedFactorial<Self::Base>

impl<M> FormalPowerSeriesCoefficientSqrt for MInt<M>

where M: MIntConvert<u32> + MIntConvert<usize> + MIntConvert<isize>,

fn sqrt_coefficient(&self) -> Option<Self>

impl<M> From<MInt<M>> for u8

where M: MIntConvert<u8>,

fn from(x: MInt<M>) -> u8

Converts to this type from the input type.

impl<M> From<MInt<M>> for u16

where M: MIntConvert<u16>,

fn from(x: MInt<M>) -> u16

Converts to this type from the input type.

impl<M> From<MInt<M>> for u32

where M: MIntConvert<u32>,

fn from(x: MInt<M>) -> u32

Converts to this type from the input type.

impl<M> From<MInt<M>> for u64

where M: MIntConvert<u64>,

fn from(x: MInt<M>) -> u64

Converts to this type from the input type.

impl<M> From<MInt<M>> for u128

where M: MIntConvert<u128>,

fn from(x: MInt<M>) -> u128

Converts to this type from the input type.

impl<M> From<MInt<M>> for usize

where M: MIntConvert<usize>,

fn from(x: MInt<M>) -> usize

Converts to this type from the input type.

impl<M> From<MInt<M>> for i8

where M: MIntConvert<i8>,

fn from(x: MInt<M>) -> i8

Converts to this type from the input type.

impl<M> From<MInt<M>> for i16

where M: MIntConvert<i16>,

fn from(x: MInt<M>) -> i16

Converts to this type from the input type.

impl<M> From<MInt<M>> for i32

where M: MIntConvert<i32>,

fn from(x: MInt<M>) -> i32

Converts to this type from the input type.

impl<M> From<MInt<M>> for i64

where M: MIntConvert<i64>,

fn from(x: MInt<M>) -> i64

Converts to this type from the input type.

impl<M> From<MInt<M>> for i128

where M: MIntConvert<i128>,

fn from(x: MInt<M>) -> i128

Converts to this type from the input type.

impl<M> From<MInt<M>> for isize

where M: MIntConvert<isize>,

fn from(x: MInt<M>) -> isize

Converts to this type from the input type.

impl<M> From<i8> for MInt<M>

where M: MIntConvert<i8>,

fn from(x: i8) -> Self

Converts to this type from the input type.

impl<M> From<i16> for MInt<M>

where M: MIntConvert<i16>,

fn from(x: i16) -> Self

Converts to this type from the input type.

impl<M> From<i32> for MInt<M>

where M: MIntConvert<i32>,

fn from(x: i32) -> Self

Converts to this type from the input type.

impl<M> From<i64> for MInt<M>

where M: MIntConvert<i64>,

fn from(x: i64) -> Self

Converts to this type from the input type.

impl<M> From<i128> for MInt<M>

where M: MIntConvert<i128>,

fn from(x: i128) -> Self

Converts to this type from the input type.

impl<M> From<isize> for MInt<M>

where M: MIntConvert<isize>,

fn from(x: isize) -> Self

Converts to this type from the input type.

impl<M> From<u8> for MInt<M>

where M: MIntConvert<u8>,

fn from(x: u8) -> Self

Converts to this type from the input type.

impl<M> From<u16> for MInt<M>

where M: MIntConvert<u16>,

fn from(x: u16) -> Self

Converts to this type from the input type.

impl<M> From<u32> for MInt<M>

where M: MIntConvert<u32>,

fn from(x: u32) -> Self

Converts to this type from the input type.

impl<M> From<u64> for MInt<M>

where M: MIntConvert<u64>,

fn from(x: u64) -> Self

Converts to this type from the input type.

impl<M> From<u128> for MInt<M>

where M: MIntConvert<u128>,

fn from(x: u128) -> Self

Converts to this type from the input type.

impl<M> From<usize> for MInt<M>

where M: MIntConvert<usize>,

fn from(x: usize) -> Self

Converts to this type from the input type.

impl<M> FromStr for MInt<M>

where M: MIntConvert + MIntBase<Inner: FromStr>,

type Err = <<M as MIntBase>::Inner as FromStr>::Err

The associated error which can be returned from parsing.

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

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

impl<M> Hash for MInt<M>

where M: MIntBase,

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<M> Mul for MInt<M>

where M: MIntBase,

type Output = MInt<M>

The resulting type after applying the * operator.

fn mul(self, rhs: Self) -> Self::Output

Performs the * operation.

impl<M> Mul<&MInt<M>> for MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Mul>::Output

The resulting type after applying the * operator.

fn mul(self, other: &MInt<M>) -> <MInt<M> as Mul<MInt<M>>>::Output

Performs the * operation.

impl<M> Mul<&MInt<M>> for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Mul>::Output

The resulting type after applying the * operator.

fn mul(self, other: &MInt<M>) -> <MInt<M> as Mul<MInt<M>>>::Output

Performs the * operation.

impl<M> Mul<MInt<M>> for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Mul>::Output

The resulting type after applying the * operator.

fn mul(self, other: MInt<M>) -> <MInt<M> as Mul<MInt<M>>>::Output

Performs the * operation.

impl<M> MulAssign for MInt<M>

where M: MIntBase,

fn mul_assign(&mut self, rhs: MInt<M>)

Performs the *= operation.

impl<M> MulAssign<&MInt<M>> for MInt<M>

where M: MIntBase,

fn mul_assign(&mut self, other: &MInt<M>)

Performs the *= operation.

impl<M> Neg for MInt<M>

where M: MIntBase,

type Output = MInt<M>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<M> Neg for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Neg>::Output

The resulting type after applying the - operator.

fn neg(self) -> <MInt<M> as Neg>::Output

Performs the unary - operation.

impl<M> One for MInt<M>

where M: MIntBase,

fn one() -> Self

fn is_one(&self) -> bool

where Self: PartialEq,

fn set_one(&mut self)

impl<M> PartialEq for MInt<M>

where M: MIntBase,

fn eq(&self, other: &Self) -> bool

Equality operator ==.

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

Inequality operator !=.

impl<M> Product for MInt<M>

where M: MIntBase,

fn product<I: Iterator<Item = Self>>(iter: I) -> Self

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

impl<'a, M> Product<&'a MInt<M>> for MInt<M>

where M: MIntBase + 'a,

fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self

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

impl<M> RandomSpec<MInt<M>> for RangeFull

where M: MIntBase, RangeTo<M::Inner>: RandomSpec<M::Inner>,

fn rand(&self, rng: &mut Xorshift) -> MInt<M>

Return a random value.

fn rand_iter(self, rng: &mut Xorshift) -> RandIter<'_, T, Self>

Return an iterator that generates random values.

impl<M> Scan for MInt<M>

where M: MIntConvert + MIntBase<Inner: Scan<Output = M::Inner>>,

type Output = MInt<M>

fn scan<S: ScanSource>(source: &mut S) -> Option<Self>

impl<M> SerdeByteStr for MInt<M>

where M: MIntBase<Inner: SerdeByteStr>,

fn serialize(&self, buf: &mut Vec<u8>)

fn deserialize<I>(iter: &mut I) -> Self

where I: Iterator<Item = u8>,

fn serialize_bytestr(&self) -> String

fn deserialize_from_bytes(bytes: &[u8]) -> Self

where Self: Sized,

impl<M> Sub for MInt<M>

where M: MIntBase,

type Output = MInt<M>

The resulting type after applying the - operator.

fn sub(self, rhs: Self) -> Self::Output

Performs the - operation.

impl<M> Sub<&MInt<M>> for MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Sub>::Output

The resulting type after applying the - operator.

fn sub(self, other: &MInt<M>) -> <MInt<M> as Sub<MInt<M>>>::Output

Performs the - operation.

impl<M> Sub<&MInt<M>> for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Sub>::Output

The resulting type after applying the - operator.

fn sub(self, other: &MInt<M>) -> <MInt<M> as Sub<MInt<M>>>::Output

Performs the - operation.

impl<M> Sub<MInt<M>> for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Sub>::Output

The resulting type after applying the - operator.

fn sub(self, other: MInt<M>) -> <MInt<M> as Sub<MInt<M>>>::Output

Performs the - operation.

impl<M> SubAssign for MInt<M>

where M: MIntBase,

fn sub_assign(&mut self, rhs: MInt<M>)

Performs the -= operation.

impl<M> SubAssign<&MInt<M>> for MInt<M>

where M: MIntBase,

fn sub_assign(&mut self, other: &MInt<M>)

Performs the -= operation.

impl<M> Sum for MInt<M>

where M: MIntBase,

fn sum<I: Iterator<Item = Self>>(iter: I) -> Self

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

impl<'a, M> Sum<&'a MInt<M>> for MInt<M>

where M: MIntBase + 'a,

fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self

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

impl<M> Zero for MInt<M>

where M: MIntBase,

fn zero() -> Self

fn is_zero(&self) -> bool

where Self: PartialEq,

fn set_zero(&mut self)