結果
問題 |
No.3119 A Little Cheat
|
ユーザー |
|
提出日時 | 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
ソースコード
#![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)*)=>{}}