結果

問題 No.3119 A Little Cheat
コンテスト
ユーザー rhoo
提出日時 2025-04-19 10:25:03
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 115 ms / 2,000 ms
コード長 11,774 bytes
コンパイル時間 13,505 ms
コンパイル使用メモリ 402,380 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-04-19 10:25:26
合計ジャッジ時間 19,727 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unexpected `cfg` condition value: `local`
   --> src/main.rs:472:7
    |
472 | #[cfg(feature = "local")]
    |       ^^^^^^^^^^^^^^^^^ help: remove the condition
    |
    = note: no expected values for `feature`
    = help: consider adding `local` as a feature in `Cargo.toml`
    = note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration
    = note: `#[warn(unexpected_cfgs)]` on by default

warning: unexpected `cfg` condition value: `local`
   --> src/main.rs:474:11
    |
474 | #[cfg(not(feature = "local"))]
    |           ^^^^^^^^^^^^^^^^^ help: remove the condition
    |
    = note: no expected values for `feature`
    = help: consider adding `local` as a feature in `Cargo.toml`
    = note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration

ソースコード

diff # 

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


#[fastout]
fn main(){
    input!{
        n:usize,
        m:usize,
        a:[usize;n],
    }

    let M=|a|M::new(a);

    let mut ans=M(0);
    let get=|a:&[(usize,usize)]|->M{
        let mut min=0;
        let mut max=m;

        // min < x <= max

        for &(x,t) in a{
            if t==0{
                max=max.min(x);
            } else{
                min=min.max(x);
            }
        }

        M(max.saturating_sub(min))
    };

    let mut dp=[[M(0);2];2];
    for i in 0..2{
        for j in 0..2{
            dp[i][j]=get(&[(a[0],i),(a[1],j)]);
        }
    }

    // let mut adds=vec![M(0);n];
    for i in 1..n{
        let mut new=[[M(0);2];2];

        for j0 in 0..2{
            for j1 in 0..2{
                for k0 in 0..2{
                    for k1 in 0..2{
                        let sum=j0+j1+k0+k1;
                        let mut any=false;
                        if sum==1{
                            if j1==1 || k0==1{
                                any=true;
                            }
                        } else if sum==3{
                            if j0==0 || k1==0{
                                any=true;
                            }
                        }
                        
                        if any{
                            ans+=dp[j0][j1]*get(&[
                                (a[i-1],k0),
                                (a[i],k1),
                            ])*M(m).pow(n as u64-i as u64-1);
                            // adds[i]+=dp[j0][j1]*get(&[
                            //     (a[i-1],k0),
                            //     (a[i],k1),
                            // ])*M(m).pow(n as u64-i as u64-1);
                        } else{
                            if i+1!=n{
                                for l in 0..2{
                                    new[k1][l]+=dp[j0][j1]*get(&[
                                        (a[i-1],k0),
                                        (a[i],k1),
                                        (a[i+1],l),
                                    ]);
                                }
                            }
                        }
                    }
                }
            }
        }

        dp=new;
    }

    // brute_force(n,m,&a);
    // eprintln!("{:?}",adds);

    let pow=M(m).pow(n as u64-1);
    for i in 0..n{
        ans+=pow*get(&[(a[i],1)]);
    }

    println!("{ans}");
}




fn brute_force(n:usize,m:usize,a:&[usize]){
    fn rec(m:usize,i:usize,a:&[usize],res:&mut [usize],ans:&mut [usize]){
        if i==a.len(){
            for i in 1..a.len(){
                let old=(a[i-1]<res[i-1]) as usize+(a[i]<res[i]) as usize;
                let new=(a[i-1]<res[i]) as usize+(a[i]<res[i-1]) as usize;

                if old<new{
                    assert!(old+1==new);
                    if i==2{
                        eprintln!("{:?}",res);
                    }
                    ans[i]+=1;
                    break;
                }
            }
            return;
        }
        
        for x in 1..=m{
            res[i]=x;
            rec(m,i+1,a,res,ans);
        }
    }

    let mut ans=vec![0;n];
    rec(m,0,a,&mut vec![!0;n],&mut ans);
    eprintln!("verify = {:?}",ans);
}



type M = StaticModInt<998244353>;
type ModInt1000000007 = StaticModInt<1000000007>;



#[derive(Clone, Copy, PartialEq, Eq, Default, Hash)]
struct StaticModInt<const MODULO: u32> {
    val: u32,
}

impl<const MODULO: u32> ModIntBase for StaticModInt<MODULO> {
    fn modulus() -> u32 {
        MODULO
    }
    unsafe fn raw(val: u32) -> Self {
        StaticModInt { 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, MODULO);
        unsafe { Self::raw(inv_val) }
    }
}



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

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


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

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



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

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

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

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



impl<const MODULO: u32> std::ops::AddAssign for StaticModInt<MODULO> {
    fn add_assign(&mut self, rhs: Self) {
        *self = *self + rhs;
    }
}

impl<const MODULO: u32> std::ops::SubAssign for StaticModInt<MODULO> {
    fn sub_assign(&mut self, rhs: Self) {
        *self = *self - rhs;
    }
}

impl<const MODULO: u32> std::ops::MulAssign for StaticModInt<MODULO> {
    fn mul_assign(&mut self, rhs: Self) {
        *self = *self * rhs;
    }
}

impl<const MODULO: u32> std::ops::DivAssign for StaticModInt<MODULO> {
    fn div_assign(&mut self, rhs: Self) {
        *self = *self / rhs;
    }
}



impl<const MODULO: u32> std::ops::Neg for StaticModInt<MODULO> {
    type Output = Self;
    fn neg(self) -> Self::Output {
        if self.val == 0 {
            self
        } else {
            unsafe { Self::raw(MODULO - self.val) }
        }
    }
}



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



macro_rules! impl_mod_int_ops_sub {
    ($trait:ident, $func:ident, $assign_trait:ident, $assign_func:ident, $op:tt, ($($t:ty),*)) => {
        $(
            impl<const MODULO: u32> std::ops::$trait<$t> for StaticModInt<MODULO> {
                type Output = Self;
                fn $func(self, rhs: $t) -> Self::Output {
                    self $op StaticModInt::new(rhs)
                }
            }
            impl<const MODULO: u32> std::ops::$trait<StaticModInt<MODULO>> for $t {
                type Output = StaticModInt<MODULO>;
                fn $func(self, rhs: StaticModInt<MODULO>) -> Self::Output {
                    StaticModInt::new(self) $op rhs
                }
            }
            impl<const MODULO: u32> std::ops::$assign_trait<$t> for StaticModInt<MODULO> {
                fn $assign_func(&mut self, rhs: $t) {
                    *self = *self $op StaticModInt::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<const MODULO: u32> std::iter::Sum for StaticModInt<MODULO> {
    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
        iter.fold(StaticModInt::zero(), |acc, x| acc + x)
    }
}

impl<const MODULO: u32> std::iter::Product for StaticModInt<MODULO> {
    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
        iter.fold(StaticModInt::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
}



#[cfg(feature = "local")]
include!("../../.rs");
#[cfg(not(feature = "local"))]
#[macro_export]macro_rules! debug{($($t:tt)*)=>{}}
0