結果

問題 No.2734 Addition and Multiplication in yukicoder (Hard)
ユーザー CoCo_Japan_pan
提出日時 2024-04-19 22:56:12
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 532 ms / 5,000 ms
コード長 12,046 bytes
コンパイル時間 15,999 ms
コンパイル使用メモリ 377,972 KB
実行使用メモリ 10,112 KB
最終ジャッジ日時 2024-10-11 16:56:36
合計ジャッジ時間 25,823 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(non_snake_case)]
pub use __cargo_equip::prelude::*;
use proconio::marker::{Bytes, Chars, Isize1, Usize1};
use proconio::{input, input_interactive};
#[allow(unused_imports)]
use proconio_derive::fastout;
use static_modint::ModInt998244353;
use std::cmp::Reverse;
/*#[fastout]
fn main() {
input! {
N: usize,
mut A: [u128; N],
}
A.sort_by(|a, b| {
let a_len = a.to_string().len();
let b_len = b.to_string().len();
if a_len == b_len {
a.cmp(b)
} else {
let a_f = (10_u128).pow(b_len as u32) * a + b;
let b_f = (10_u128).pow(a_len as u32) * b + a;
a_f.cmp(&b_f)
}
});
let ans = A.iter().fold(ModInt998244353::new(0), |acc, &a| {
let digits = a.to_string().len();
acc * ModInt998244353::raw(10).pow(digits as u64) + ModInt998244353::new(a)
});
println!("{}", ans);
}*/
fn main() {
let __proconio_stdout = ::std::io::stdout();
let mut __proconio_stdout = ::std::io::BufWriter::new(__proconio_stdout.lock());
#[allow(unused_macros)]
macro_rules ! print { ($ ($ tt : tt) *) => { { use std :: io :: Write as _ ; :: std :: write ! (__proconio_stdout , $ ($ tt) *) . unwrap () ; } }
        ; }
#[allow(unused_macros)]
macro_rules ! println { ($ ($ tt : tt) *) => { { use std :: io :: Write as _ ; :: std :: writeln ! (__proconio_stdout , $ ($ tt) *) . unwrap () ;
        } } ; }
let __proconio_res = {
input! { N : usize , mut A : [u128 ; N] , }
A.sort_by(|a, b| {
let a_len = a.to_string().len();
let b_len = b.to_string().len();
if a_len == b_len {
a.cmp(b)
} else {
let a_f = (10_u128).pow(b_len as u32) * a + b;
let b_f = (10_u128).pow(a_len as u32) * b + a;
a_f.cmp(&b_f)
}
});
let ans = A.iter().fold(ModInt998244353::new(0), |acc, &a| {
let digits = a.to_string().len();
acc * ModInt998244353::raw(10).pow(digits as u64) + ModInt998244353::new(a)
});
println!("{}", ans);
};
<::std::io::BufWriter<::std::io::StdoutLock> as ::std::io::Write>::flush(
&mut __proconio_stdout,
)
.unwrap();
return __proconio_res;
}
#[macro_export]
macro_rules! mat {
($($e:expr),*) => { vec![$($e),*] };
($($e:expr,)*) => { vec![$($e),*] };
($e:expr; $d:expr) => { vec![$e; $d] };
($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] };
}
#[macro_export]
macro_rules! chmin {
($a:expr, $b:expr) => {
if $a > $b {
$a = $b;
true
} else {
false
}
};
}
#[macro_export]
macro_rules! chmax {
($a:expr, $b:expr) => {
if $a < $b {
$a = $b;
true
} else {
false
}
};
}
/// https://maguro.dev/debug-macro/
#[macro_export]
macro_rules! debug {
($($a:expr),* $(,)*) => {
#[cfg(debug_assertions)]
eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*);
};
}
// The following code was expanded by `cargo-equip`.
/// # Bundled libraries
///
/// - `internal_type_traits 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#1e1107f6f59acf7b7a31e3df7b8b28dff87722a2)` licensed
    under `CC0-1.0` as `crate::__cargo_equip::crates::__internal_type_traits_0_1_0`
/// - `modint_traits 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#1e1107f6f59acf7b7a31e3df7b8b28dff87722a2)` licensed
    under `CC0-1.0` as `crate::__cargo_equip::crates::__modint_traits_0_1_0`
/// - `static_modint 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#1e1107f6f59acf7b7a31e3df7b8b28dff87722a2)` licensed
    under `CC0-1.0` as `crate::__cargo_equip::crates::static_modint`
///
/// # Procedural macros
///
/// - `proconio-derive 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT OR Apache-2.0`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
pub(crate) mod crates {
pub mod __internal_type_traits_0_1_0 {use std::ops::{Add,AddAssign,Sub,SubAssign};pub trait Integral:Copy+Add<Output=Self>+AddAssign+Sub
            <Output=Self>+SubAssign+Ord+Zero+One+BoundedBelow+BoundedAbove{}pub trait Zero{fn zero()->Self;}pub trait One{fn one()->Self;}pub trait
            BoundedBelow{fn min_value()->Self;}pub trait BoundedAbove{fn max_value()->Self;}macro_rules!impl_integral{($($ty:ty),*)=>{$(impl Zero
            for$ty{#[inline]fn zero()->Self{0}}impl One for$ty{#[inline]fn one()->Self{1}}impl BoundedBelow for$ty{#[inline]fn min_value()->Self{Self
            ::MIN}}impl BoundedAbove for$ty{#[inline]fn max_value()->Self{Self::MAX}}impl Integral for$ty{})*};}impl_integral!(i8,i16,i32,i64,i128
            ,isize,u8,u16,u32,u64,u128,usize);}
pub mod __modint_traits_0_1_0 {use std::fmt::{Debug,Display};use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign};use
            std::str::FromStr;pub trait ModInt:Debug+Default+Clone+PartialEq+Eq+Display+Copy+Add<Output=Self>+Sub<Output=Self>+Mul<Output=Self>+Div
            <Output=Self>+AddAssign+SubAssign+MulAssign+DivAssign+Neg<Output=Self>+FromStr{fn new<T:RemEuclidU32>(x:T)->Self;fn raw(x:u32)->Self;fn
            value(&self)->u32;fn modulus()->u32;fn pow(&self,mut n:u64)->Self{let mut ret=Self::new(1);let mut base=*self;while n>0{if n&1==1{ret
            *=base;}base*=base;n>>=1;}ret}#[inline]fn inv(&self)->Self{let(g,x)=inv_gcd(self.value(),Self::modulus());assert_eq!(g,1);Self::raw(x
            )}}fn inv_gcd(a:u32,b:u32)->(u32,u32){assert!(a<b);if a==0{return(b,0);}let mut s=b;let mut t=a;let mut m0=0_i32;let mut m1=1_i32;while
            t!=0{let u=s/t;s-=t*u;m0-=m1*(u as i32);std::mem::swap(&mut s,&mut t);std::mem::swap(&mut m0,&mut m1);}if m0<0{m0+=(b/s)as i32;}(s,m0 as
            u32)}pub trait RemEuclidU32:Copy{fn rem_euclid_u32(self,modulus:u32)->u32;}impl RemEuclidU32 for u8{#[inline]fn rem_euclid_u32(self
            ,modulus:u32)->u32{self as u32%modulus}}impl RemEuclidU32 for u16{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self as
            u32%modulus}}impl RemEuclidU32 for u32{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self%modulus}}impl RemEuclidU32 for
            u64{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{(self%modulus as u64)as u32}}impl RemEuclidU32 for usize{#[inline]fn rem_euclid_u32
            (self,modulus:u32)->u32{let casted:u64=self.try_into().unwrap();casted.rem_euclid_u32(modulus)}}impl RemEuclidU32 for u128{#[inline]fn
            rem_euclid_u32(self,modulus:u32)->u32{(self%modulus as u128)as u32}}#[inline]fn neg(val:u32,modulus:u32)->u32{if val==0{0}else{modulus
            -val}}macro_rules!impl_rem_euclid_u32_for_signed{($($t:ty),*)=>{$(impl RemEuclidU32 for$t{#[inline]fn rem_euclid_u32(self,modulus:u32
            )->u32{if self<0{neg(self.unsigned_abs().rem_euclid_u32(modulus),modulus)}else{self.unsigned_abs().rem_euclid_u32(modulus)}}})*}
            ;}impl_rem_euclid_u32_for_signed!(i8,i16,i32,i64,isize,i128);}
pub mod proconio_derive {pub use crate::__cargo_equip::macros::proconio_derive
            ::*;#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_derive_derive_readable{($(_:tt)*)=>(::std::compile_error!
            ("`derive_readable` from `proconio-derive 0.2.1` should have been expanded"
            );)}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_derive_fastout{($(_:tt)*)=>(::std::compile_error!("`fastout` from
            `proconio-derive 0.2.1` should have been expanded");)}}
pub mod static_modint {use crate::__cargo_equip::preludes::static_modint::*;use internal_type_traits::{One,Zero};use modint_traits::{ModInt
            ,RemEuclidU32};use std::fmt::Display;use std::iter::{Product,Sum};use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub
            ,SubAssign};use std::str::FromStr;pub type ModInt998244353=StaticModInt<998244353>;pub type ModInt1000000007=StaticModInt<1000000007
            >;#[derive(Debug,Clone,Copy,PartialEq,Eq,Hash,Default)]pub struct StaticModInt<const MOD:u32>{value:u32,}impl<const MOD:u32>Zero for
            StaticModInt<MOD>{fn zero()->Self{Self::raw(0)}}impl<const MOD:u32>One for StaticModInt<MOD>{fn one()->Self{Self::new(1)}}impl<const MOD
            :u32>Display for StaticModInt<MOD>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.value)}}impl<const
            MOD:u32,T>Sum<T>for StaticModInt<MOD>where Self:Add<T,Output=Self>,{fn sum<I:Iterator<Item=T>>(iter:I)->Self{iter.fold(Self::raw(0),Add
            ::add)}}impl<const MOD:u32,T>Product<T>for StaticModInt<MOD>where Self:Mul<T,Output=Self>,{fn product<I:Iterator<Item=T>>(iter:I
            )->Self{iter.fold(Self::new(1),Mul::mul)}}impl<const MOD:u32>FromStr for StaticModInt<MOD>{type Err=<i64 as FromStr>::Err;fn from_str(s
            :&str)->Result<Self,Self::Err>{i64::from_str(s).map(Self::new)}}impl<const MOD:u32>StaticModInt<MOD>{#[inline]pub fn value(&self
            )->u32{self.value}#[inline]pub fn modulus()->u32{MOD}#[inline]pub fn new<T:RemEuclidU32>(x:T)->Self{ModInt::new(x)}#[inline]pub fn raw(x
            :u32)->Self{Self{value:x}}#[inline]pub fn pow(&self,n:u64)->Self{ModInt::pow(self,n)}#[inline]pub fn inv(&self)->Self{ModInt::inv(self
            )}}impl<const MOD:u32>ModInt for StaticModInt<MOD>{#[inline]fn value(&self)->u32{self.value}#[inline]fn modulus()->u32{MOD}#[inline]fn
            raw(x:u32)->Self{Self{value:x}}#[inline]fn new<T:RemEuclidU32>(x:T)->Self{Self{value:x.rem_euclid_u32(MOD),}}}impl<const MOD:u32>Neg for
            StaticModInt<MOD>{type Output=Self;#[inline]fn neg(self)->Self{if self.value==0{Self{value:0}}else{Self{value:MOD-self.value,}}}}impl
            <const MOD:u32,T>Add<T>for StaticModInt<MOD>where Self:AddAssign<T>,{type Output=Self;fn add(mut self,rhs:T)->Self{self+=rhs;self}}impl
            <const MOD:u32>AddAssign for StaticModInt<MOD>{fn add_assign(&mut self,rhs:Self){self.value+=rhs.value;if self.value>=MOD{self.value-=MOD
            ;}}}impl<const MOD:u32,T:RemEuclidU32>AddAssign<T>for StaticModInt<MOD>{fn add_assign(&mut self,rhs:T){*self+=Self::new(rhs);}}impl<const
            MOD:u32,T>Sub<T>for StaticModInt<MOD>where Self:SubAssign<T>,{type Output=Self;fn sub(mut self,rhs:T)->Self{self-=rhs;self}}impl<const
            MOD:u32>SubAssign for StaticModInt<MOD>{fn sub_assign(&mut self,rhs:Self){if self.value<rhs.value{self.value+=MOD;}self.value-=rhs.value
            ;}}impl<const MOD:u32,T:RemEuclidU32>SubAssign<T>for StaticModInt<MOD>{fn sub_assign(&mut self,rhs:T){*self-=Self::new(rhs);}}impl<const
            MOD:u32,T>Mul<T>for StaticModInt<MOD>where Self:MulAssign<T>,{type Output=Self;fn mul(mut self,rhs:T)->Self{self*=rhs;self}}impl<const
            MOD:u32>MulAssign for StaticModInt<MOD>{fn mul_assign(&mut self,rhs:Self){self.value=(self.value as u64*rhs.value as u64).rem_euclid_u32
            (MOD);}}impl<const MOD:u32,T:RemEuclidU32>MulAssign<T>for StaticModInt<MOD>{fn mul_assign(&mut self,rhs:T){*self*=Self::new(rhs);}}impl
            <const MOD:u32,T>Div<T>for StaticModInt<MOD>where Self:DivAssign<T>,{type Output=Self;fn div(mut self,rhs:T)->Self{self/=rhs
            ;self}}#[allow(clippy::suspicious_op_assign_impl)]impl<const MOD:u32>DivAssign for StaticModInt<MOD>{fn div_assign(&mut self,rhs:Self){
            *self*=rhs.inv();}}impl<const MOD:u32,T:RemEuclidU32>DivAssign<T>for StaticModInt<MOD>{fn div_assign(&mut self,rhs:T){*self/=Self::new
            (rhs);}}macro_rules!impl_from_primitive{($($t:ty),*)=>{$(impl<const MOD:u32>From<$t>for StaticModInt<MOD>{fn from(x:$t)->Self{Self::new(x
            )}})*};}impl_from_primitive!(u8,u16,u32,u64,usize,u128,i8,i16,i32,i64,isize,i128);}
}
pub(crate) mod macros {
pub mod __internal_type_traits_0_1_0 {}
pub mod __modint_traits_0_1_0 {}
pub mod proconio_derive {pub use crate::{__cargo_equip_macro_def_proconio_derive_derive_readable as derive_readable
            ,__cargo_equip_macro_def_proconio_derive_fastout as fastout};}
pub mod static_modint {}
}
pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
mod preludes {
pub mod __internal_type_traits_0_1_0 {}
pub mod __modint_traits_0_1_0 {}
pub mod proconio_derive {}
pub mod static_modint {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__internal_type_traits_0_1_0 as internal_type_traits
            ,__modint_traits_0_1_0 as modint_traits};}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0