結果

問題 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
        }
    }
}
0