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 12)

pub fn sqrt_mod(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, q, yp: [(u32, u32)]);
    for (y, p) in yp.take(q) {
        DynMIntU32::set_mod(p);
        if let Some(x) = DynMIntU32::from(y).sqrt() {
            writeln!(writer, "{}", x).ok();
        } else {
            writeln!(writer, "-1").ok();
        }
    }
}

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 19)

pub fn sum_of_totient_function(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, 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)
        });
    writeln!(writer, "{}", qa[n]).ok();
}

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

    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        let t1 = MInt::<N2>::new(N1::get_mod()).inv();
        let m1 = MInt::<M>::from(N1::get_mod());
        let m1_3 = MInt::<N3>::new(N1::get_mod());
        let t2 = (m1_3 * MInt::<N3>::new(N2::get_mod())).inv();
        let m2 = m1 * MInt::<M>::from(N2::get_mod());
        Convolve::<N1>::inverse_transform(f.0, len)
            .into_iter()
            .zip(Convolve::<N2>::inverse_transform(f.1, len))
            .zip(Convolve::<N3>::inverse_transform(f.2, len))
            .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();
                MInt::<M>::from(d1) + MInt::<M>::from(d2) * m1 + MInt::<M>::from(d3) * m2
            })
            .collect()
    }
    fn multiply(f: &mut Self::F, g: &Self::F) {
        assert_eq!(f.0.len(), g.0.len());
        assert_eq!(f.1.len(), g.1.len());
        assert_eq!(f.2.len(), g.2.len());
        for (f, g) in f.0.iter_mut().zip(g.0.iter()) {
            *f *= *g;
        }
        for (f, g) in f.1.iter_mut().zip(g.1.iter()) {
            *f *= *g;
        }
        for (f, g) in f.2.iter_mut().zip(g.2.iter()) {
            *f *= *g;
        }
    }
    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        if Self::length(&a).max(Self::length(&b)) <= 300 {
            return convolve_karatsuba(&a, &b);
        }
        if Self::length(&a).min(Self::length(&b)) <= 60 {
            return convolve_naive(&a, &b);
        }
        let len = (Self::length(&a) + Self::length(&b)).saturating_sub(1);
        let mut a = Self::transform(a, len);
        let b = Self::transform(b, len);
        Self::multiply(&mut a, &b);
        Self::inverse_transform(a, len)
    }
}

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>, 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 mut f = (
            MVec::<N1>::with_capacity(npot),
            MVec::<N2>::with_capacity(npot),
            MVec::<N3>::with_capacity(npot),
        );
        for t in t {
            f.0.push(t.into());
            f.1.push(t.into());
            f.2.push(t.into());
        }
        f.0.resize_with(npot, Zero::zero);
        f.1.resize_with(npot, Zero::zero);
        f.2.resize_with(npot, Zero::zero);
        ntt(&mut f.0);
        ntt(&mut f.1);
        ntt(&mut f.2);
        f
    }

    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        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;
        Convolve::<N1>::inverse_transform(f.0, len)
            .into_iter()
            .zip(Convolve::<N2>::inverse_transform(f.1, len))
            .zip(Convolve::<N3>::inverse_transform(f.2, len))
            .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();
                d1 as u64 + d2 as u64 * m1 + d3 as u64 * m2
            })
            .collect()
    }

    fn multiply(f: &mut Self::F, g: &Self::F) {
        assert_eq!(f.0.len(), g.0.len());
        assert_eq!(f.1.len(), g.1.len());
        assert_eq!(f.2.len(), g.2.len());
        for (f, g) in f.0.iter_mut().zip(g.0.iter()) {
            *f *= *g;
        }
        for (f, g) in f.1.iter_mut().zip(g.1.iter()) {
            *f *= *g;
        }
        for (f, g) in f.2.iter_mut().zip(g.2.iter()) {
            *f *= *g;
        }
    }

    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        if Self::length(&a).max(Self::length(&b)) <= 300 {
            return convolve_karatsuba(&a, &b);
        }
        if Self::length(&a).min(Self::length(&b)) <= 60 {
            return convolve_naive(&a, &b);
        }
        let len = (Self::length(&a) + Self::length(&b)).saturating_sub(1);
        let mut a = Self::transform(a, len);
        let b = Self::transform(b, len);
        Self::multiply(&mut a, &b);
        Self::inverse_transform(a, len)
    }
}

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

    /// F(a) → F(a + [0] * a.len())
    fn ntt_doubling(f: Self::F) -> Self::F;

    /// F(a(x)), F(b(x)) → even(F(a(x) * b(-x)))
    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F;

    /// F(a(x)), F(b(x)) → odd(F(a(x) * b(-x)))
    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F;
}

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 ntt_doubling(mut f: Self::F) -> Self::F {
        let n = f.len();
        let k = n.trailing_zeros() as usize;
        let mut a = Self::inverse_transform(f.clone(), n);
        let mut rot = MInt::<M>::one();
        let zeta = MInt::<M>::new_unchecked(M::INFO.root[k + 1]);
        for a in a.iter_mut() {
            *a *= rot;
            rot *= zeta;
        }
        f.extend(Self::transform(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);
        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
    }
}

impl<M, N1, N2, N3> NttReuse for Convolve<(M, (N1, N2, N3))>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    fn ntt_doubling(f: Self::F) -> Self::F {
        (
            Convolve::<N1>::ntt_doubling(f.0),
            Convolve::<N2>::ntt_doubling(f.1),
            Convolve::<N3>::ntt_doubling(f.2),
        )
    }

    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))
    }
}
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())
    }
}
impl<M> FromStr for MInt<M>
where
    M: MIntConvert + MIntBase<Inner: FromStr>,
{
    type Err = <M::Inner as FromStr>::Err;
    #[inline]
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        s.parse::<M::Inner>().map(Self::new)
    }
}
impl<M> IterScan for MInt<M>
where
    M: MIntConvert + MIntBase<Inner: FromStr>,
{
    type Output = Self;
    #[inline]
    fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
        iter.next()?.parse::<MInt<M>>().ok()
    }
}
impl<M> SerdeByteStr for MInt<M>
where
    M: MIntBase<Inner: SerdeByteStr>,
{
    fn serialize(&self, buf: &mut Vec<u8>) {
        self.inner().serialize(buf)
    }

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

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

        fn rand(&self, rng: &mut Xorshift) -> MInt<M> {
            MInt::<M>::new_unchecked(rng.random(..M::get_mod()))
        }

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

fn ntt_scalar<M>(a: &mut [MInt<M>])
where
    M: Montgomery32NttModulus,
{
    let n = a.len();
    let mut v = n / 2;
    let imag = MInt::<M>::new_unchecked(M::INFO.root[2]);
    while v > 1 {
        let mut w1 = MInt::<M>::one();
        for (s, a) in a.chunks_exact_mut(v << 1).enumerate() {
            let (l, r) = a.split_at_mut(v);
            let (ll, lr) = l.split_at_mut(v >> 1);
            let (rl, rr) = r.split_at_mut(v >> 1);
            let w2 = w1 * w1;
            let w3 = w1 * w2;
            for (((x0, x1), x2), x3) in ll.iter_mut().zip(lr).zip(rl).zip(rr) {
                let a0 = *x0;
                let a1 = *x1 * w1;
                let a2 = *x2 * w2;
                let a3 = *x3 * w3;
                let a0pa2 = a0 + a2;
                let a0na2 = a0 - a2;
                let a1pa3 = a1 + a3;
                let a1na3imag = (a1 - a3) * imag;
                *x0 = a0pa2 + a1pa3;
                *x1 = a0pa2 - a1pa3;
                *x2 = a0na2 + a1na3imag;
                *x3 = a0na2 - a1na3imag;
            }
            w1 *= MInt::<M>::new_unchecked(M::INFO.rate3[s.trailing_ones() as usize]);
        }
        v >>= 2;
    }
    if v == 1 {
        let mut w1 = MInt::<M>::one();
        for (s, a) in a.chunks_exact_mut(2).enumerate() {
            unsafe {
                let (l, r) = a.split_at_mut(1);
                let x0 = l.get_unchecked_mut(0);
                let x1 = r.get_unchecked_mut(0);
                let a0 = *x0;
                let a1 = *x1 * w1;
                *x0 = a0 + a1;
                *x1 = a0 - a1;
            }
            w1 *= MInt::<M>::new_unchecked(M::INFO.rate2[s.trailing_ones() as usize]);
        }
    }
}

fn intt_scalar<M>(a: &mut [MInt<M>])
where
    M: Montgomery32NttModulus,
{
    let n = a.len();
    let mut v = 1;
    if n.trailing_zeros() & 1 == 1 {
        let mut w1 = MInt::<M>::one();
        for (s, a) in a.chunks_exact_mut(2).enumerate() {
            unsafe {
                let (l, r) = a.split_at_mut(1);
                let x0 = l.get_unchecked_mut(0);
                let x1 = r.get_unchecked_mut(0);
                let a0 = *x0;
                let a1 = *x1;
                *x0 = a0 + a1;
                *x1 = (a0 - a1) * w1;
            }
            w1 *= MInt::<M>::new_unchecked(M::INFO.inv_rate2[s.trailing_ones() as usize]);
        }
        v <<= 1;
    }
    let iimag = MInt::<M>::new_unchecked(M::INFO.inv_root[2]);
    while v < n {
        let mut w1 = MInt::<M>::one();
        for (s, a) in a.chunks_exact_mut(v << 2).enumerate() {
            let (l, r) = a.split_at_mut(v << 1);
            let (ll, lr) = l.split_at_mut(v);
            let (rl, rr) = r.split_at_mut(v);
            let w2 = w1 * w1;
            let w3 = w1 * w2;
            for (((x0, x1), x2), x3) in ll.iter_mut().zip(lr).zip(rl).zip(rr) {
                let a0 = *x0;
                let a1 = *x1;
                let a2 = *x2;
                let a3 = *x3;
                let a0pa1 = a0 + a1;
                let a0na1 = a0 - a1;
                let a2pa3 = a2 + a3;
                let a2na3iimag = (a2 - a3) * iimag;
                *x0 = a0pa1 + a2pa3;
                *x1 = (a0na1 + a2na3iimag) * w1;
                *x2 = (a0pa1 - a2pa3) * w2;
                *x3 = (a0na1 - a2na3iimag) * w3;
            }
            w1 *= MInt::<M>::new_unchecked(M::INFO.inv_rate3[s.trailing_ones() as usize]);
        }
        v <<= 2;
    }
}

fn ntt<M>(a: &mut [MInt<M>])
where
    M: Montgomery32NttModulus,
{
    #[cfg(target_arch = "x86_64")]
    {
        match simd_backend() {
            SimdBackend::Avx512 => unsafe { ntt_simd::ntt_avx512::<M>(a) },
            SimdBackend::Avx2 => unsafe { ntt_simd::ntt_avx2::<M>(a) },
            SimdBackend::Scalar => ntt_scalar(a),
        }
    }
    #[cfg(not(target_arch = "x86_64"))]
    {
        ntt_scalar(a);
    }
}

fn intt<M>(a: &mut [MInt<M>])
where
    M: Montgomery32NttModulus,
{
    #[cfg(target_arch = "x86_64")]
    {
        match simd_backend() {
            SimdBackend::Avx512 => unsafe { ntt_simd::intt_avx512::<M>(a) },
            SimdBackend::Avx2 => unsafe { ntt_simd::intt_avx2::<M>(a) },
            SimdBackend::Scalar => intt_scalar(a),
        }
    }
    #[cfg(not(target_arch = "x86_64"))]
    {
        intt_scalar(a);
    }
}

#[cfg(target_arch = "x86_64")]
#[allow(unsafe_op_in_unsafe_fn)] // SIMD intrinsics and raw pointers are confined here
mod ntt_simd {
    use super::*;
    use std::arch::x86_64::*;

    const LAZY_THRESHOLD: u32 = 1 << 30;

    #[target_feature(enable = "avx2")]
    unsafe fn normalize_avx2<M>(a: &mut [u32])
    where
        M: Montgomery32NttModulus,
    {
        let mod_vec = _mm256_set1_epi32(M::MOD as i32);
        let sign = _mm256_set1_epi32(0x8000_0000u32 as i32);
        let mut i = 0;
        while i + 8 <= a.len() {
            let x = _mm256_loadu_si256(a.as_ptr().add(i) as *const __m256i);
            let x_x = _mm256_xor_si256(x, sign);
            let m_x = _mm256_xor_si256(mod_vec, sign);
            let gt = _mm256_cmpgt_epi32(x_x, m_x);
            let eq = _mm256_cmpeq_epi32(x, mod_vec);
            let mask = _mm256_or_si256(gt, eq);
            let sub = _mm256_and_si256(mod_vec, mask);
            let y = _mm256_sub_epi32(x, sub);
            _mm256_storeu_si256(a.as_mut_ptr().add(i) as *mut __m256i, y);
            i += 8;
        }
        while i < a.len() {
            let x = a[i];
            a[i] = if x >= M::MOD { x - M::MOD } else { x };
            i += 1;
        }
    }

    #[target_feature(enable = "avx512f,avx512dq,avx512cd,avx512bw,avx512vl")]
    unsafe fn normalize_avx512<M>(a: &mut [u32])
    where
        M: Montgomery32NttModulus,
    {
        let mod_vec = _mm512_set1_epi32(M::MOD as i32);
        let mut i = 0;
        while i + 16 <= a.len() {
            let x = _mm512_loadu_si512(a.as_ptr().add(i) as *const __m512i);
            let mask = !_mm512_cmp_epu32_mask(x, mod_vec, _MM_CMPINT_LT);
            let y = _mm512_mask_sub_epi32(x, mask, x, mod_vec);
            _mm512_storeu_si512(a.as_mut_ptr().add(i) as *mut __m512i, y);
            i += 16;
        }
        while i < a.len() {
            let x = a[i];
            a[i] = if x >= M::MOD { x - M::MOD } else { x };
            i += 1;
        }
    }

    unsafe fn add_vec_avx2<M>(
        a: __m256i,
        b: __m256i,
        mod_vec: __m256i,
        mod2_vec: __m256i,
        sign: __m256i,
    ) -> __m256i
    where
        M: Montgomery32NttModulus,
    {
        if M::MOD < LAZY_THRESHOLD {
            simd32::montgomery_add_256(a, b, mod2_vec, sign)
        } else {
            simd32::add_mod_256(a, b, mod_vec, sign)
        }
    }

    unsafe fn sub_vec_avx2<M>(
        a: __m256i,
        b: __m256i,
        mod_vec: __m256i,
        mod2_vec: __m256i,
        sign: __m256i,
    ) -> __m256i
    where
        M: Montgomery32NttModulus,
    {
        if M::MOD < LAZY_THRESHOLD {
            simd32::montgomery_sub_256(a, b, mod2_vec, sign)
        } else {
            simd32::sub_mod_256(a, b, mod_vec, sign)
        }
    }

    unsafe fn mul_vec_avx2<M>(
        a: __m256i,
        b: __m256i,
        r_vec: __m256i,
        mod_vec: __m256i,
        sign: __m256i,
    ) -> __m256i
    where
        M: Montgomery32NttModulus,
    {
        if M::MOD < LAZY_THRESHOLD {
            simd32::montgomery_mul_256(a, b, r_vec, mod_vec)
        } else {
            simd32::montgomery_mul_256_canon(a, b, r_vec, mod_vec, sign)
        }
    }

    unsafe fn add_vec_avx512<M>(
        a: __m512i,
        b: __m512i,
        mod_vec: __m512i,
        mod2_vec: __m512i,
    ) -> __m512i
    where
        M: Montgomery32NttModulus,
    {
        if M::MOD < LAZY_THRESHOLD {
            simd32::montgomery_add_512(a, b, mod2_vec)
        } else {
            simd32::add_mod_512(a, b, mod_vec)
        }
    }

    unsafe fn sub_vec_avx512<M>(
        a: __m512i,
        b: __m512i,
        mod_vec: __m512i,
        mod2_vec: __m512i,
    ) -> __m512i
    where
        M: Montgomery32NttModulus,
    {
        if M::MOD < LAZY_THRESHOLD {
            simd32::montgomery_sub_512(a, b, mod2_vec)
        } else {
            simd32::sub_mod_512(a, b, mod_vec)
        }
    }

    unsafe fn mul_vec_avx512<M>(a: __m512i, b: __m512i, r_vec: __m512i, mod_vec: __m512i) -> __m512i
    where
        M: Montgomery32NttModulus,
    {
        if M::MOD < LAZY_THRESHOLD {
            simd32::montgomery_mul_512(a, b, r_vec, mod_vec)
        } else {
            simd32::montgomery_mul_512_canon(a, b, r_vec, mod_vec)
        }
    }

    #[target_feature(enable = "avx2")]
    pub(super) unsafe fn ntt_avx2<M>(a: &mut [MInt<M>])
    where
        M: Montgomery32NttModulus,
    {
        let n = a.len();
        if n <= 1 {
            return;
        }
        let ptr = a.as_mut_ptr() as *mut u32;
        let a = std::slice::from_raw_parts_mut(ptr, n);
        let mod_vec = _mm256_set1_epi32(M::MOD as i32);
        let mod2_vec = _mm256_set1_epi32(M::MOD.wrapping_add(M::MOD) as i32);
        let r_vec = _mm256_set1_epi32(M::R.wrapping_neg() as i32);
        let sign = _mm256_set1_epi32(0x8000_0000u32 as i32);
        let imag = M::INFO.root[2];
        let imag_vec = _mm256_set1_epi32(imag as i32);

        let mut v = n / 2;
        while v > 1 {
            let half = v >> 1;
            let mut w1 = M::N1;
            for (s, block) in a.chunks_exact_mut(v << 1).enumerate() {
                let base = block.as_mut_ptr();
                let ll = base;
                let lr = base.add(half);
                let rl = base.add(v);
                let rr = base.add(v + half);

                let w2 = M::mod_mul(w1, w1);
                let w3 = M::mod_mul(w2, w1);
                let w1v = _mm256_set1_epi32(w1 as i32);
                let w2v = _mm256_set1_epi32(w2 as i32);
                let w3v = _mm256_set1_epi32(w3 as i32);

                let mut i = 0;
                while i + 8 <= half {
                    let x0 = _mm256_loadu_si256(ll.add(i) as *const __m256i);
                    let x1 = _mm256_loadu_si256(lr.add(i) as *const __m256i);
                    let x2 = _mm256_loadu_si256(rl.add(i) as *const __m256i);
                    let x3 = _mm256_loadu_si256(rr.add(i) as *const __m256i);

                    let a1 = mul_vec_avx2::<M>(x1, w1v, r_vec, mod_vec, sign);
                    let a2 = mul_vec_avx2::<M>(x2, w2v, r_vec, mod_vec, sign);
                    let a3 = mul_vec_avx2::<M>(x3, w3v, r_vec, mod_vec, sign);

                    let a0pa2 = add_vec_avx2::<M>(x0, a2, mod_vec, mod2_vec, sign);
                    let a0na2 = sub_vec_avx2::<M>(x0, a2, mod_vec, mod2_vec, sign);
                    let a1pa3 = add_vec_avx2::<M>(a1, a3, mod_vec, mod2_vec, sign);
                    let a1na3 = sub_vec_avx2::<M>(a1, a3, mod_vec, mod2_vec, sign);
                    let a1na3imag = mul_vec_avx2::<M>(a1na3, imag_vec, r_vec, mod_vec, sign);

                    let y0 = add_vec_avx2::<M>(a0pa2, a1pa3, mod_vec, mod2_vec, sign);
                    let y1 = sub_vec_avx2::<M>(a0pa2, a1pa3, mod_vec, mod2_vec, sign);
                    let y2 = add_vec_avx2::<M>(a0na2, a1na3imag, mod_vec, mod2_vec, sign);
                    let y3 = sub_vec_avx2::<M>(a0na2, a1na3imag, mod_vec, mod2_vec, sign);

                    _mm256_storeu_si256(ll.add(i) as *mut __m256i, y0);
                    _mm256_storeu_si256(lr.add(i) as *mut __m256i, y1);
                    _mm256_storeu_si256(rl.add(i) as *mut __m256i, y2);
                    _mm256_storeu_si256(rr.add(i) as *mut __m256i, y3);
                    i += 8;
                }
                while i < half {
                    let a0 = *ll.add(i);
                    let a1 = M::mod_mul(*lr.add(i), w1);
                    let a2 = M::mod_mul(*rl.add(i), w2);
                    let a3 = M::mod_mul(*rr.add(i), w3);
                    let a0pa2 = M::mod_add(a0, a2);
                    let a0na2 = M::mod_sub(a0, a2);
                    let a1pa3 = M::mod_add(a1, a3);
                    let a1na3 = M::mod_sub(a1, a3);
                    let a1na3imag = M::mod_mul(a1na3, imag);
                    *ll.add(i) = M::mod_add(a0pa2, a1pa3);
                    *lr.add(i) = M::mod_sub(a0pa2, a1pa3);
                    *rl.add(i) = M::mod_add(a0na2, a1na3imag);
                    *rr.add(i) = M::mod_sub(a0na2, a1na3imag);
                    i += 1;
                }
                w1 = M::mod_mul(w1, M::INFO.rate3[s.trailing_ones() as usize]);
            }
            v >>= 2;
        }
        if v == 1 {
            let mut w1 = M::N1;
            for (s, block) in a.chunks_exact_mut(2).enumerate() {
                let a0 = *block.get_unchecked(0);
                let a1 = M::mod_mul(*block.get_unchecked(1), w1);
                *block.get_unchecked_mut(0) = M::mod_add(a0, a1);
                *block.get_unchecked_mut(1) = M::mod_sub(a0, a1);
                w1 = M::mod_mul(w1, M::INFO.rate2[s.trailing_ones() as usize]);
            }
        }
        normalize_avx2::<M>(a);
    }

    #[target_feature(enable = "avx2")]
    pub(super) unsafe fn intt_avx2<M>(a: &mut [MInt<M>])
    where
        M: Montgomery32NttModulus,
    {
        let n = a.len();
        if n <= 1 {
            return;
        }
        let ptr = a.as_mut_ptr() as *mut u32;
        let a = std::slice::from_raw_parts_mut(ptr, n);
        let mod_vec = _mm256_set1_epi32(M::MOD as i32);
        let mod2_vec = _mm256_set1_epi32(M::MOD.wrapping_add(M::MOD) as i32);
        let r_vec = _mm256_set1_epi32(M::R.wrapping_neg() as i32);
        let sign = _mm256_set1_epi32(0x8000_0000u32 as i32);
        let iimag = M::INFO.inv_root[2];
        let iimag_vec = _mm256_set1_epi32(iimag as i32);

        let mut v = 1;
        if n.trailing_zeros() & 1 == 1 {
            let mut w1 = M::N1;
            for (s, block) in a.chunks_exact_mut(2).enumerate() {
                let a0 = *block.get_unchecked(0);
                let a1 = *block.get_unchecked(1);
                *block.get_unchecked_mut(0) = M::mod_add(a0, a1);
                *block.get_unchecked_mut(1) = M::mod_mul(M::mod_sub(a0, a1), w1);
                w1 = M::mod_mul(w1, M::INFO.inv_rate2[s.trailing_ones() as usize]);
            }
            v <<= 1;
        }
        while v < n {
            let mut w1 = M::N1;
            for (s, block) in a.chunks_exact_mut(v << 2).enumerate() {
                let base = block.as_mut_ptr();
                let ll = base;
                let lr = base.add(v);
                let rl = base.add(v << 1);
                let rr = base.add(v * 3);

                let w2 = M::mod_mul(w1, w1);
                let w3 = M::mod_mul(w2, w1);
                let w1v = _mm256_set1_epi32(w1 as i32);
                let w2v = _mm256_set1_epi32(w2 as i32);
                let w3v = _mm256_set1_epi32(w3 as i32);

                let mut i = 0;
                while i + 8 <= v {
                    let x0 = _mm256_loadu_si256(ll.add(i) as *const __m256i);
                    let x1 = _mm256_loadu_si256(lr.add(i) as *const __m256i);
                    let x2 = _mm256_loadu_si256(rl.add(i) as *const __m256i);
                    let x3 = _mm256_loadu_si256(rr.add(i) as *const __m256i);

                    let a0pa1 = add_vec_avx2::<M>(x0, x1, mod_vec, mod2_vec, sign);
                    let a0na1 = sub_vec_avx2::<M>(x0, x1, mod_vec, mod2_vec, sign);
                    let a2pa3 = add_vec_avx2::<M>(x2, x3, mod_vec, mod2_vec, sign);
                    let a2na3 = sub_vec_avx2::<M>(x2, x3, mod_vec, mod2_vec, sign);
                    let a2na3iimag = mul_vec_avx2::<M>(a2na3, iimag_vec, r_vec, mod_vec, sign);

                    let y0 = add_vec_avx2::<M>(a0pa1, a2pa3, mod_vec, mod2_vec, sign);
                    let y1 = add_vec_avx2::<M>(a0na1, a2na3iimag, mod_vec, mod2_vec, sign);
                    let y2 = sub_vec_avx2::<M>(a0pa1, a2pa3, mod_vec, mod2_vec, sign);
                    let y3 = sub_vec_avx2::<M>(a0na1, a2na3iimag, mod_vec, mod2_vec, sign);

                    let y1 = mul_vec_avx2::<M>(y1, w1v, r_vec, mod_vec, sign);
                    let y2 = mul_vec_avx2::<M>(y2, w2v, r_vec, mod_vec, sign);
                    let y3 = mul_vec_avx2::<M>(y3, w3v, r_vec, mod_vec, sign);

                    _mm256_storeu_si256(ll.add(i) as *mut __m256i, y0);
                    _mm256_storeu_si256(lr.add(i) as *mut __m256i, y1);
                    _mm256_storeu_si256(rl.add(i) as *mut __m256i, y2);
                    _mm256_storeu_si256(rr.add(i) as *mut __m256i, y3);
                    i += 8;
                }
                while i < v {
                    let a0 = *ll.add(i);
                    let a1 = *lr.add(i);
                    let a2 = *rl.add(i);
                    let a3 = *rr.add(i);
                    let a0pa1 = M::mod_add(a0, a1);
                    let a0na1 = M::mod_sub(a0, a1);
                    let a2pa3 = M::mod_add(a2, a3);
                    let a2na3iimag = M::mod_mul(M::mod_sub(a2, a3), iimag);
                    *ll.add(i) = M::mod_add(a0pa1, a2pa3);
                    *lr.add(i) = M::mod_mul(M::mod_add(a0na1, a2na3iimag), w1);
                    *rl.add(i) = M::mod_mul(M::mod_sub(a0pa1, a2pa3), w2);
                    *rr.add(i) = M::mod_mul(M::mod_sub(a0na1, a2na3iimag), w3);
                    i += 1;
                }
                w1 = M::mod_mul(w1, M::INFO.inv_rate3[s.trailing_ones() as usize]);
            }
            v <<= 2;
        }
        normalize_avx2::<M>(a);
    }

    #[target_feature(enable = "avx512f,avx512dq,avx512cd,avx512bw,avx512vl")]
    pub(super) unsafe fn ntt_avx512<M>(a: &mut [MInt<M>])
    where
        M: Montgomery32NttModulus,
    {
        let n = a.len();
        if n <= 1 {
            return;
        }
        let ptr = a.as_mut_ptr() as *mut u32;
        let a = std::slice::from_raw_parts_mut(ptr, n);
        let mod_vec = _mm512_set1_epi32(M::MOD as i32);
        let mod2_vec = _mm512_set1_epi32(M::MOD.wrapping_add(M::MOD) as i32);
        let r_vec = _mm512_set1_epi32(M::R.wrapping_neg() as i32);
        let imag = M::INFO.root[2];
        let imag_vec = _mm512_set1_epi32(imag as i32);

        let mut v = n / 2;
        while v > 1 {
            let half = v >> 1;
            let mut w1 = M::N1;
            for (s, block) in a.chunks_exact_mut(v << 1).enumerate() {
                let base = block.as_mut_ptr();
                let ll = base;
                let lr = base.add(half);
                let rl = base.add(v);
                let rr = base.add(v + half);
                let w2 = M::mod_mul(w1, w1);
                let w3 = M::mod_mul(w2, w1);
                let w1v = _mm512_set1_epi32(w1 as i32);
                let w2v = _mm512_set1_epi32(w2 as i32);
                let w3v = _mm512_set1_epi32(w3 as i32);

                let mut i = 0;
                while i + 16 <= half {
                    let x0 = _mm512_loadu_si512(ll.add(i) as *const __m512i);
                    let x1 = _mm512_loadu_si512(lr.add(i) as *const __m512i);
                    let x2 = _mm512_loadu_si512(rl.add(i) as *const __m512i);
                    let x3 = _mm512_loadu_si512(rr.add(i) as *const __m512i);

                    let a1 = mul_vec_avx512::<M>(x1, w1v, r_vec, mod_vec);
                    let a2 = mul_vec_avx512::<M>(x2, w2v, r_vec, mod_vec);
                    let a3 = mul_vec_avx512::<M>(x3, w3v, r_vec, mod_vec);

                    let a0pa2 = add_vec_avx512::<M>(x0, a2, mod_vec, mod2_vec);
                    let a0na2 = sub_vec_avx512::<M>(x0, a2, mod_vec, mod2_vec);
                    let a1pa3 = add_vec_avx512::<M>(a1, a3, mod_vec, mod2_vec);
                    let a1na3 = sub_vec_avx512::<M>(a1, a3, mod_vec, mod2_vec);
                    let a1na3imag = mul_vec_avx512::<M>(a1na3, imag_vec, r_vec, mod_vec);

                    let y0 = add_vec_avx512::<M>(a0pa2, a1pa3, mod_vec, mod2_vec);
                    let y1 = sub_vec_avx512::<M>(a0pa2, a1pa3, mod_vec, mod2_vec);
                    let y2 = add_vec_avx512::<M>(a0na2, a1na3imag, mod_vec, mod2_vec);
                    let y3 = sub_vec_avx512::<M>(a0na2, a1na3imag, mod_vec, mod2_vec);

                    _mm512_storeu_si512(ll.add(i) as *mut __m512i, y0);
                    _mm512_storeu_si512(lr.add(i) as *mut __m512i, y1);
                    _mm512_storeu_si512(rl.add(i) as *mut __m512i, y2);
                    _mm512_storeu_si512(rr.add(i) as *mut __m512i, y3);
                    i += 16;
                }
                while i < half {
                    let a0 = *ll.add(i);
                    let a1 = M::mod_mul(*lr.add(i), w1);
                    let a2 = M::mod_mul(*rl.add(i), w2);
                    let a3 = M::mod_mul(*rr.add(i), w3);
                    let a0pa2 = M::mod_add(a0, a2);
                    let a0na2 = M::mod_sub(a0, a2);
                    let a1pa3 = M::mod_add(a1, a3);
                    let a1na3 = M::mod_sub(a1, a3);
                    let a1na3imag = M::mod_mul(a1na3, imag);
                    *ll.add(i) = M::mod_add(a0pa2, a1pa3);
                    *lr.add(i) = M::mod_sub(a0pa2, a1pa3);
                    *rl.add(i) = M::mod_add(a0na2, a1na3imag);
                    *rr.add(i) = M::mod_sub(a0na2, a1na3imag);
                    i += 1;
                }
                w1 = M::mod_mul(w1, M::INFO.rate3[s.trailing_ones() as usize]);
            }
            v >>= 2;
        }
        if v == 1 {
            let mut w1 = M::N1;
            for (s, block) in a.chunks_exact_mut(2).enumerate() {
                let a0 = *block.get_unchecked(0);
                let a1 = M::mod_mul(*block.get_unchecked(1), w1);
                *block.get_unchecked_mut(0) = M::mod_add(a0, a1);
                *block.get_unchecked_mut(1) = M::mod_sub(a0, a1);
                w1 = M::mod_mul(w1, M::INFO.rate2[s.trailing_ones() as usize]);
            }
        }
        normalize_avx512::<M>(a);
    }

    #[target_feature(enable = "avx512f,avx512dq,avx512cd,avx512bw,avx512vl")]
    pub(super) unsafe fn intt_avx512<M>(a: &mut [MInt<M>])
    where
        M: Montgomery32NttModulus,
    {
        let n = a.len();
        if n <= 1 {
            return;
        }
        let ptr = a.as_mut_ptr() as *mut u32;
        let a = std::slice::from_raw_parts_mut(ptr, n);
        let mod_vec = _mm512_set1_epi32(M::MOD as i32);
        let mod2_vec = _mm512_set1_epi32(M::MOD.wrapping_add(M::MOD) as i32);
        let r_vec = _mm512_set1_epi32(M::R.wrapping_neg() as i32);
        let iimag = M::INFO.inv_root[2];
        let iimag_vec = _mm512_set1_epi32(iimag as i32);

        let mut v = 1;
        if n.trailing_zeros() & 1 == 1 {
            let mut w1 = M::N1;
            for (s, block) in a.chunks_exact_mut(2).enumerate() {
                let a0 = *block.get_unchecked(0);
                let a1 = *block.get_unchecked(1);
                *block.get_unchecked_mut(0) = M::mod_add(a0, a1);
                *block.get_unchecked_mut(1) = M::mod_mul(M::mod_sub(a0, a1), w1);
                w1 = M::mod_mul(w1, M::INFO.inv_rate2[s.trailing_ones() as usize]);
            }
            v <<= 1;
        }
        while v < n {
            let mut w1 = M::N1;
            for (s, block) in a.chunks_exact_mut(v << 2).enumerate() {
                let base = block.as_mut_ptr();
                let ll = base;
                let lr = base.add(v);
                let rl = base.add(v << 1);
                let rr = base.add(v * 3);
                let w2 = M::mod_mul(w1, w1);
                let w3 = M::mod_mul(w2, w1);
                let w1v = _mm512_set1_epi32(w1 as i32);
                let w2v = _mm512_set1_epi32(w2 as i32);
                let w3v = _mm512_set1_epi32(w3 as i32);

                let mut i = 0;
                while i + 16 <= v {
                    let x0 = _mm512_loadu_si512(ll.add(i) as *const __m512i);
                    let x1 = _mm512_loadu_si512(lr.add(i) as *const __m512i);
                    let x2 = _mm512_loadu_si512(rl.add(i) as *const __m512i);
                    let x3 = _mm512_loadu_si512(rr.add(i) as *const __m512i);

                    let a0pa1 = add_vec_avx512::<M>(x0, x1, mod_vec, mod2_vec);
                    let a0na1 = sub_vec_avx512::<M>(x0, x1, mod_vec, mod2_vec);
                    let a2pa3 = add_vec_avx512::<M>(x2, x3, mod_vec, mod2_vec);
                    let a2na3 = sub_vec_avx512::<M>(x2, x3, mod_vec, mod2_vec);
                    let a2na3iimag = mul_vec_avx512::<M>(a2na3, iimag_vec, r_vec, mod_vec);

                    let y0 = add_vec_avx512::<M>(a0pa1, a2pa3, mod_vec, mod2_vec);
                    let y1 = add_vec_avx512::<M>(a0na1, a2na3iimag, mod_vec, mod2_vec);
                    let y2 = sub_vec_avx512::<M>(a0pa1, a2pa3, mod_vec, mod2_vec);
                    let y3 = sub_vec_avx512::<M>(a0na1, a2na3iimag, mod_vec, mod2_vec);

                    let y1 = mul_vec_avx512::<M>(y1, w1v, r_vec, mod_vec);
                    let y2 = mul_vec_avx512::<M>(y2, w2v, r_vec, mod_vec);
                    let y3 = mul_vec_avx512::<M>(y3, w3v, r_vec, mod_vec);

                    _mm512_storeu_si512(ll.add(i) as *mut __m512i, y0);
                    _mm512_storeu_si512(lr.add(i) as *mut __m512i, y1);
                    _mm512_storeu_si512(rl.add(i) as *mut __m512i, y2);
                    _mm512_storeu_si512(rr.add(i) as *mut __m512i, y3);
                    i += 16;
                }
                while i < v {
                    let a0 = *ll.add(i);
                    let a1 = *lr.add(i);
                    let a2 = *rl.add(i);
                    let a3 = *rr.add(i);
                    let a0pa1 = M::mod_add(a0, a1);
                    let a0na1 = M::mod_sub(a0, a1);
                    let a2pa3 = M::mod_add(a2, a3);
                    let a2na3iimag = M::mod_mul(M::mod_sub(a2, a3), iimag);
                    *ll.add(i) = M::mod_add(a0pa1, a2pa3);
                    *lr.add(i) = M::mod_mul(M::mod_add(a0na1, a2na3iimag), w1);
                    *rl.add(i) = M::mod_mul(M::mod_sub(a0pa1, a2pa3), w2);
                    *rr.add(i) = M::mod_mul(M::mod_sub(a0na1, a2na3iimag), w3);
                    i += 1;
                }
                w1 = M::mod_mul(w1, M::INFO.inv_rate3[s.trailing_ones() as usize]);
            }
            v <<= 2;
        }
        normalize_avx512::<M>(a);
    }
}

fn convolve_naive<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Copy + Zero + AddAssign<T> + Mul<Output = T>,
{
    if a.is_empty() && b.is_empty() {
        return Vec::new();
    }
    let len = a.len() + b.len() - 1;
    let mut c = vec![T::zero(); len];
    if a.len() < b.len() {
        for (i, &b) in b.iter().enumerate() {
            for (a, c) in a.iter().zip(&mut c[i..]) {
                *c += *a * b;
            }
        }
    } else {
        for (i, &a) in a.iter().enumerate() {
            for (b, c) in b.iter().zip(&mut c[i..]) {
                *c += *b * a;
            }
        }
    }
    c
}

fn convolve_karatsuba<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Copy + Zero + AddAssign<T> + SubAssign<T> + Mul<Output = T>,
{
    if a.len().min(b.len()) <= 30 {
        return convolve_naive(a, b);
    }
    let m = a.len().max(b.len()).div_ceil(2);
    let (a0, a1) = if a.len() <= m {
        (a, &[][..])
    } else {
        a.split_at(m)
    };
    let (b0, b1) = if b.len() <= m {
        (b, &[][..])
    } else {
        b.split_at(m)
    };
    let f00 = convolve_karatsuba(a0, b0);
    let f11 = convolve_karatsuba(a1, b1);
    let mut a0a1 = a0.to_vec();
    for (a0a1, &a1) in a0a1.iter_mut().zip(a1) {
        *a0a1 += a1;
    }
    let mut b0b1 = b0.to_vec();
    for (b0b1, &b1) in b0b1.iter_mut().zip(b1) {
        *b0b1 += b1;
    }
    let mut f01 = convolve_karatsuba(&a0a1, &b0b1);
    for (f01, &f00) in f01.iter_mut().zip(&f00) {
        *f01 -= f00;
    }
    for (f01, &f11) in f01.iter_mut().zip(&f11) {
        *f01 -= f11;
    }
    let mut c = vec![T::zero(); a.len() + b.len() - 1];
    for (c, &f00) in c.iter_mut().zip(&f00) {
        *c += f00;
    }
    for (c, &f01) in c[m..].iter_mut().zip(&f01) {
        *c += f01;
    }
    for (c, &f11) in c[m << 1..].iter_mut().zip(&f11) {
        *c += f11;
    }
    c
}

impl<M> ConvolveSteps for Convolve<M>
where
    M: Montgomery32NttModulus,
{
    type T = Vec<MInt<M>>;
    type F = Vec<MInt<M>>;
    fn length(t: &Self::T) -> usize {
        t.len()
    }
    fn transform(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(mut f: Self::F, len: usize) -> Self::T {
        intt(&mut f);
        f.truncate(len);
        let inv = MInt::from(len.max(1).next_power_of_two() as u32).inv();
        for f in f.iter_mut() {
            *f *= inv;
        }
        f
    }
    fn multiply(f: &mut Self::F, g: &Self::F) {
        assert_eq!(f.len(), g.len());
        for (f, g) in f.iter_mut().zip(g.iter()) {
            *f *= *g;
        }
    }
    fn convolve(mut a: Self::T, mut b: Self::T) -> Self::T {
        if Self::length(&a).max(Self::length(&b)) <= 100 {
            return convolve_karatsuba(&a, &b);
        }
        if Self::length(&a).min(Self::length(&b)) <= 60 {
            return convolve_naive(&a, &b);
        }
        let len = (Self::length(&a) + Self::length(&b)).saturating_sub(1);
        let size = len.max(1).next_power_of_two();
        if len <= size / 2 + 2 {
            let xa = a.pop().unwrap();
            let xb = b.pop().unwrap();
            let mut c = vec![MInt::<M>::zero(); len];
            *c.last_mut().unwrap() = xa * xb;
            for (a, c) in a.iter().zip(&mut c[b.len()..]) {
                *c += *a * xb;
            }
            for (b, c) in b.iter().zip(&mut c[a.len()..]) {
                *c += *b * xa;
            }
            let d = Self::convolve(a, b);
            for (d, c) in d.into_iter().zip(&mut c) {
                *c += d;
            }
            return c;
        }
        let same = a == b;
        let mut a = Self::transform(a, len);
        if same {
            for a in a.iter_mut() {
                *a *= *a;
            }
        } else {
            let b = Self::transform(b, len);
            Self::multiply(&mut a, &b);
        }
        Self::inverse_transform(a, len)
    }
}

type MVec<M> = Vec<MInt<M>>;
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 mut f = (
            MVec::<N1>::with_capacity(npot),
            MVec::<N2>::with_capacity(npot),
            MVec::<N3>::with_capacity(npot),
        );
        for t in t {
            f.0.push(<M as MIntConvert<u32>>::into(t.inner()).into());
            f.1.push(<M as MIntConvert<u32>>::into(t.inner()).into());
            f.2.push(<M as MIntConvert<u32>>::into(t.inner()).into());
        }
        f.0.resize_with(npot, Zero::zero);
        f.1.resize_with(npot, Zero::zero);
        f.2.resize_with(npot, Zero::zero);
        ntt(&mut f.0);
        ntt(&mut f.1);
        ntt(&mut f.2);
        f
    }
    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        let t1 = MInt::<N2>::new(N1::get_mod()).inv();
        let m1 = MInt::<M>::from(N1::get_mod());
        let m1_3 = MInt::<N3>::new(N1::get_mod());
        let t2 = (m1_3 * MInt::<N3>::new(N2::get_mod())).inv();
        let m2 = m1 * MInt::<M>::from(N2::get_mod());
        Convolve::<N1>::inverse_transform(f.0, len)
            .into_iter()
            .zip(Convolve::<N2>::inverse_transform(f.1, len))
            .zip(Convolve::<N3>::inverse_transform(f.2, len))
            .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();
                MInt::<M>::from(d1) + MInt::<M>::from(d2) * m1 + MInt::<M>::from(d3) * m2
            })
            .collect()
    }
    fn multiply(f: &mut Self::F, g: &Self::F) {
        assert_eq!(f.0.len(), g.0.len());
        assert_eq!(f.1.len(), g.1.len());
        assert_eq!(f.2.len(), g.2.len());
        for (f, g) in f.0.iter_mut().zip(g.0.iter()) {
            *f *= *g;
        }
        for (f, g) in f.1.iter_mut().zip(g.1.iter()) {
            *f *= *g;
        }
        for (f, g) in f.2.iter_mut().zip(g.2.iter()) {
            *f *= *g;
        }
    }
    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        if Self::length(&a).max(Self::length(&b)) <= 300 {
            return convolve_karatsuba(&a, &b);
        }
        if Self::length(&a).min(Self::length(&b)) <= 60 {
            return convolve_naive(&a, &b);
        }
        let len = (Self::length(&a) + Self::length(&b)).saturating_sub(1);
        let mut a = Self::transform(a, len);
        let b = Self::transform(b, len);
        Self::multiply(&mut a, &b);
        Self::inverse_transform(a, len)
    }
}

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>, 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 mut f = (
            MVec::<N1>::with_capacity(npot),
            MVec::<N2>::with_capacity(npot),
            MVec::<N3>::with_capacity(npot),
        );
        for t in t {
            f.0.push(t.into());
            f.1.push(t.into());
            f.2.push(t.into());
        }
        f.0.resize_with(npot, Zero::zero);
        f.1.resize_with(npot, Zero::zero);
        f.2.resize_with(npot, Zero::zero);
        ntt(&mut f.0);
        ntt(&mut f.1);
        ntt(&mut f.2);
        f
    }

    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        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;
        Convolve::<N1>::inverse_transform(f.0, len)
            .into_iter()
            .zip(Convolve::<N2>::inverse_transform(f.1, len))
            .zip(Convolve::<N3>::inverse_transform(f.2, len))
            .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();
                d1 as u64 + d2 as u64 * m1 + d3 as u64 * m2
            })
            .collect()
    }

    fn multiply(f: &mut Self::F, g: &Self::F) {
        assert_eq!(f.0.len(), g.0.len());
        assert_eq!(f.1.len(), g.1.len());
        assert_eq!(f.2.len(), g.2.len());
        for (f, g) in f.0.iter_mut().zip(g.0.iter()) {
            *f *= *g;
        }
        for (f, g) in f.1.iter_mut().zip(g.1.iter()) {
            *f *= *g;
        }
        for (f, g) in f.2.iter_mut().zip(g.2.iter()) {
            *f *= *g;
        }
    }

    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        if Self::length(&a).max(Self::length(&b)) <= 300 {
            return convolve_karatsuba(&a, &b);
        }
        if Self::length(&a).min(Self::length(&b)) <= 60 {
            return convolve_naive(&a, &b);
        }
        let len = (Self::length(&a) + Self::length(&b)).saturating_sub(1);
        let mut a = Self::transform(a, len);
        let b = Self::transform(b, len);
        Self::multiply(&mut a, &b);
        Self::inverse_transform(a, len)
    }
}

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

    /// F(a) → F(a + [0] * a.len())
    fn ntt_doubling(f: Self::F) -> Self::F;

    /// F(a(x)), F(b(x)) → even(F(a(x) * b(-x)))
    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F;

    /// F(a(x)), F(b(x)) → odd(F(a(x) * b(-x)))
    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F;
}

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 ntt_doubling(mut f: Self::F) -> Self::F {
        let n = f.len();
        let k = n.trailing_zeros() as usize;
        let mut a = Self::inverse_transform(f.clone(), n);
        let mut rot = MInt::<M>::one();
        let zeta = MInt::<M>::new_unchecked(M::INFO.root[k + 1]);
        for a in a.iter_mut() {
            *a *= rot;
            rot *= zeta;
        }
        f.extend(Self::transform(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);
        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
    }
}

impl<M, N1, N2, N3> NttReuse for Convolve<(M, (N1, N2, N3))>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    fn ntt_doubling(f: Self::F) -> Self::F {
        (
            Convolve::<N1>::ntt_doubling(f.0),
            Convolve::<N2>::ntt_doubling(f.1),
            Convolve::<N3>::ntt_doubling(f.2),
        )
    }

    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
        }

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/algorithm/chromatic_number.rs (line 40)

    pub fn k_colorable(&self, k: usize) -> bool {
        !self
            .ind
            .iter()
            .map(|d| d.pow(k))
            .enumerate()
            .map(|(s, d)| if s.count_ones() % 2 == 0 { d } else { -d })
            .sum::<MInt<M>>()
            .is_zero()
    }

pub fn inv(self) -> Self

Examples found in repository

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

    fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
        intt(&mut f);
        f.truncate(len);
        let inv = MInt::from(len.max(1).next_power_of_two() as u32).inv();
        for f in f.iter_mut() {
            *f *= inv;
        }
        f
    }
    fn multiply(f: &mut Self::F, g: &Self::F) {
        assert_eq!(f.len(), g.len());
        for (f, g) in f.iter_mut().zip(g.iter()) {
            *f *= *g;
        }
    }
    fn convolve(mut a: Self::T, mut b: Self::T) -> Self::T {
        if Self::length(&a).max(Self::length(&b)) <= 100 {
            return convolve_karatsuba(&a, &b);
        }
        if Self::length(&a).min(Self::length(&b)) <= 60 {
            return convolve_naive(&a, &b);
        }
        let len = (Self::length(&a) + Self::length(&b)).saturating_sub(1);
        let size = len.max(1).next_power_of_two();
        if len <= size / 2 + 2 {
            let xa = a.pop().unwrap();
            let xb = b.pop().unwrap();
            let mut c = vec![MInt::<M>::zero(); len];
            *c.last_mut().unwrap() = xa * xb;
            for (a, c) in a.iter().zip(&mut c[b.len()..]) {
                *c += *a * xb;
            }
            for (b, c) in b.iter().zip(&mut c[a.len()..]) {
                *c += *b * xa;
            }
            let d = Self::convolve(a, b);
            for (d, c) in d.into_iter().zip(&mut c) {
                *c += d;
            }
            return c;
        }
        let same = a == b;
        let mut a = Self::transform(a, len);
        if same {
            for a in a.iter_mut() {
                *a *= *a;
            }
        } else {
            let b = Self::transform(b, len);
            Self::multiply(&mut a, &b);
        }
        Self::inverse_transform(a, len)
    }
}

type MVec<M> = Vec<MInt<M>>;
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 mut f = (
            MVec::<N1>::with_capacity(npot),
            MVec::<N2>::with_capacity(npot),
            MVec::<N3>::with_capacity(npot),
        );
        for t in t {
            f.0.push(<M as MIntConvert<u32>>::into(t.inner()).into());
            f.1.push(<M as MIntConvert<u32>>::into(t.inner()).into());
            f.2.push(<M as MIntConvert<u32>>::into(t.inner()).into());
        }
        f.0.resize_with(npot, Zero::zero);
        f.1.resize_with(npot, Zero::zero);
        f.2.resize_with(npot, Zero::zero);
        ntt(&mut f.0);
        ntt(&mut f.1);
        ntt(&mut f.2);
        f
    }
    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        let t1 = MInt::<N2>::new(N1::get_mod()).inv();
        let m1 = MInt::<M>::from(N1::get_mod());
        let m1_3 = MInt::<N3>::new(N1::get_mod());
        let t2 = (m1_3 * MInt::<N3>::new(N2::get_mod())).inv();
        let m2 = m1 * MInt::<M>::from(N2::get_mod());
        Convolve::<N1>::inverse_transform(f.0, len)
            .into_iter()
            .zip(Convolve::<N2>::inverse_transform(f.1, len))
            .zip(Convolve::<N3>::inverse_transform(f.2, len))
            .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();
                MInt::<M>::from(d1) + MInt::<M>::from(d2) * m1 + MInt::<M>::from(d3) * m2
            })
            .collect()
    }
    fn multiply(f: &mut Self::F, g: &Self::F) {
        assert_eq!(f.0.len(), g.0.len());
        assert_eq!(f.1.len(), g.1.len());
        assert_eq!(f.2.len(), g.2.len());
        for (f, g) in f.0.iter_mut().zip(g.0.iter()) {
            *f *= *g;
        }
        for (f, g) in f.1.iter_mut().zip(g.1.iter()) {
            *f *= *g;
        }
        for (f, g) in f.2.iter_mut().zip(g.2.iter()) {
            *f *= *g;
        }
    }
    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        if Self::length(&a).max(Self::length(&b)) <= 300 {
            return convolve_karatsuba(&a, &b);
        }
        if Self::length(&a).min(Self::length(&b)) <= 60 {
            return convolve_naive(&a, &b);
        }
        let len = (Self::length(&a) + Self::length(&b)).saturating_sub(1);
        let mut a = Self::transform(a, len);
        let b = Self::transform(b, len);
        Self::multiply(&mut a, &b);
        Self::inverse_transform(a, len)
    }
}

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>, 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 mut f = (
            MVec::<N1>::with_capacity(npot),
            MVec::<N2>::with_capacity(npot),
            MVec::<N3>::with_capacity(npot),
        );
        for t in t {
            f.0.push(t.into());
            f.1.push(t.into());
            f.2.push(t.into());
        }
        f.0.resize_with(npot, Zero::zero);
        f.1.resize_with(npot, Zero::zero);
        f.2.resize_with(npot, Zero::zero);
        ntt(&mut f.0);
        ntt(&mut f.1);
        ntt(&mut f.2);
        f
    }

    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        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;
        Convolve::<N1>::inverse_transform(f.0, len)
            .into_iter()
            .zip(Convolve::<N2>::inverse_transform(f.1, len))
            .zip(Convolve::<N3>::inverse_transform(f.2, len))
            .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();
                d1 as u64 + d2 as u64 * m1 + d3 as u64 * m2
            })
            .collect()
    }

    fn multiply(f: &mut Self::F, g: &Self::F) {
        assert_eq!(f.0.len(), g.0.len());
        assert_eq!(f.1.len(), g.1.len());
        assert_eq!(f.2.len(), g.2.len());
        for (f, g) in f.0.iter_mut().zip(g.0.iter()) {
            *f *= *g;
        }
        for (f, g) in f.1.iter_mut().zip(g.1.iter()) {
            *f *= *g;
        }
        for (f, g) in f.2.iter_mut().zip(g.2.iter()) {
            *f *= *g;
        }
    }

    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        if Self::length(&a).max(Self::length(&b)) <= 300 {
            return convolve_karatsuba(&a, &b);
        }
        if Self::length(&a).min(Self::length(&b)) <= 60 {
            return convolve_naive(&a, &b);
        }
        let len = (Self::length(&a) + Self::length(&b)).saturating_sub(1);
        let mut a = Self::transform(a, len);
        let b = Self::transform(b, len);
        Self::multiply(&mut a, &b);
        Self::inverse_transform(a, len)
    }
}

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

    /// F(a) → F(a + [0] * a.len())
    fn ntt_doubling(f: Self::F) -> Self::F;

    /// F(a(x)), F(b(x)) → even(F(a(x) * b(-x)))
    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F;

    /// F(a(x)), F(b(x)) → odd(F(a(x) * b(-x)))
    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F;
}

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 ntt_doubling(mut f: Self::F) -> Self::F {
        let n = f.len();
        let k = n.trailing_zeros() as usize;
        let mut a = Self::inverse_transform(f.clone(), n);
        let mut rot = MInt::<M>::one();
        let zeta = MInt::<M>::new_unchecked(M::INFO.root[k + 1]);
        for a in a.iter_mut() {
            *a *= rot;
            rot *= zeta;
        }
        f.extend(Self::transform(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);
        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
    }
}

impl<M, N1, N2, N3> NttReuse for Convolve<(M, (N1, N2, N3))>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    fn ntt_doubling(f: Self::F) -> Self::F {
        (
            Convolve::<N1>::ntt_doubling(f.0),
            Convolve::<N2>::ntt_doubling(f.1),
            Convolve::<N3>::ntt_doubling(f.2),
        )
    }

    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
        }

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_matrix.rs (line 290)

    fn black_box_linear_equation(&self, mut b: Vec<MInt<M>>) -> Option<Vec<MInt<M>>>
    where
        M: MIntConvert<u64>,
    {
        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 19)

pub fn sum_of_totient_function(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, 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)
        });
    writeln!(writer, "{}", qa[n]).ok();
}

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/mint_matrix.rs (line 55)

    fn determinant_linear_non_singular(mut self, mut other: Self) -> Option<Vec<MInt<M>>>
    where
        M: MIntBase,
    {
        let n = self.data.len();
        let mut f = MInt::one();
        for d in 0..n {
            let i = other.data.iter().position(|other| !other[d].is_zero())?;
            if i != d {
                self.data.swap(i, d);
                other.data.swap(i, d);
                f = -f;
            }
            f *= other[d][d];
            let r = other[d][d].inv();
            for j in 0..n {
                self[d][j] *= r;
                other[d][j] *= r;
            }
            assert!(other[d][d].is_one());
            for i in d + 1..n {
                let a = other[i][d];
                for k in 0..n {
                    self[i][k] = self[i][k] - a * self[d][k];
                    other[i][k] = other[i][k] - a * other[d][k];
                }
            }
            for j in d + 1..n {
                let a = other[d][j];
                for k in 0..n {
                    self[k][j] = self[k][j] - a * self[k][d];
                    other[k][j] = other[k][j] - a * other[k][d];
                }
            }
        }
        for s in self.data.iter_mut() {
            for s in s.iter_mut() {
                *s = -*s;
            }
        }
        let mut p = self.characteristic_polynomial();
        for p in p.iter_mut() {
            *p *= f;
        }
        Some(p)
    }

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())
    }
}
impl<M> FromStr for MInt<M>
where
    M: MIntConvert + MIntBase<Inner: FromStr>,
{
    type Err = <M::Inner as FromStr>::Err;
    #[inline]
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        s.parse::<M::Inner>().map(Self::new)
    }
}
impl<M> IterScan for MInt<M>
where
    M: MIntConvert + MIntBase<Inner: FromStr>,
{
    type Output = Self;
    #[inline]
    fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
        iter.next()?.parse::<MInt<M>>().ok()
    }
}
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 978)

    fn transform(t: Self::T, len: usize) -> Self::F {
        let npot = len.max(1).next_power_of_two();
        let mut f = (
            MVec::<N1>::with_capacity(npot),
            MVec::<N2>::with_capacity(npot),
            MVec::<N3>::with_capacity(npot),
        );
        for t in t {
            f.0.push(<M as MIntConvert<u32>>::into(t.inner()).into());
            f.1.push(<M as MIntConvert<u32>>::into(t.inner()).into());
            f.2.push(<M as MIntConvert<u32>>::into(t.inner()).into());
        }
        f.0.resize_with(npot, Zero::zero);
        f.1.resize_with(npot, Zero::zero);
        f.2.resize_with(npot, Zero::zero);
        ntt(&mut f.0);
        ntt(&mut f.1);
        ntt(&mut f.2);
        f
    }
    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        let t1 = MInt::<N2>::new(N1::get_mod()).inv();
        let m1 = MInt::<M>::from(N1::get_mod());
        let m1_3 = MInt::<N3>::new(N1::get_mod());
        let t2 = (m1_3 * MInt::<N3>::new(N2::get_mod())).inv();
        let m2 = m1 * MInt::<M>::from(N2::get_mod());
        Convolve::<N1>::inverse_transform(f.0, len)
            .into_iter()
            .zip(Convolve::<N2>::inverse_transform(f.1, len))
            .zip(Convolve::<N3>::inverse_transform(f.2, len))
            .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();
                MInt::<M>::from(d1) + MInt::<M>::from(d2) * m1 + MInt::<M>::from(d3) * m2
            })
            .collect()
    }
    fn multiply(f: &mut Self::F, g: &Self::F) {
        assert_eq!(f.0.len(), g.0.len());
        assert_eq!(f.1.len(), g.1.len());
        assert_eq!(f.2.len(), g.2.len());
        for (f, g) in f.0.iter_mut().zip(g.0.iter()) {
            *f *= *g;
        }
        for (f, g) in f.1.iter_mut().zip(g.1.iter()) {
            *f *= *g;
        }
        for (f, g) in f.2.iter_mut().zip(g.2.iter()) {
            *f *= *g;
        }
    }
    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        if Self::length(&a).max(Self::length(&b)) <= 300 {
            return convolve_karatsuba(&a, &b);
        }
        if Self::length(&a).min(Self::length(&b)) <= 60 {
            return convolve_naive(&a, &b);
        }
        let len = (Self::length(&a) + Self::length(&b)).saturating_sub(1);
        let mut a = Self::transform(a, len);
        let b = Self::transform(b, len);
        Self::multiply(&mut a, &b);
        Self::inverse_transform(a, len)
    }
}

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>, 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 mut f = (
            MVec::<N1>::with_capacity(npot),
            MVec::<N2>::with_capacity(npot),
            MVec::<N3>::with_capacity(npot),
        );
        for t in t {
            f.0.push(t.into());
            f.1.push(t.into());
            f.2.push(t.into());
        }
        f.0.resize_with(npot, Zero::zero);
        f.1.resize_with(npot, Zero::zero);
        f.2.resize_with(npot, Zero::zero);
        ntt(&mut f.0);
        ntt(&mut f.1);
        ntt(&mut f.2);
        f
    }

    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        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;
        Convolve::<N1>::inverse_transform(f.0, len)
            .into_iter()
            .zip(Convolve::<N2>::inverse_transform(f.1, len))
            .zip(Convolve::<N3>::inverse_transform(f.2, len))
            .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();
                d1 as u64 + d2 as u64 * m1 + d3 as u64 * m2
            })
            .collect()
    }

impl MInt<DynModuloU32>

pub fn set_mod(m: u32)

Examples found in repository

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

pub fn sqrt_mod(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, q, yp: [(u32, u32)]);
    for (y, p) in yp.take(q) {
        DynMIntU32::set_mod(p);
        if let Some(x) = DynMIntU32::from(y).sqrt() {
            writeln!(writer, "{}", x).ok();
        } else {
            writeln!(writer, "-1").ok();
        }
    }
}

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

pub fn binomial_coefficient_prime_mod(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, 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);
        iter_print!(writer, ans);
    }
}

impl MInt<DynModuloU64>

pub fn set_mod(m: u64)

Trait Implementations

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> 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> AddAssign<&MInt<M>> for MInt<M>

where M: MIntBase,

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

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> 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> 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<&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> 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> DivAssign<&MInt<M>> for MInt<M>

where M: MIntBase,

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

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> 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 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 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 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 isize

where M: MIntConvert<isize>,

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

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 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 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 usize

where M: MIntConvert<usize>,

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

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

where M: MIntConvert<i8>,

fn from(x: i8) -> 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<u128> for MInt<M>

where M: MIntConvert<u128>,

fn from(x: u128) -> 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<u8> for MInt<M>

where M: MIntConvert<u8>,

fn from(x: u8) -> 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> IterScan for MInt<M>

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

type Output = MInt<M>

fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output>

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> 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> MulAssign<&MInt<M>> for MInt<M>

where M: MIntBase,

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

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> 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> 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> 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

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

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

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

impl<'a, 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> 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<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> 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<&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> 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> SubAssign<&MInt<M>> for MInt<M>

where M: MIntBase,

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

Performs the -= operation.

impl<M> SubAssign for MInt<M>

where M: MIntBase,

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

Performs the -= operation.

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

where M: MIntBase,

fn zero() -> Self

fn is_zero(&self) -> bool

where Self: PartialEq,

fn set_zero(&mut self)

impl<M> Copy for MInt<M>

where M: MIntBase,

impl<M> Eq for MInt<M>

where M: MIntBase,