#1033519 (Rust) No.2941 Sigma Music Game Score Problem

• 問題: No.2941 Sigma Music Game Score Problem
• ユーザー: kekenx
• 提出日時: 2024-12-28 14:42:30
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 90 ms / 2,500 ms
• コード長: 4,797 bytes
• コンパイル時間: 15,553 ms
• コンパイル使用メモリ: 395,004 KB
• 実行使用メモリ: 25,236 KB
• 最終ジャッジ日時: 2024-12-28 14:42:49
• 合計ジャッジ時間: 18,758 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
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	2 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	1 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	1 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	2 ms; 5,248 KB
testcase_12	AC	2 ms; 5,248 KB
testcase_13	AC	2 ms; 5,248 KB
testcase_14	AC	2 ms; 5,248 KB
testcase_15	AC	1 ms; 5,248 KB
testcase_16	AC	65 ms; 18,688 KB
testcase_17	AC	79 ms; 20,816 KB
testcase_18	AC	83 ms; 23,452 KB
testcase_19	AC	64 ms; 19,236 KB
testcase_20	AC	55 ms; 16,000 KB
testcase_21	AC	24 ms; 7,936 KB
testcase_22	AC	25 ms; 8,448 KB
testcase_23	AC	24 ms; 8,064 KB
testcase_24	AC	78 ms; 23,656 KB
testcase_25	AC	10 ms; 5,248 KB
testcase_26	AC	1 ms; 5,248 KB
testcase_27	AC	1 ms; 5,248 KB
testcase_28	AC	1 ms; 5,248 KB
testcase_29	AC	21 ms; 7,876 KB
testcase_30	AC	30 ms; 11,084 KB
testcase_31	AC	90 ms; 25,236 KB
testcase_32	AC	88 ms; 25,216 KB

ソースコード

use proconio::input;

type Mint = kekenx::ModInt<998244353>;

fn main() {
    input! {
    m: u64,
    n: usize,
    mut x: [u64; n],
    }

    x.push(m + 1);

    let mut prev = 0;
    let mut ans = Mint::new(0);
    let inv = Mint::new(6).inv();
    for i in x {
        let j = Mint::new(i - prev - 1);
        ans += j * (Mint::new(1) + j) * (Mint::new(2) * j + Mint::new(1)) * inv;
        prev = i;
    }

    println!("{ans}");
}

pub mod kekenx {
    use std::fmt;
    use std::{
        convert::{TryFrom, TryInto},
        iter::{Product, Sum},
        ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign},
    };

    #[derive(Eq, PartialEq, Clone, Copy, Hash)]
    pub struct ModInt<const M: u64>(u64);

    impl<const M: u64> ModInt<M> {
        pub fn new(val: u64) -> ModInt<M> {
            ModInt(val % M)
        }

        pub fn val(&self) -> u64 {
            self.0
        }

        pub fn pow(&self, mut e: u64) -> ModInt<M> {
            let mut r = ModInt::new(1);
            let mut x = *self;
            while e > 0 {
                if e % 2 == 1 {
                    r *= x;
                }
                x *= x;
                e >>= 1;
            }
            r
        }

        pub fn inv(&self) -> ModInt<M> {
            self.pow(M - 2)
        }
    }

    macro_rules! impl_from {
        ($t: ty) => {
            impl<const M: u64> From<$t> for ModInt<M> {
                fn from(from: $t) -> Self {
                    let mut x = from.into();
                    if x >= M {
                        x %= M;
                    }
                    Self(x)
                }
            }
        };
    }

    macro_rules! impl_try_from {
        ($t: ty) => {
            impl<const M: u64> TryFrom<$t> for ModInt<M> {
                type Error = ();
                fn try_from(from: $t) -> Result<Self, Self::Error> {
                    let mut x = from.try_into().unwrap();
                    if x >= M {
                        x %= M;
                    }
                    Ok(Self(x))
                }
            }
        };
    }

    // Signed to ModInt
    impl_try_from!(i16);
    impl_try_from!(i32);
    impl_try_from!(i64);

    // Unsigned to ModInt
    impl_from!(u8);
    impl_from!(u16);
    impl_from!(u32);

    impl<const M: u64> AddAssign for ModInt<M> {
        fn add_assign(&mut self, rhs: Self) {
            self.0 += rhs.0;
            if self.0 >= M {
                self.0 -= M;
            }
        }
    }

    impl<const M: u64> Add for ModInt<M> {
        type Output = Self;
        fn add(self, rhs: Self) -> Self::Output {
            let mut ret = self;
            ret += rhs;
            ret
        }
    }

    impl<const M: u64> SubAssign for ModInt<M> {
        fn sub_assign(&mut self, rhs: Self) {
            if rhs.0 > self.0 {
                self.0 += M;
            }
            self.0 -= rhs.0;
        }
    }

    impl<const M: u64> Sub for ModInt<M> {
        type Output = Self;
        fn sub(self, rhs: Self) -> Self::Output {
            let mut ret = self;
            ret -= rhs;
            ret
        }
    }

    impl<const M: u64> MulAssign for ModInt<M> {
        fn mul_assign(&mut self, rhs: Self) {
            self.0 *= rhs.0;
            if self.0 > M {
                self.0 %= M;
            }
        }
    }

    impl<const M: u64> Mul for ModInt<M> {
        type Output = Self;
        fn mul(self, rhs: Self) -> Self::Output {
            let mut ret = self;
            ret *= rhs;
            ret
        }
    }

    impl<const M: u64> DivAssign for ModInt<M> {
        fn div_assign(&mut self, rhs: Self) {
            self.mul_assign(rhs.inv());
        }
    }

    impl<const M: u64> Div for ModInt<M> {
        type Output = Self;
        fn div(self, rhs: Self) -> Self::Output {
            let mut ret = self;
            ret /= rhs;
            ret
        }
    }

    impl<const M: u64> fmt::Display for ModInt<M> {
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
            write!(f, "{}", self.0)
        }
    }

    impl<const M: u64> fmt::Debug for ModInt<M> {
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
            write!(f, "{{ModInt: {}, modulo: {}}}", self.0, M)
        }
    }

    impl<const M: u64> Default for ModInt<M> {
        fn default() -> Self {
            ModInt::new(0)
        }
    }

    impl<const M: u64> Product for ModInt<M> {
        fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(ModInt::<M>::new(1), |a, b| a * b)
        }
    }

    impl<const M: u64> Sum for ModInt<M> {
        fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(ModInt::<M>::new(0), |a, b| a + b)
        }
    }
}