#654428 (Rust) No.1712 Read and Pile

• 問題: No.1712 Read and Pile
• ユーザー: akakimidori
• 提出日時: 2021-05-05 18:36:07
• 言語: Rust (1.83.0 + proconio)
• 結果: RE
• 実行時間: -
• コード長: 5,323 bytes
• コンパイル時間: 10,962 ms
• コンパイル使用メモリ: 391,484 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-09-17 16:53:09
• 合計ジャッジ時間: 12,567 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 1 RE * 2
other	RE * 40

ソースコード

// ---------- begin ModInt ----------
mod modint {

    #[allow(dead_code)]
    pub struct Mod;
    impl ConstantModulo for Mod {
        const MOD: u32 = 998_244_353;
    }

    use std::marker::*;
    use std::ops::*;

    pub trait Modulo {
        fn modulo() -> u32;
    }

    pub trait ConstantModulo {
        const MOD: u32;
    }

    impl<T> Modulo for T
    where
        T: ConstantModulo,
    {
        fn modulo() -> u32 {
            T::MOD
        }
    }

    pub struct ModInt<T>(pub u32, PhantomData<T>);

    impl<T> Clone for ModInt<T> {
        fn clone(&self) -> Self {
            ModInt::new_unchecked(self.0)
        }
    }

    impl<T> Copy for ModInt<T> {}

    impl<T: Modulo> Add for ModInt<T> {
        type Output = ModInt<T>;
        fn add(self, rhs: Self) -> Self::Output {
            let mut d = self.0 + rhs.0;
            if d >= T::modulo() {
                d -= T::modulo();
            }
            ModInt::new_unchecked(d)
        }
    }

    impl<T: Modulo> AddAssign for ModInt<T> {
        fn add_assign(&mut self, rhs: Self) {
            *self = *self + rhs;
        }
    }

    impl<T: Modulo> Sub for ModInt<T> {
        type Output = ModInt<T>;
        fn sub(self, rhs: Self) -> Self::Output {
            let mut d = T::modulo() + self.0 - rhs.0;
            if d >= T::modulo() {
                d -= T::modulo();
            }
            ModInt::new_unchecked(d)
        }
    }

    impl<T: Modulo> SubAssign for ModInt<T> {
        fn sub_assign(&mut self, rhs: Self) {
            *self = *self - rhs;
        }
    }

    impl<T: Modulo> Mul for ModInt<T> {
        type Output = ModInt<T>;
        fn mul(self, rhs: Self) -> Self::Output {
            let v = self.0 as u64 * rhs.0 as u64 % T::modulo() as u64;
            ModInt::new_unchecked(v as u32)
        }
    }

    impl<T: Modulo> MulAssign for ModInt<T> {
        fn mul_assign(&mut self, rhs: Self) {
            *self = *self * rhs;
        }
    }

    impl<T: Modulo> Neg for ModInt<T> {
        type Output = ModInt<T>;
        fn neg(self) -> Self::Output {
            if self.0 == 0 {
                Self::zero()
            } else {
                Self::new_unchecked(T::modulo() - self.0)
            }
        }
    }

    impl<T> std::fmt::Display for ModInt<T> {
        fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
            write!(f, "{}", self.0)
        }
    }

    impl<T: Modulo> From<usize> for ModInt<T> {
        fn from(val: usize) -> ModInt<T> {
            ModInt::new_unchecked((val % T::modulo() as usize) as u32)
        }
    }

    #[allow(dead_code)]
    impl<T> ModInt<T> {
        pub fn new_unchecked(d: u32) -> Self {
            ModInt(d, PhantomData)
        }
        pub fn zero() -> Self {
            ModInt::new_unchecked(0)
        }
        pub fn one() -> Self {
            ModInt::new_unchecked(1)
        }
        pub fn is_zero(&self) -> bool {
            self.0 == 0
        }
    }

    #[allow(dead_code)]
    impl<T: Modulo> ModInt<T> {
        pub fn new(d: u32) -> Self {
            ModInt::new_unchecked(d % T::modulo())
        }
        pub fn pow(&self, mut n: u64) -> Self {
            let mut t = Self::one();
            let mut s = *self;
            while n > 0 {
                if n & 1 == 1 {
                    t *= s;
                }
                s *= s;
                n >>= 1;
            }
            t
        }
        pub fn inv(&self) -> Self {
            assert!(self.0 != 0);
            self.pow(T::modulo() as u64 - 2)
        }
    }
}
// ---------- end ModInt ----------

use modint::*;
type M = ModInt<Mod>;

const MIN_N: usize = 1;
const MAX_N: usize = 200_000;
const MIN_M: usize = 1;
const MAX_M: usize = 200_000;

fn read() -> (usize, Vec<usize>) {
    let mut s = String::new();
    use std::io::Read;
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let mut next = |l: usize, r: usize| -> usize {
        let v = it.next().unwrap().parse::<usize>().unwrap();
        assert!(l <= v && v <= r);
        v
    };
    let n = next(MIN_N, MAX_N);
    let m = next(MIN_M, MAX_M);
    let mut a = vec![0; m];
    for a in a.iter_mut() {
        *a = next(0, n);
    }
    assert!(it.next().is_none());
    (n, a)
}

fn naive(n: usize, a: &[usize]) -> M {
    assert!(n <= 500);
    let mut mat = vec![vec![M::zero(); n]; n];
    for i in 0..n {
        for j in 0..i {
            mat[i][j] = M::one();
        }
    }
    let p = M::from(n).inv();
    let q = M::from(n - 2) * p;
    let mut ans = M::from(a.len());
    for &a in a.iter() {
        if a == 0 {
            ans += M::from(n - 1) * M::new(2).inv();
            for i in 0..n {
                for j in 0..i {
                    mat[i][j] = q * mat[i][j] + p;
                    mat[j][i] = q * mat[j][i] + p;
                }
            }
        } else {
            let a = a - 1;
            ans += mat[a].iter().fold(M::zero(), |s, a| s + *a);
            for j in 0..n {
                if a != j {
                    mat[a][j] = M::zero();
                    mat[j][a] = M::one();
                }
            }
        }
    }
    ans
}

fn main() {
    let (n, a) = read();
    let ans = naive(n, &a);
    println!("{}", ans);
}