#669047 (Rust) No.732 3PrimeCounting

提出ソース
結果

問題	No.732 3PrimeCounting
ユーザー	へのく
提出日時	2021-06-22 20:52:55
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	491 ms / 3,000 ms
コード長	42,553 bytes
コンパイル時間	17,308 ms
コンパイル使用メモリ	378,164 KB
実行使用メモリ	19,440 KB
最終ジャッジ日時	2024-06-23 16:59:28
合計ジャッジ時間	25,966 ms
ジャッジサーバーID （参考情報）	judge3 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	1 ms 5,248 KB
testcase_03	AC	1 ms 5,248 KB
testcase_04	AC	1 ms 5,248 KB
testcase_05	AC	0 ms 5,248 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	1 ms 5,376 KB
testcase_10	AC	1 ms 5,376 KB
testcase_11	AC	1 ms 5,376 KB
testcase_12	AC	1 ms 5,376 KB
testcase_13	AC	1 ms 5,376 KB
testcase_14	AC	1 ms 5,376 KB
testcase_15	AC	1 ms 5,376 KB
testcase_16	AC	1 ms 5,376 KB
testcase_17	AC	1 ms 5,376 KB
testcase_18	AC	1 ms 5,376 KB
testcase_19	AC	0 ms 5,376 KB
testcase_20	AC	3 ms 5,376 KB
testcase_21	AC	8 ms 5,376 KB
testcase_22	AC	8 ms 5,376 KB
testcase_23	AC	1 ms 5,376 KB
testcase_24	AC	1 ms 5,376 KB
testcase_25	AC	15 ms 5,376 KB
testcase_26	AC	13 ms 5,376 KB
testcase_27	AC	4 ms 5,376 KB
testcase_28	AC	4 ms 5,376 KB
testcase_29	AC	7 ms 5,376 KB
testcase_30	AC	6 ms 5,376 KB
testcase_31	AC	8 ms 5,376 KB
testcase_32	AC	12 ms 5,376 KB
testcase_33	AC	13 ms 5,376 KB
testcase_34	AC	13 ms 5,376 KB
testcase_35	AC	13 ms 5,376 KB
testcase_36	AC	13 ms 5,376 KB
testcase_37	AC	2 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	12 ms 5,376 KB
testcase_40	AC	8 ms 5,376 KB
testcase_41	AC	7 ms 5,376 KB
testcase_42	AC	8 ms 5,376 KB
testcase_43	AC	7 ms 5,376 KB
testcase_44	AC	8 ms 5,376 KB
testcase_45	AC	4 ms 5,376 KB
testcase_46	AC	5 ms 5,376 KB
testcase_47	AC	6 ms 5,376 KB
testcase_48	AC	15 ms 5,376 KB
testcase_49	AC	15 ms 5,376 KB
testcase_50	AC	8 ms 5,376 KB
testcase_51	AC	8 ms 5,376 KB
testcase_52	AC	3 ms 5,376 KB
testcase_53	AC	32 ms 5,376 KB
testcase_54	AC	237 ms 11,276 KB
testcase_55	AC	238 ms 11,272 KB
testcase_56	AC	239 ms 11,400 KB
testcase_57	AC	69 ms 5,376 KB
testcase_58	AC	67 ms 5,376 KB
testcase_59	AC	32 ms 5,376 KB
testcase_60	AC	114 ms 6,068 KB
testcase_61	AC	113 ms 6,064 KB
testcase_62	AC	241 ms 12,556 KB
testcase_63	AC	140 ms 7,680 KB
testcase_64	AC	116 ms 6,648 KB
testcase_65	AC	114 ms 6,640 KB
testcase_66	AC	1 ms 5,376 KB
testcase_67	AC	1 ms 5,376 KB
testcase_68	AC	241 ms 12,068 KB
testcase_69	AC	238 ms 12,064 KB
testcase_70	AC	236 ms 11,320 KB
testcase_71	AC	236 ms 11,320 KB
testcase_72	AC	140 ms 7,400 KB
testcase_73	AC	294 ms 15,376 KB
testcase_74	AC	300 ms 15,380 KB
testcase_75	AC	15 ms 5,376 KB
testcase_76	AC	235 ms 11,724 KB
testcase_77	AC	68 ms 5,376 KB
testcase_78	AC	288 ms 13,788 KB
testcase_79	AC	236 ms 11,988 KB
testcase_80	AC	285 ms 13,080 KB
testcase_81	AC	236 ms 11,492 KB
testcase_82	AC	3 ms 5,376 KB
testcase_83	AC	66 ms 5,376 KB
testcase_84	AC	110 ms 5,704 KB
testcase_85	AC	229 ms 10,700 KB
testcase_86	AC	285 ms 13,432 KB
testcase_87	AC	491 ms 19,440 KB
testcase_88	AC	488 ms 19,440 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#![allow(non_snake_case)]
use crate::{
    fps::{conv_i64::ConvI64, formal_power_series::Fps},
    primes::utils::sieve,
    scanner::Scanner,
};

fn main() {
    let mut scan = Scanner::new();
    let n = scan.int();
    let (primes, _) = sieve(3 * n);
    let mut ret = 0i64;
    let f = Fps::<i64, ConvI64>::new_degs(&primes.take_while(|&p| p <= n));

    let mut g = &f * &f * &f;
    g.resize(3 * n + 1);
    ret += primes.map(|p| g[p]).sum();

    let mut g = Fps::new_degs(&primes.take_while(|&p| p <= n).map(|p| p * 2));

    g *= &f;
    g.resize(3 * n + 1);
    ret -= 3 * primes.map(|p| g[p]).sum();

    println!("{}", ret / 6);
}
pub mod primes {
    pub mod utils {
        use crate::arraylist::List;

        pub fn sieve(n: isize) -> (List<isize>, List<bool>) {
            let mut primes = List::new();
            let mut is_prime = List::init(true, n + 1);
            is_prime.fill(0..=1, false);
            for i in 2..n + 1 {
                if is_prime[i] {
                    primes.push(i);
                    for j in (2..).map(|j| j * i).take_while(|&j| j <= n) {
                        is_prime[j] = false;
                    }
                }
            }
            (primes, is_prime)
        }
    }
}
pub mod scanner {
    use std::io::{stdin, BufReader, Bytes, Read, Stdin};
    use std::str::FromStr;

    pub struct Scanner {
        buf: Bytes<BufReader<Stdin>>,
    }

    impl Scanner {
        pub fn new() -> Scanner {
            Scanner {
                buf: BufReader::new(stdin()).bytes(),
            }
        }

        #[inline]
        fn token<T: std::iter::FromIterator<char>>(&mut self) -> T {
            self.buf
                .by_ref()
                .map(|c| c.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        }

        #[inline]
        pub fn read<T: FromStr>(&mut self) -> T {
            self.string().parse().ok().unwrap()
        }

        #[inline]
        pub fn string(&mut self) -> String {
            self.token()
        }

        #[inline]
        pub fn int(&mut self) -> isize {
            self.read()
        }
    }
}
pub mod nums {
    use std::mem::swap;

    pub fn ceil_pow2(n: u32) -> u32 {
        32 - n.saturating_sub(1).leading_zeros()
    }

    pub fn inv_gcd(a: i64, b: i64) -> (i64, i64) {
        let a = a.rem_euclid(b);
        if a == 0 {
            return (b, 0);
        }

        let mut s = b;
        let mut t = a;
        let mut m0 = 0;
        let mut m1 = 1;

        while t != 0 {
            let u = s / t;
            s -= t * u;
            m0 -= m1 * u;

            swap(&mut s, &mut t);
            swap(&mut m0, &mut m1);
        }

        if m0 < 0 {
            m0 += b / s;
        }
        (s, m0)
    }

    pub fn primitive_root(m: i32) -> i32 {
        match m {
            2 => return 1,
            167_772_161 => return 3,
            469_762_049 => return 3,
            754_974_721 => return 11,
            998_244_353 => return 3,
            _ => {}
        }

        let mut divs = [0; 20];
        divs[0] = 2;
        let mut cnt = 1;
        let mut x = (m - 1) / 2;
        while x % 2 == 0 {
            x /= 2;
        }
        for i in (3..std::i32::MAX).step_by(2) {
            if i as i64 * i as i64 > x as i64 {
                break;
            }
            if x % i == 0 {
                divs[cnt] = i;
                cnt += 1;
                while x % i == 0 {
                    x /= i;
                }
            }
        }
        if x > 1 {
            divs[cnt] = x;
            cnt += 1;
        }
        let mut g = 2;
        loop {
            if (0..cnt).all(|i| pow_mod(g as _, ((m - 1) / divs[i]) as _, m as _) != 1) {
                break g as i32;
            }
            g += 1;
        }
    }

    pub fn pow_mod(mut a: i64, mut n: i64, m: i64) -> i64 {
        let mut res = 1;
        a %= m;
        while n > 0 {
            if n & 1 == 1 {
                res *= a;
                res %= m;
            }
            a = (a * a) % m;
            n >>= 1;
        }
        res
    }
}
pub mod modulo {
    use crate::nums::inv_gcd;
    use crate::{impl_integer_functions, independent::integer::Int};
    use std::cell::RefCell;
    use std::fmt::Debug;
    use std::marker::PhantomData;
    use std::ops::*;
    use std::sync::atomic::{self, AtomicU32};
    use std::thread::LocalKey;

    pub trait Modulus: 'static + PartialEq + Eq + Copy + Clone + std::hash::Hash + Ord {
        const M: u32;
        const HINT_M_IS_PRIME: bool;
        fn butterfly_cache() -> &'static LocalKey<RefCell<Option<ButterflyCache<Self>>>>;
    }

    pub trait DynamicModulus:
        'static + PartialEq + Eq + Copy + Clone + std::hash::Hash + Ord
    {
        fn state() -> &'static AtomicU32 {
            static M: AtomicU32 = AtomicU32::new(1_000_000_007);
            &M
        }
        fn update(m: u32) {
            Self::state().store(m, atomic::Ordering::SeqCst)
        }
        fn umod() -> u32 {
            Self::state().load(atomic::Ordering::SeqCst)
        }
    }

    #[derive(PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)]
    pub enum DefaultId {}
    impl DynamicModulus for DefaultId {}

    macro_rules! impl_from_for_modint {
        ($name:ident, $guard: ident, $($tpe:ident),*) => {
            $(
                impl<T: $guard> From<$tpe> for $name<T> {
                    fn from(n: $tpe) -> Self {
                        Self::new(n)
                    }
                }
            )*
        };
    }

    macro_rules! impl_assign {
        ($name:ident, $guard:ident, $($t1:ty, $t2:ty, $fa:ident, $f:ident),*) => {
            $(
                impl<T: $guard> $t1 for $name<T> {
                    type Output = Self;
                    #[inline]
                    fn $f(self, other: Self) -> Self {
                        <Self as ModInt>::$f(self, other)
                    }
                }
                impl<T: $guard> $t2 for $name<T> {
                    #[inline]
                    fn $fa(&mut self, other: Self) {
                        *self = <Self as ModInt>::$f(*self, other);
                    }
                }
            )*
        };
    }

    macro_rules! impl_modint_structs {
        ($name:ident, $guard:ident) => {
            #[derive(PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)]
            #[repr(transparent)]
            pub struct $name<T> {
                pub val: u32,
                phantom: PhantomData<fn() -> T>,
            }
            impl<T> Debug for $name<T> {
                fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
                    self.val.fmt(f)
                }
            }
            impl<T: $guard> $name<T> {
                #[inline]
                pub fn new<U: Int>(a: U) -> Self {
                    <Self as ModInt>::new(a)
                }
                #[inline]
                pub fn inv(self) -> Self {
                    <Self as ModInt>::inv(self)
                }
                #[inline]
                pub fn raw(val: u32) -> Self {
                    Self {
                        val,
                        phantom: PhantomData,
                    }
                }
                #[inline]
                pub fn pow<U: Int>(self, x: U) -> Self {
                    <Self as ModInt>::pow(self, x)
                }
                #[inline]
                pub fn zero() -> Self {
                    <Self as Int>::zero()
                }
                #[inline]
                pub fn one() -> Self {
                    <Self as Int>::one()
                }
            }
            impl<T> std::fmt::Display for $name<T> {
                fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
                    write!(f, "{}", self.val)
                }
            }
            impl_from_for_modint!(
                $name, $guard, u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize
            );
            impl_assign!(
                $name, $guard, Add, AddAssign, add_assign, add, Sub, SubAssign, sub_assign, sub,
                Mul, MulAssign, mul_assign, mul, Div, DivAssign, div_assign, div, Rem, RemAssign,
                rem_assign, rem
            );
            impl<T: $guard> Int for $name<T> {
                impl_integer_functions!(|s: &Self| s.val, |x| Self::new(x), |s: &Self, n: i64| s
                    .pow(n));
            }
        };
    }

    impl_modint_structs!(StaticModInt, Modulus);
    impl_modint_structs!(DynamicModInt, DynamicModulus);

    #[macro_export]
    macro_rules! modint {
        () => {$crate::modint!(1000000007, true);};
        ($m:literal) => {$crate::modint!($m, true);};
        ($m:literal, $is_prime:literal) => {
            $crate::modint!($m, ModValue, $is_prime);
            #[allow(dead_code)]
            type Z = $crate::modulo::StaticModInt<ModValue>;
        };
        ($name:ident) => {
            $crate::modint!($name, $name, true);
        };
        ($value:expr, $name:ident, $is_prime:literal) => {
            #[derive(Debug, PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)]
            pub enum $name {}
            impl $crate::modulo::Modulus for $name {
                const M: u32 = $value as _;
                const HINT_M_IS_PRIME: bool = $is_prime;
                fn butterfly_cache() -> &'static ::std::thread::LocalKey<::std::cell::RefCell<::std::option::Option<$crate::modulo::ButterflyCache<Self>>>> {
                    thread_local! {
                        static BUTTERFLY_CACHE: ::std::cell::RefCell<::std::option::Option<$crate::modulo::ButterflyCache<$name>>> = ::std::default::Default::default();
                    }
                    &BUTTERFLY_CACHE
                }
            }
        };
    }

    pub type D = DynamicModInt<DefaultId>;

    pub trait ModInt: Int {
        fn new<U: Int>(val: U) -> Self {
            let x = val.to_i128();
            Self::raw(x.rem_euclid(Self::modulus() as i128) as _)
        }
        fn inv(self) -> Self {
            if Self::mod_is_prime() {
                Self::pow(self, Self::modulus() - 2)
            } else {
                let (g, x) = inv_gcd(Self::val(self) as _, Self::modulus() as _);
                if g != 1 {
                    panic!("the multiplicative inverse does not exist");
                } else {
                    Self::new(x)
                }
            }
        }
        fn raw(val: u32) -> Self;
        fn val(self) -> u32;
        fn modulus() -> u32;
        fn mod_is_prime() -> bool;
        fn add(self, other: Self) -> Self {
            let mut ret = self.val() + other.val();
            if ret >= Self::modulus() {
                ret -= Self::modulus();
            }
            Self::raw(ret)
        }
        fn sub(self, other: Self) -> Self {
            let mut ret = self.val().wrapping_sub(other.val());
            if ret >= Self::modulus() {
                ret = ret.wrapping_add(Self::modulus());
            }
            Self::raw(ret)
        }
        fn mul(self, other: Self) -> Self {
            Self::raw(
                (u64::from(self.val()) * u64::from(other.val()) % u64::from(Self::modulus())) as _,
            )
        }
        fn div(self, other: Self) -> Self {
            self * other.inv()
        }
        fn rem(self, other: Self) -> Self {
            Self::raw(self.val() % other.val())
        }
        fn pow<U: Int>(self, x: U) -> Self {
            let mut n = x.to_i64();
            let mut a = self;
            let mut res = Self::raw(1);
            while n > 0 {
                if n & 1 == 1 {
                    res *= a;
                }
                a = a * a;
                n >>= 1;
            }
            res
        }
    }

    impl<M: Modulus> ModInt for StaticModInt<M> {
        fn raw(val: u32) -> Self {
            Self::raw(val)
        }
        fn val(self) -> u32 {
            self.val
        }
        fn modulus() -> u32 {
            M::M
        }
        fn mod_is_prime() -> bool {
            M::HINT_M_IS_PRIME
        }
    }

    impl<M: DynamicModulus> ModInt for DynamicModInt<M> {
        fn raw(val: u32) -> Self {
            Self::raw(val)
        }
        fn val(self) -> u32 {
            self.val
        }
        fn modulus() -> u32 {
            M::umod()
        }
        fn mod_is_prime() -> bool {
            false
        }
    }

    pub struct ButterflyCache<T> {
        pub sum_e: Vec<StaticModInt<T>>,
        pub sum_ie: Vec<StaticModInt<T>>,
    }
}

pub mod fps {
    pub mod convolution {
        use crate::{
            arraylist::List,
            independent::integer::Int,
            modint,
            modulo::{ButterflyCache, Modulus, StaticModInt},
            nums::*,
        };

        fn prepare<M: Modulus>() -> ButterflyCache<M> {
            let g = StaticModInt::<M>::raw(primitive_root(M::M as i32) as u32);
            let mut es = [StaticModInt::<M>::raw(0); 30];
            let mut ies = [StaticModInt::<M>::raw(0); 30];
            let cnt2 = (M::M - 1).trailing_zeros() as usize;
            let mut e = g.pow((M::M - 1) >> cnt2);
            let mut ie = e.inv();
            for i in (2..=cnt2).rev() {
                es[i - 2] = e;
                ies[i - 2] = ie;
                e *= e;
                ie *= ie;
            }
            let sum_e = es
                .iter()
                .scan(StaticModInt::new(1), |acc, e| {
                    *acc *= *e;
                    Some(*acc)
                })
                .collect();
            let sum_ie = ies
                .iter()
                .scan(StaticModInt::new(1), |acc, ie| {
                    *acc *= *ie;
                    Some(*acc)
                })
                .collect();
            ButterflyCache { sum_e, sum_ie }
        }

        fn butterfly<M: Modulus>(a: &mut [StaticModInt<M>]) {
            let n = a.len();
            let h = ceil_pow2(n as u32);

            M::butterfly_cache().with(|cache| {
                let mut cache = cache.borrow_mut();
                let ButterflyCache { sum_e, .. } = cache.get_or_insert_with(prepare);
                for ph in 1..=h {
                    let w = 1 << (ph - 1);
                    let p = 1 << (h - ph);
                    let mut now = StaticModInt::<M>::new(1);
                    for s in 0..w {
                        let offset = s << (h - ph + 1);
                        for i in 0..p {
                            let l = a[i + offset];
                            let r = a[i + offset + p] * now;
                            a[i + offset] = l + r;
                            a[i + offset + p] = l - r;
                        }
                        now *= sum_e[(!s).trailing_zeros() as usize];
                    }
                }
            });
        }

        fn butterfly_inv<M: Modulus>(a: &mut [StaticModInt<M>]) {
            let n = a.len();
            let h = ceil_pow2(n as u32);
            M::butterfly_cache().with(|cache| {
                let mut cache = cache.borrow_mut();
                let ButterflyCache { sum_ie, .. } = cache.get_or_insert_with(prepare);
                for ph in (1..=h).rev() {
                    let w = 1 << (ph - 1);
                    let p = 1 << (h - ph);
                    let mut inow = StaticModInt::<M>::new(1);
                    for s in 0..w {
                        let offset = s << (h - ph + 1);
                        for i in 0..p {
                            let l = a[i + offset];
                            let r = a[i + offset + p];
                            a[i + offset] = l + r;
                            a[i + offset + p] = StaticModInt::new(M::M + l.val - r.val) * inow;
                        }
                        inow *= sum_ie[(!s).trailing_zeros() as usize];
                    }
                }
            })
        }

        pub fn convolution_naive<T: Int>(a: &[T], b: &[T]) -> List<T> {
            if a.is_empty() || b.is_empty() {
                return vec![].into();
            }
            let (n, m) = (a.len(), b.len());
            let (n, m, a, b) = if n < m { (m, n, b, a) } else { (n, m, a, b) };
            let mut ans = vec![T::zero(); n + m - 1];
            for i in 0..n {
                for j in 0..m {
                    ans[i + j] += a[i] * b[j];
                }
            }
            ans.into()
        }

        pub fn convolution_ntt<M: Modulus>(
            a: &[StaticModInt<M>],
            b: &[StaticModInt<M>],
        ) -> List<StaticModInt<M>> {
            if a.is_empty() || b.is_empty() {
                return vec![].into();
            }
            let (n, m) = (a.len(), b.len());

            if n.min(m) <= 60 {
                return convolution_naive(a, b);
            }

            let (mut a, mut b) = (a.to_owned(), b.to_owned());
            let z = 1 << ceil_pow2((n + m - 1) as _);
            a.resize(z, StaticModInt::raw(0));
            butterfly(&mut a);
            b.resize(z, StaticModInt::raw(0));
            butterfly(&mut b);
            for (a, b) in a.iter_mut().zip(&b) {
                *a *= *b;
            }
            butterfly_inv(&mut a);
            a.resize(n + m - 1, StaticModInt::raw(0));
            let iz = StaticModInt::new(z).inv();
            for a in &mut a {
                *a *= iz;
            }
            a.into()
        }

        fn convolution_raw<T: Int, M: Modulus>(a: &[T], b: &[T]) -> List<T> {
            convolution_raw_mod::<T, M>(&a, &b)
                .into_iter()
                .map(|z| T::from_u32(z.val))
                .collect()
        }

        fn convolution_raw_mod<T: Int, M: Modulus>(a: &[T], b: &[T]) -> List<StaticModInt<M>> {
            let a = a
                .iter()
                .cloned()
                .map(StaticModInt::<M>::new)
                .collect::<Vec<_>>();
            let b = b
                .iter()
                .cloned()
                .map(StaticModInt::<M>::new)
                .collect::<Vec<_>>();
            convolution_ntt::<M>(&a, &b)
        }

        pub fn convolution_i64(a: &[i64], b: &[i64]) -> List<i64> {
            const M1: u64 = 754_974_721;
            const M2: u64 = 167_772_161;
            const M3: u64 = 469_762_049;
            const M2M3: u64 = M2 * M3;
            const M1M3: u64 = M1 * M3;
            const M1M2: u64 = M1 * M2;
            const M1M2M3: u64 = M1M2.wrapping_mul(M3);

            modint!(M1);
            modint!(M2);
            modint!(M3);

            if a.is_empty() || b.is_empty() {
                return List::new();
            }

            let (_, i1) = inv_gcd(M2M3 as _, M1 as _);
            let (_, i2) = inv_gcd(M1M3 as _, M2 as _);
            let (_, i3) = inv_gcd(M1M2 as _, M3 as _);

            let c1 = convolution_raw::<_, M1>(a, b);
            let c2 = convolution_raw::<_, M2>(a, b);
            let c3 = convolution_raw::<_, M3>(a, b);

            c1.into_iter()
                .zip(c2)
                .zip(c3)
                .map(|((c1, c2), c3)| {
                    const OFFSET: &[u64] = &[0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3];

                    let mut x = [(c1, i1, M1, M2M3), (c2, i2, M2, M1M3), (c3, i3, M3, M1M2)]
                        .iter()
                        .map(|&(c, i, m1, m2)| {
                            c.wrapping_mul(i).rem_euclid(m1 as _).wrapping_mul(m2 as _)
                        })
                        .fold(0, i64::wrapping_add);

                    let mut diff = c1 - x.rem_euclid(M1 as _);
                    if diff < 0 {
                        diff += M1 as i64;
                    }
                    x = x.wrapping_sub(OFFSET[diff.rem_euclid(5) as usize] as _);
                    x
                })
                .collect()
        }
    }
    pub mod conv_i64 {
        use crate::{
            arraylist::List,
            fps::{convolution::convolution_i64, formal_power_series::Conv},
        };

        #[derive(Debug, PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)]
        pub enum ConvI64 {}
        impl Conv<i64> for ConvI64 {
            fn convolution(a: &[i64], b: &[i64]) -> List<i64> {
                convolution_i64(a, b)
            }
        }

        #[macro_export]
        macro_rules! fps_i64 {
            ($($args:tt)+) => {$crate::fps!([$($args)+] [$crate::fps::conv_i64::ConvI64])};
        }
    }
    pub mod formal_power_series {
        use std::{fmt::Debug, iter::FromIterator, marker::PhantomData, ops::*};

        use crate::{
            arraylist::{lst, List},
            independent::integer::Int,
            list,
            modulo::ModInt,
        };

        pub trait Conv<T> {
            fn convolution(a: &[T], b: &[T]) -> List<T>;
        }

        impl<T: Int, F: Conv<T>> From<&lst<T>> for Fps<T, F> {
            fn from(lst: &lst<T>) -> Self {
                Self::new(lst.list())
            }
        }

        impl<T: Int, F: Conv<T>> FromIterator<T> for Fps<T, F> {
            fn from_iter<U: IntoIterator<Item = T>>(iter: U) -> Self {
                Self::new(iter.into_iter().collect())
            }
        }

        #[derive(PartialEq, Eq)]
        pub struct Fps<T, F: Conv<T>> {
            pub data: List<T>,
            phantom: PhantomData<fn() -> F>,
        }

        impl<T: Int, F: Conv<T>> Clone for Fps<T, F> {
            fn clone(&self) -> Self {
                Self::new(self.data.clone())
            }
        }

        impl<T: Int + Debug, F: Conv<T>> Debug for Fps<T, F> {
            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
                self.data.fmt(f)
            }
        }

        impl<T: Int, F: Conv<T>> Fps<T, F> {
            pub fn new(data: List<T>) -> Fps<T, F> {
                Fps {
                    data,
                    phantom: PhantomData,
                }
            }

            pub fn new_degs(degrees: &lst<isize>) -> Fps<T, F> {
                degrees
                    .hist(degrees.max_item().map_or(0, |m| *m + 1))
                    .into_iter()
                    .map(T::from_isize)
                    .collect()
            }

            pub fn empty() -> Self {
                Self::new(List::new())
            }

            pub fn lens(&self) -> isize {
                self.data.lens()
            }

            pub fn is_empty(&self) -> bool {
                self.data.lens() == 0
            }

            pub fn resize(&mut self, new_len: isize) {
                self.data.resize(new_len, T::zero());
            }

            pub fn shrink(&mut self) {
                while self.data.last() == Some(&T::zero()) {
                    self.data.pop();
                }
            }

            pub fn pre(&self, size: isize) -> Self {
                Self::from(&self.data[..self.lens().min(size)])
            }

            pub fn inv(&self, deg: impl Into<Option<isize>>) -> Self
            where
                T: ModInt,
            {
                assert!(self[0] != T::zero());
                let n = self.lens();
                let deg = deg.into().unwrap_or(n);
                let mut ret = Self::new(list![T::one() / self[0]]);
                let mut i = 1;
                while i < deg {
                    ret = (&ret + &ret - &ret * &ret * &self.pre(i << 1)).pre(i << 1);
                    i <<= 1;
                }
                ret.pre(deg)
            }
        }

        macro_rules! impl_ops {
            ($({$guard:ident, $tpe:ident, $fname:ident, $op:tt, [$($lhs:tt)+], [$($rhs:tt)+]})*) => {
                $(impl<T: $guard, F: Conv<T>> $tpe<$($rhs)+> for $($lhs)+ {
                    type Output = Fps<T, F>;
                    fn $fname(self, rhs: $($rhs)+) -> Self::Output {
                        let mut ret: Fps<T, F> = self.clone();
                        ret $op rhs;
                        ret
                    }
                })*
            };
        }

        macro_rules! impl_ops_times {
            ($([$($lhs:tt)+] * [$($rhs:tt)+]),*; $([$($lhs2:tt)+] * [$($rhs2:tt)+]),*) => {
                $(
                    impl_ops!(
                        {Int, Add, add, +=, [$($lhs)+], [$($rhs)+]}
                        {Int, Sub, sub, -=, [$($lhs)+], [$($rhs)+]}
                        {Int, Mul, mul, *=, [$($lhs)+], [$($rhs)+]}
                        {ModInt, Div, div, /=, [$($lhs)+], [$($rhs)+]}
                        {ModInt, Rem, rem, %=, [$($lhs)+], [$($rhs)+]}
                    );
                )*
                $(
                    impl_ops!(
                        {Int, Add, add, +=, [$($lhs2)+], [$($rhs2)+]}
                        {Int, Sub, sub, -=, [$($lhs2)+], [$($rhs2)+]}
                        {Int, Mul, mul, *=, [$($lhs2)+], [$($rhs2)+]}
                    );
                )*
            };
        }

        impl_ops_times!([Fps<T, F>] * [&Self], [Fps<T, F>] * [Self], [&Fps<T, F>] * [Self]; [Fps<T, F>] * [T], [&Fps<T, F>] * [T]);

        macro_rules! impl_assign_ops {
            ($([$($rhs:tt)+]),*) => {
                $(
                    impl<T: Int, F: Conv<T>> AddAssign<$($rhs)+> for Fps<T, F> {
                        fn add_assign(&mut self, rhs: $($rhs)+) {
                            if rhs.lens() > self.lens() {self.resize(rhs.lens())};
                            self.data.iter_mut().zip(rhs.data.iter()).for_each(|(e, r)| *e += *r);
                        }
                    }
                    impl<T: Int, F: Conv<T>> SubAssign<$($rhs)+> for Fps<T, F> {
                        fn sub_assign(&mut self, rhs: $($rhs)+) {
                            if rhs.lens() > self.lens() {self.resize(rhs.lens())};
                            self.data.iter_mut().zip(rhs.data.iter()).for_each(|(e,r)| *e -= *r);
                            self.shrink();
                        }
                    }
                    impl<T: Int, F: Conv<T>> MulAssign<$($rhs)+> for Fps<T, F> {
                        fn mul_assign(&mut self, rhs: $($rhs)+) {
                            self.data = F::convolution(&self.data, &rhs.data);
                        }
                    }
                    impl<T: ModInt, F: Conv<T>> RemAssign<$($rhs)+> for Fps<T, F> {
                        fn rem_assign(&mut self, rhs: $($rhs)+) {
                            *self -= &(&*self / &rhs * rhs);
                        }
                    }

                    impl<T: ModInt, F: Conv<T>> DivAssign<$($rhs)+> for Fps<T, F> {
                        fn div_assign(&mut self, rhs: $($rhs)+) {
                            let n = self.lens();
                            self.data = F::convolution(&self.data, &rhs.inv(n).data);
                            self.resize(n);
                        }
                    }
                )*
            };
        }

        impl_assign_ops!([Self], [&Self]);

        impl<T: Int, F: Conv<T>> Neg for &Fps<T, F> {
            type Output = Fps<T, F>;

            fn neg(self) -> Self::Output {
                let data = self.data.map(|x| T::zero() - x);
                Fps {
                    data,
                    phantom: PhantomData,
                }
            }
        }

        impl<T: Int, F: Conv<T>> AddAssign<T> for Fps<T, F> {
            fn add_assign(&mut self, rhs: T) {
                if self.is_empty() {
                    self.resize(1)
                };
                self[0] += rhs;
            }
        }

        impl<T: Int, F: Conv<T>> SubAssign<T> for Fps<T, F> {
            fn sub_assign(&mut self, rhs: T) {
                if self.is_empty() {
                    self.resize(1);
                }
                self[0] -= rhs;
                self.shrink();
            }
        }

        impl<T: Int, F: Conv<T>> MulAssign<T> for Fps<T, F> {
            fn mul_assign(&mut self, rhs: T) {
                for e in self.data.iter_mut() {
                    *e *= rhs;
                }
            }
        }

        impl<T: Int, F: Conv<T>> Shr<isize> for &Fps<T, F> {
            type Output = Fps<T, F>;

            fn shr(self, rhs: isize) -> Self::Output {
                if self.lens() <= rhs {
                    return Fps::<T, F>::empty();
                }
                Self::Output::from(&self.data[rhs..])
            }
        }

        impl<T: Int, F: Conv<T>> Shl<isize> for &Fps<T, F> {
            type Output = Fps<T, F>;

            fn shl(self, rhs: isize) -> Self::Output {
                let mut data = list![T::zero();rhs];
                data.append(&self.data);
                Self::Output::new(data)
            }
        }

        impl<T: Int, F: Conv<T>> Index<isize> for Fps<T, F> {
            type Output = T;

            fn index(&self, index: isize) -> &T {
                &self.data[index]
            }
        }

        impl<T: Int, F: Conv<T>> IndexMut<isize> for Fps<T, F> {
            fn index_mut(&mut self, index: isize) -> &mut T {
                &mut self.data[index]
            }
        }

        #[macro_export]
        macro_rules! fps {
            ([$($args:tt)+] [$($tpe:tt)+]) => {$crate::fps::formal_power_series::Fps::<_, $($tpe)+>::new($crate::list![$($args)+])};
        }
    }
}

pub mod independent {
    pub mod integer {
        use std::fmt::Display;
        use std::ops::*;

        pub trait Int:
            Add<Output = Self>
            + Sub<Output = Self>
            + Mul<Output = Self>
            + Div<Output = Self>
            + Rem<Output = Self>
            + AddAssign
            + SubAssign
            + MulAssign
            + DivAssign
            + RemAssign
            + std::hash::Hash
            + PartialEq
            + Eq
            + PartialOrd
            + Ord
            + Copy
            + Display
        {
            fn to_u8(&self) -> u8;
            fn to_u16(&self) -> u16;
            fn to_u32(&self) -> u32;
            fn to_u64(&self) -> u64;
            fn to_u128(&self) -> u128;
            fn to_i8(&self) -> i8;
            fn to_i16(&self) -> i16;
            fn to_i32(&self) -> i32;
            fn to_i64(&self) -> i64;
            fn to_i128(&self) -> i128;
            fn to_usize(&self) -> usize;
            fn to_isize(&self) -> isize;
            fn from_u8(x: u8) -> Self;
            fn from_u16(x: u16) -> Self;
            fn from_u32(x: u32) -> Self;
            fn from_u64(x: u64) -> Self;
            fn from_u128(x: u128) -> Self;
            fn from_i8(x: i8) -> Self;
            fn from_i16(x: i16) -> Self;
            fn from_i32(x: i32) -> Self;
            fn from_i64(x: i64) -> Self;
            fn from_i128(x: i128) -> Self;
            fn from_usize(x: usize) -> Self;
            fn from_isize(x: isize) -> Self;
            fn zero() -> Self;
            fn one() -> Self;
            fn next(&self) -> Self {
                *self + Self::one()
            }
            fn powint(&self, n: i64) -> Self;
        }

        #[macro_export]
        macro_rules! impl_integer_functions {
            ($to_op:expr, $from_op:expr, $pow:expr) => {
                impl_integer_functions!(
                    $to_op, $from_op, $pow,
                    to_u8, from_u8, u8,
                    to_u16, from_u16, u16,
                    to_u32, from_u32, u32,
                    to_u64, from_u64, u64,
                    to_u128, from_u128, u128,
                    to_i8, from_i8, i8,
                    to_i16, from_i16, i16,
                    to_i32, from_i32, i32,
                    to_i64, from_i64, i64,
                    to_i128, from_i128, i128,
                    to_usize, from_usize, usize,
                    to_isize, from_isize, isize
                );
            };
            ($to_op:expr, $from_op:expr, $pow:expr, $($tofn:ident, $fromfn:ident, $tpe:ident),*) => {
                $(
                    fn $tofn(&self) -> $tpe {
                        $to_op(self) as $tpe
                    }
                    fn $fromfn(x: $tpe) -> Self {
                        $from_op(x)
                    }
                )*
                fn zero() -> Self {$from_op(0)}
                fn one() -> Self {$from_op(1)}
                fn powint(&self, n: i64) -> Self {$pow(self, n)}
            };
        }

        macro_rules! impl_integer {
            ($($tpe:ident),*) => {
                $(
                    impl Int for $tpe {
                        impl_integer_functions!(
                            |s: &Self| *s, |x| x as $tpe, |s: &Self, n: i64| s.pow(n as u32)
                        );
                    }
                )*
            };
        }

        impl_integer!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize);
    }
}
pub mod arraylist {

    use std::ops::*;
    use std::slice::Iter;

    use std::fmt::Formatter;
    use std::iter::FromIterator;

    use crate::independent::integer::Int;

    #[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
    pub struct List<T> {
        pub data: Vec<T>,
    }

    impl<T> List<T> {
        #[inline]
        pub fn new() -> List<T> {
            List { data: vec![] }
        }
        #[inline]
        pub fn init(init: T, n: isize) -> List<T>
        where
            T: Clone,
        {
            List {
                data: vec![init; n as usize],
            }
        }

        #[inline]
        pub fn pop(&mut self) -> Option<T> {
            self.data.pop()
        }
        #[inline]
        pub fn push(&mut self, item: T) {
            self.data.push(item);
        }

        #[inline]
        pub fn append(&mut self, other: &lst<T>)
        where
            T: Clone,
        {
            self.data.append(&mut other.to_vec());
        }

        #[inline]
        pub fn resize(&mut self, new_len: isize, value: T)
        where
            T: Clone,
        {
            self.data.resize(new_len as usize, value);
        }
    }

    macro_rules! impl_idx {
        ($($tpe:ty, $t:ident [$($output:tt)+], $slf:ident, $index:ident, $f:expr),*) => {
            $(impl<$t> Index<$tpe> for List<$t> {
                type Output = $($output)+;
                #[inline]
                fn index(&$slf, $index: $tpe) -> &Self::Output {$f}
            })*
            $(impl<$t> Index<$tpe> for lst<$t> {
                type Output = $($output)+;
                #[inline]
                fn index(&$slf, $index: $tpe) -> &Self::Output {$f}
            })*
        }
    }

    macro_rules! impl_idx_mut {
        ($($tpe:ty, $slf:ident, $index:ident, $f:expr),*) => {
            $(impl<T> IndexMut<$tpe> for List<T> {
                #[inline]
                fn index_mut(&mut $slf, $index: $tpe) -> &mut Self::Output {$f}
            })*
            $(impl<T> IndexMut<$tpe> for lst<T> {
                #[inline]
                fn index_mut(&mut $slf, $index: $tpe) -> &mut Self::Output {$f}
            })*
        };
    }

    macro_rules! impl_idx_slice {
        ($($tpe:ty),*) => {
            impl_idx!($($tpe, T [lst<T>], self, i, self.as_slice(i)),*);
            impl_idx_mut!($($tpe, self, i, self.as_slice_mut(i)),*);
        };
    }

    impl_idx! {
        isize, T [T], self, i, self.at(i),
        char, T [T], self, i, self.at(i as isize - 'a' as isize)
    }

    impl_idx_slice! {
        Range<isize>, RangeTo<isize>, RangeFrom<isize>, RangeFull, RangeInclusive<isize>, RangeToInclusive<isize>
    }

    impl_idx_mut! {
        isize, self, i, self.at_mut(i),
        char, self, i, self.at_mut(i as isize - 'a' as isize)
    }

    impl<T> FromIterator<T> for List<T> {
        #[inline]
        fn from_iter<U: IntoIterator<Item = T>>(iter: U) -> Self {
            List {
                data: iter.into_iter().collect(),
            }
        }
    }

    impl<T> IntoIterator for List<T> {
        type Item = T;
        type IntoIter = std::vec::IntoIter<T>;

        #[inline]
        fn into_iter(self) -> std::vec::IntoIter<T> {
            self.data.into_iter()
        }
    }

    macro_rules! impl_traits {
        ($($tpe:tt),*) => {
            $(
                impl<T: std::fmt::Display> std::fmt::Display for $tpe<T> {
                    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
                        write!(f, "{}", self.iter().map(|x| format!("{}", x)).collect::<Vec<_>>().join(" "))
                    }
                }

                impl<T: std::fmt::Debug> std::fmt::Debug for $tpe<T> {
                    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
                        self.data.fmt(f)
                    }
                }

                impl<'a, T> IntoIterator for &'a $tpe<T> {
                    type Item = &'a T;
                    type IntoIter = Iter<'a, T>;

                    #[inline]
                    fn into_iter(self) -> Iter<'a, T> {
                        self.iter()
                    }
                }
            )*
        };
    }

    impl_traits!(List, lst);

    impl<T> From<Vec<T>> for List<T> {
        #[inline]
        fn from(vec: Vec<T>) -> Self {
            List { data: vec }
        }
    }

    impl<T: Clone> From<&[T]> for List<T> {
        #[inline]
        fn from(slice: &[T]) -> Self {
            slice.iter().cloned().collect()
        }
    }

    impl<T> Deref for List<T> {
        type Target = lst<T>;

        #[inline]
        fn deref(&self) -> &lst<T> {
            lst::new(&self.data)
        }
    }

    impl<T> DerefMut for List<T> {
        #[inline]
        fn deref_mut(&mut self) -> &mut lst<T> {
            lst::new_mut(&mut self.data)
        }
    }

    #[macro_export]
    macro_rules! list {
        () => { $crate::arraylist::List::new() };
        ($($v:expr),+ $(,)?) => { $crate::arraylist::List::from([$($v),+].to_vec()) };
        ($v:expr; $a:expr) => { $crate::arraylist::List::init($v, $a)};
        ($v:expr; $a:expr; $($rest:expr);+) => { $crate::arraylist::List::init(list!($v; $($rest);+), $a) };
    }

    #[allow(non_camel_case_types)]
    #[derive(PartialEq, Eq, PartialOrd, Ord)]
    #[repr(transparent)]
    pub struct lst<T> {
        data: [T],
    }

    impl<T> lst<T> {
        #[inline]
        pub fn new(slice: &[T]) -> &Self {
            unsafe { &*(slice as *const [T] as *const Self) }
        }
        #[inline]
        pub fn new_mut(slice: &mut [T]) -> &mut Self {
            unsafe { &mut *(slice as *mut [T] as *mut Self) }
        }
        #[inline]
        pub fn lens(&self) -> isize {
            self.data.len() as isize
        }
        #[inline]
        pub fn list(&self) -> List<T>
        where
            T: Clone,
        {
            self.cloned().collect()
        }

        #[inline]
        fn at(&self, index: isize) -> &T {
            if cfg!(debug_assertions) {
                self.data.index(index as usize)
            } else {
                unsafe { self.data.get_unchecked(index as usize) }
            }
        }
        #[inline]
        fn at_mut(&mut self, index: isize) -> &mut T {
            if cfg!(debug_assertions) {
                self.data.index_mut(index as usize)
            } else {
                unsafe { self.data.get_unchecked_mut(index as usize) }
            }
        }
        #[inline]
        pub fn as_slice(&self, range: impl RangeBounds<isize>) -> &lst<T> {
            if cfg!(debug_assertions) {
                lst::new(self.data.index(self.rgm(range)))
            } else {
                unsafe { lst::new(self.data.get_unchecked(self.rgm(range))) }
            }
        }
        #[inline]
        pub fn as_slice_mut(&mut self, range: impl RangeBounds<isize>) -> &mut lst<T> {
            if cfg!(debug_assertions) {
                lst::new_mut(self.data.index_mut(self.rgm(range)))
            } else {
                let r = self.rgm(range);
                unsafe { lst::new_mut(self.data.get_unchecked_mut(r)) }
            }
        }

        #[inline]
        pub fn cloned(&self) -> std::iter::Cloned<Iter<T>>
        where
            T: Clone,
        {
            self.iter().cloned()
        }

        #[inline]
        pub fn map<B, F>(&self, f: F) -> List<B>
        where
            T: Clone,
            F: FnMut(T) -> B,
        {
            self.cloned().map(f).collect()
        }

        #[inline]
        pub fn take_while<P>(&self, predicate: P) -> List<T>
        where
            T: Clone,
            P: FnMut(&T) -> bool,
        {
            self.cloned().take_while(predicate).collect()
        }

        #[inline]
        pub fn sum(&self) -> T
        where
            T: Int,
        {
            self.cloned().fold(T::zero(), |acc, x| acc + x)
        }

        #[inline]
        pub fn max_item(&self) -> Option<&T>
        where
            T: Ord,
        {
            self.iter().max()
        }

        #[inline]
        pub fn fill(&mut self, r: impl RangeBounds<isize>, item: T)
        where
            T: Clone,
        {
            for i in self.rgm(r) {
                self.data[i] = item.clone();
            }
        }
        #[inline]
        fn rgm(&self, r: impl RangeBounds<isize>) -> Range<usize> {
            (match r.start_bound() {
                Bound::Included(x) => *x as usize,
                Bound::Excluded(x) => *x as usize + 1,
                _ => 0,
            })
            .max(0)..(match r.end_bound() {
                Bound::Included(x) => *x as usize + 1,
                Bound::Excluded(x) => *x as usize,
                _ => self.len(),
            })
            .min(self.len())
        }
    }

    impl lst<isize> {
        #[inline]
        pub fn hist(&self, exclusive_ub: isize) -> List<isize> {
            let mut cnt = List::init(0, exclusive_ub);
            for &i in self {
                cnt[i] += 1;
            }
            cnt
        }
    }

    impl<T> Deref for lst<T> {
        type Target = [T];
        #[inline]
        fn deref(&self) -> &[T] {
            &self.data
        }
    }

    impl<T> DerefMut for lst<T> {
        #[inline]
        fn deref_mut(&mut self) -> &mut [T] {
            &mut self.data
        }
    }

    impl<'a, T> From<&'a [T]> for &'a lst<T> {
        #[inline]
        fn from(slice: &'a [T]) -> Self {
            lst::new(slice)
        }
    }
}
yukicoder

結果

テストケース

ソースコード
