結果

問題 No.3123 Inversion
ユーザー rhoo
提出日時 2025-06-07 14:58:27
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 716 ms / 10,000 ms
コード長 10,784 bytes
コンパイル時間 12,321 ms
コンパイル使用メモリ 401,704 KB
実行使用メモリ 115,328 KB
最終ジャッジ日時 2025-06-07 14:59:07
合計ジャッジ時間 35,952 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_imports,non_snake_case,dead_code)]
use std::{cmp::Reverse as Rev,collections::*,iter::*};
use proconio::{marker::*,*};



#[fastout]
fn main(){
    input!{
        t:usize,
        m:u32,
        case:[usize;t],
    }
    M::set_modulus(m);

    let M=|n:usize|M::new(n);
    
    let n=5e6 as usize+1;

    let mut fac=vec![M(0);n];
    fac[0]+=1;
    for i in 1..n{
        fac[i]=fac[i-1]*i;
    }
    
    let mut dp1=vec![M(0);n];
    dp1[0]+=1;
    dp1[1]+=1;
    for i in 4..n{
        if i%2==0{
            dp1[i]=dp1[i-4]*(i-2);
        } else{
            dp1[i]=dp1[i-4]*(i-3);
        }
    }
    
    let mut dp2=vec![M(0);n];
    dp2[0]+=1;
    dp2[1]+=1;
    dp2[2]+=2;
    dp2[3]+=2;
    for i in 4..n{
        if i%2==0{
            dp2[i]=dp2[i-4]*(i-2)+dp2[i-2]*2;
        } else{
            dp2[i]=dp2[i-4]*(i-3)+dp2[i-2]*2;
        }
    }

    let mut dp3=vec![M(0);n];
    dp3[0]+=1;
    dp3[1]+=1;
    for i in 2..n{
        dp3[i]=dp3[i-2]*(i/2)*2;
    }

    let mut dp4=vec![M(0);n];
    dp4[0]+=1;
    dp4[1]+=1;
    for i in 2..n{
        dp4[i]=dp4[i-1]+dp4[i-2]*(i-1);
    }

    let solve=|n:usize|->M{
        if n==1{
            return M(1);
        }

        // eprintln!("{}",dp1[n]);
        // eprintln!("{}",dp2[n]);

        // 位数4
        let a=dp1[n]+dp2[n];
        
        // 位数2
        let b=dp3[n]-a+(dp4[n]-dp2[n])*2;
        
        // 位数1
        let c=fac[n]-a-b;
        // eprintln!("{} {} {}",a,b,c);

        2*a+4*b+8*c
    };
    
    for &n in &case{
        let ans=solve(n);
        println!("{ans}");

        // break;
    }
} 




// use std::collections::*;
// use itertools::*;
// use ac_library::*;


// fn main(){
//     let n=4;
//     let mut id=HashMap::new();
//     let mut perm=vec![];

//     for (i,p) in (0..n).permutations(n).enumerate(){
//         perm.push(p.clone());
//         id.insert(p,i);
//     }

//     let rev=|a:&[usize]|->Vec<usize>{
//         (0..a.len()).rev().map(|i|a[i]).collect()
//     };

//     let inv=|a:&[usize]|->Vec<usize>{
//         let mut b=vec![!0;a.len()];
//         for i in 0..a.len(){
//             b[a[i]]=i;
//         }
//         b
//     };
    
//     let mut uf=Dsu::new(id.len());
//     for (i,p) in (0..n).permutations(n).enumerate(){
//         let ni=id[&rev(&p)];
//         uf.merge(i,ni);

//         let ni=id[&inv(&p)];
//         uf.merge(i,ni);
//     }

//     let gs=uf.groups();
//     // for i in 0..gs.len(){
//     //     if gs[i].len()==8{
//     //         for &id in &gs[i]{
//     //             eprintln!("{:?}",perm[id]);
//     //         }
//     //     }
//     // }
    
//     let mut cnt=[0;10];
//     for i in 0..gs.len(){
//         cnt[gs[i].len()]+=1;
//     }

//     for i in 0..cnt.len(){
//         if cnt[i]!=0{
//             println!("{}: {}",i,cnt[i]*i);
//         }
//     }
// }



// [2, 0, 1, 3]
// [3, 1, 0, 2]




type M=ModInt;
type ModInt = DynamicModInt;


static mut MODULO:u32=998244353;


#[derive(Clone, Copy, PartialEq, Eq, Default, Hash)]
struct DynamicModInt {
    val: u32,
}
impl DynamicModInt {
    fn set_modulus(m:u32) {
        unsafe{ MODULO = m }
    }
}

impl ModIntBase for DynamicModInt {
    fn modulus() -> u32 {
        unsafe{ MODULO }
    }
    unsafe fn raw(val: u32) -> Self {
        DynamicModInt { val }
    }
    fn val(self) -> u32 {
        self.val
    }
    fn inv(self) -> Self {
        assert!(self.val != 0, "divisor by zero");
        let inv_val = mod_inv_by_ext_gcd(self.val, Self::modulus());
        unsafe { Self::raw(inv_val) }
    }
}



impl std::fmt::Display for DynamicModInt {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.val)
    }
}

impl std::fmt::Debug for DynamicModInt {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.val)
    }
}


macro_rules! impl_from_int {
    ($($t:ty),*) => {
        $(impl From<$t> for DynamicModInt {
            fn from(x: $t) -> Self {
                DynamicModInt::new(x)
            }
        })*
    }
}

impl_from_int!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize);



impl std::ops::Add for DynamicModInt {
    type Output = Self;
    fn add(self, rhs: Self) -> Self::Output {
        let mut sum = self.val + rhs.val;
        if sum >= Self::modulus() {
            sum -= Self::modulus();
        }
        unsafe { Self::raw(sum) }
    }
}

impl std::ops::Sub for DynamicModInt {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self::Output {
        let diff = if self.val >= rhs.val {
            self.val - rhs.val
        } else {
            Self::modulus() + self.val - rhs.val
        };
        unsafe { Self::raw(diff) }
    }
}

impl std::ops::Mul for DynamicModInt {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self::Output {
        let prod = (self.val as u64 * rhs.val as u64 % Self::modulus() as u64) as u32;
        unsafe { Self::raw(prod) }
    }
}

impl std::ops::Div for DynamicModInt {
    type Output = Self;
    fn div(self, rhs: Self) -> Self::Output {
        self * rhs.inv()
    }
}



impl std::ops::AddAssign for DynamicModInt {
    fn add_assign(&mut self, rhs: Self) {
        *self = *self + rhs;
    }
}

impl std::ops::SubAssign for DynamicModInt {
    fn sub_assign(&mut self, rhs: Self) {
        *self = *self - rhs;
    }
}

impl std::ops::MulAssign for DynamicModInt {
    fn mul_assign(&mut self, rhs: Self) {
        *self = *self * rhs;
    }
}

impl std::ops::DivAssign for DynamicModInt {
    fn div_assign(&mut self, rhs: Self) {
        *self = *self / rhs;
    }
}



impl std::ops::Neg for DynamicModInt {
    type Output = Self;
    fn neg(self) -> Self::Output {
        if self.val == 0 {
            self
        } else {
            unsafe { Self::raw(Self::modulus() - self.val) }
        }
    }
}



impl std::str::FromStr for DynamicModInt {
    type Err = <u32 as std::str::FromStr>::Err;
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let x = s.parse::<u64>()?;
        Ok(DynamicModInt::new(x))
    }
}



macro_rules! impl_mod_int_ops_sub {
    ($trait:ident, $func:ident, $assign_trait:ident, $assign_func:ident, $op:tt, ($($t:ty),*)) => {
        $(
            impl std::ops::$trait<$t> for DynamicModInt {
                type Output = Self;
                fn $func(self, rhs: $t) -> Self::Output {
                    self $op DynamicModInt::new(rhs)
                }
            }
            impl std::ops::$trait<DynamicModInt> for $t {
                type Output = DynamicModInt;
                fn $func(self, rhs: DynamicModInt) -> Self::Output {
                    DynamicModInt::new(self) $op rhs
                }
            }
            impl std::ops::$assign_trait<$t> for DynamicModInt {
                fn $assign_func(&mut self, rhs: $t) {
                    *self = *self $op DynamicModInt::new(rhs);
                }
            }
        )*
    }
}

macro_rules! impl_mod_int_ops {
    ($($t:tt)*) => {
        impl_mod_int_ops_sub!($($t)*, (i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize));
    }
}

impl_mod_int_ops!(Add, add, AddAssign, add_assign, +);
impl_mod_int_ops!(Sub, sub, SubAssign, sub_assign, -);
impl_mod_int_ops!(Mul, mul, MulAssign, mul_assign, *);
impl_mod_int_ops!(Div, div, DivAssign, div_assign, /);



impl std::iter::Sum for DynamicModInt {
    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
        iter.fold(DynamicModInt::zero(), |acc, x| acc + x)
    }
}

impl std::iter::Product for DynamicModInt {
    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
        iter.fold(DynamicModInt::one(), |acc, x| acc * x)
    }
}



trait RemEuclidU32 {
    fn rem_euclid_u32(self, modulus: u32) -> u32;
}

macro_rules! impl_rem_euclid_u32_for_small_signed {
    ($($ty:tt),*) => {
        $(
            impl RemEuclidU32 for $ty {
                fn rem_euclid_u32(self, modulus: u32) -> u32 {
                    (self as i64).rem_euclid(i64::from(modulus)) as _
                }
            }
        )*
    }
}

impl_rem_euclid_u32_for_small_signed!(i8, i16, i32, i64, isize);

impl RemEuclidU32 for i128 {
    fn rem_euclid_u32(self, modulus: u32) -> u32 {
        self.rem_euclid(i128::from(modulus)) as _
    }
}

macro_rules! impl_rem_euclid_u32_for_small_unsigned {
    ($($ty:tt),*) => {
        $(
            impl RemEuclidU32 for $ty {
                fn rem_euclid_u32(self, modulus: u32) -> u32 {
                    self as u32 % modulus
                }
            }
        )*
    }
}

macro_rules! impl_rem_euclid_u32_for_large_unsigned {
    ($($ty:tt),*) => {
        $(
            impl RemEuclidU32 for $ty {
                fn rem_euclid_u32(self, modulus: u32) -> u32 {
                    (self % (modulus as $ty)) as _
                }
            }
        )*
    }
}

impl_rem_euclid_u32_for_small_unsigned!(u8, u16, u32);
impl_rem_euclid_u32_for_large_unsigned!(u64, u128);


#[cfg(target_pointer_width = "32")]
impl_rem_euclid_u32_for_small_unsigned!(usize);

#[cfg(target_pointer_width = "64")]
impl_rem_euclid_u32_for_large_unsigned!(usize);



trait ModIntBase: Default
    + std::str::FromStr
    + From<i8>
    + From<i16>
    + From<i32>
    + From<i64>
    + From<i128>
    + From<isize>
    + From<u8>
    + From<u16>
    + From<u32>
    + From<u64>
    + From<u128>
    + From<usize>
    + Copy
    + Eq
    + std::hash::Hash
    + std::fmt::Display
    + std::fmt::Debug
    + std::ops::Neg<Output = Self>
    + std::ops::Add<Output = Self>
    + std::ops::Sub<Output = Self>
    + std::ops::Mul<Output = Self>
    + std::ops::Div<Output = Self>
    + std::ops::AddAssign
    + std::ops::SubAssign
    + std::ops::MulAssign
    + std::ops::DivAssign
{
    fn modulus() -> u32;
    unsafe fn raw(val: u32) -> Self;
    fn val(self) -> u32;
    fn inv(self) -> Self;

    fn new(val: impl RemEuclidU32) -> Self {
        unsafe { Self::raw(val.rem_euclid_u32(Self::modulus())) }
    }

    fn zero() -> Self {
        unsafe { Self::raw(0) }
    }

    fn one() -> Self {
        unsafe { Self::raw(1) }
    }

    fn pow(self, mut n: u64) -> Self {
        let mut x = self;
        let mut r = Self::one();
        while n > 0 {
            if n & 1 == 1 {
                r *= x;
            }
            x *= x;
            n >>= 1;
        }
        r
    }
}



fn mod_inv_by_ext_gcd(x: u32, modulus: u32) -> u32 {
    let (mut a, mut b) = (x as i64, modulus as i64);
    let (mut u, mut v) = (1i64, 0i64);
    while b != 0 {
        let t = a / b;

        a -= t * b;
        (a,b)=(b,a);

        u -= t * v;
        (u,v)=(v,u);
    }
    assert!(a==1);

    ((u % modulus as i64 + modulus as i64) % modulus as i64) as u32
}
0