結果

問題 No.2903 A Round-the-World Trip with the Tent
ユーザー Esu0
提出日時 2024-09-27 21:25:21
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 36 ms / 2,000 ms
コード長 7,043 bytes
コンパイル時間 14,488 ms
コンパイル使用メモリ 378,248 KB
実行使用メモリ 6,812 KB
最終ジャッジ日時 2024-09-27 21:25:49
合計ジャッジ時間 13,901 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

pub use __cargo_equip::prelude::*;

use proconio::input;
use util::ModInt;
type MInt = ModInt<998244353>;

fn main() {
    input! {
        k: u64,
        n: usize,
    }
    let mut dp = vec![MInt::new(0); n + 1];
    if k == 1 {
        let mut p = MInt::new(2);
        for dpi in dp[1..].iter_mut() {
            *dpi = p;
            p *= MInt::new(2);
        }
    } else {
        let mut p = MInt::new(2);
        for dpi in dp[1..].iter_mut() {
            *dpi = p + MInt::new(1);
            p *= MInt::new(2);
        }
    }
    for i in 1..=n {
        let dpi = dp[i];
        let mut j = i * 2;
        while j <= n {
            let tmp = dp[j] - dpi;
            dp[j] = tmp;
            j += i;
        }
    }
    println!("{}", dp[n]);
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `git+https://github.com/Esu0/mylib-rust.git#util@0.1.0` licensed under **missing** as `crate::__cargo_equip::crates::util`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod util {pub mod algorithm{use std::{iter::FusedIterator,ops::{Add,Div,Mul,RangeBounds,Rem,Sub},};pub trait Integer:Sized+Add<Output=Self>+Sub<Output=Self>+Mul<Output=Self>+Div<Output=Self>+Rem<Output=Self>+Ord+Copy{const MIN:Self;const MAX:Self;const ZERO:Self;const ONE:Self;const TWO:Self;}macro_rules!impl_integer{($($t:ty),*)=>{$(impl Integer for$t{const MIN:Self=<$t>::MIN;const MAX:Self=<$t>::MAX;const ZERO:Self=0;const ONE:Self=1;const TWO:Self=2;})*};}impl_integer!(i8,i16,i32,i64,i128,isize);impl_integer!(u8,u16,u32,u64,u128,usize);pub fn upper_bound<T:Integer>(range:impl RangeBounds<T>,mut f:impl FnMut(T)->bool)->T{let mut l=match range.start_bound(){std::ops::Bound::Included(&l)=>l,std::ops::Bound::Excluded(&l)=>l+T::ONE,std::ops::Bound::Unbounded=>T::MIN/T::TWO,};let mut r=match range.end_bound(){std::ops::Bound::Included(&r)=>r+T::ONE,std::ops::Bound::Excluded(&r)=>r,std::ops::Bound::Unbounded=>T::MAX/T::TWO,};while r-l>T::ONE{let m=l+(r-l)/T::TWO;if f(m){l=m+T::ONE;}else{r=m;}}if f(l){l+T::ONE}else{l}}pub fn lower_bound<T:Integer>(range:impl RangeBounds<T>,mut f:impl FnMut(T)->bool)->T{upper_bound(range,|x|!f(x))}pub trait IteratorExt:Iterator{fn cumulative_sum<T,F>(self,init:T,f:F)->CumSum<Self,T,F>where Self:Sized,F:FnMut(&T,Self::Item)->T,{CumSum{iter:self,sum:Some(init),f,}}}impl<I:Iterator>IteratorExt for I{}pub struct CumSum<I,T,F>{iter:I,sum:Option<T>,f:F,}impl<I,T,F>Iterator for CumSum<I,T,F>where I:Iterator,F:FnMut(&T,I::Item)->T,{type Item=T;fn next(&mut self)->Option<Self::Item>{if let Some(sum)=self.sum.as_mut(){if let Some(next)=self.iter.next(){let next_sum=(self.f)(sum,next);Some(std::mem::replace(sum,next_sum))}else{self.sum.take()}}else{None}}fn size_hint(&self)->(usize,Option<usize>){let(lower,upper)=self.iter.size_hint();(lower+1,upper.map(|x|x+1))}}impl<I,T,F>ExactSizeIterator for CumSum<I,T,F>where I:ExactSizeIterator,F:FnMut(&T,I::Item)->T,{fn len(&self)->usize{self.iter.len()+1}}impl<I,T,F>FusedIterator for CumSum<I,T,F>where I:Iterator,F:FnMut(&T,I::Item)->T,{}}pub mod modulo{use std::{fmt::{self,Display},ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Sub,SubAssign},};#[derive(Debug,Clone,Copy,PartialEq,Eq,Default,PartialOrd,Ord,Hash)]pub struct ModInt<const MOD:u32>(u32);const fn check_primary<const M:u32>()->bool{match M{0=>false,1=>false,2=>true,_=>{if M%2==0{return false;}let mut i=3;while i*i<=M{if M%i==0{return false;}i+=2;}true}}}impl<const MOD:u32>ModInt<MOD>{const MOD_IS_PRIME:bool=check_primary::<MOD>();pub const fn new(x:i64)->Self{Self(x.rem_euclid(MOD as i64)as u32)}pub const fn get(self)->u32{self.0}pub const fn add_const(self,rhs:Self)->Self{let sum=self.0 as u64+rhs.0 as u64;if sum>=MOD as u64{Self((sum-MOD as u64)as u32)}else{Self(sum as u32)}}pub const fn sub_const(self,rhs:Self)->Self{let diff=self.0 as u64+MOD as u64-rhs.0 as u64;if diff>=MOD as u64{Self((diff-MOD as u64)as u32)}else{Self(diff as u32)}}pub const fn mul_const(self,rhs:Self)->Self{Self((self.0 as u64*rhs.0 as u64%MOD as u64)as u32)}pub const fn pow(self,mut exp:u32)->Self{let mut result=Self(1);let mut base=self;while exp>0{if exp&1==1{result=result.mul_const(base);}base=base.mul_const(base);exp>>=1;}result}pub const fn inv(self)->Self{if!Self::MOD_IS_PRIME{panic!("Cannot calculate the inverse of a number in a non-prime modulo.");}self.pow(MOD-2)}}impl<const MOD:u32>Add for ModInt<MOD>{type Output=Self;fn add(self,rhs:Self)->Self::Output{self.add_const(rhs)}}impl<const MOD:u32>Add<u32>for ModInt<MOD>{type Output=Self;fn add(self,rhs:u32)->Self::Output{self.add_const(Self(rhs%MOD))}}impl<const MOD:u32>Add<u64>for ModInt<MOD>{type Output=Self;fn add(self,rhs:u64)->Self::Output{self.add_const(Self((rhs%MOD as u64)as u32))}}impl<const MOD:u32>AddAssign for ModInt<MOD>{fn add_assign(&mut self,rhs:Self){*self=*self+rhs;}}impl<const MOD:u32>AddAssign<u32>for ModInt<MOD>{fn add_assign(&mut self,rhs:u32){*self=*self+rhs;}}impl<const MOD:u32>AddAssign<u64>for ModInt<MOD>{fn add_assign(&mut self,rhs:u64){*self=*self+rhs;}}impl<const MOD:u32>Sub for ModInt<MOD>{type Output=Self;fn sub(self,rhs:Self)->Self::Output{self.sub_const(rhs)}}impl<const MOD:u32>Sub<u32>for ModInt<MOD>{type Output=Self;fn sub(self,rhs:u32)->Self::Output{self.sub_const(Self(rhs%MOD))}}impl<const MOD:u32>Sub<u64>for ModInt<MOD>{type Output=Self;fn sub(self,rhs:u64)->Self::Output{self.sub_const(Self((rhs%MOD as u64)as u32))}}impl<const MOD:u32>SubAssign for ModInt<MOD>{fn sub_assign(&mut self,rhs:Self){*self=*self-rhs;}}impl<const MOD:u32>SubAssign<u32>for ModInt<MOD>{fn sub_assign(&mut self,rhs:u32){*self=*self-rhs;}}impl<const MOD:u32>SubAssign<u64>for ModInt<MOD>{fn sub_assign(&mut self,rhs:u64){*self=*self-rhs;}}impl<const MOD:u32>Mul for ModInt<MOD>{type Output=Self;fn mul(self,rhs:Self)->Self::Output{self.mul_const(rhs)}}impl<const MOD:u32>Mul<u32>for ModInt<MOD>{type Output=Self;fn mul(self,rhs:u32)->Self::Output{Self((self.0 as u64*rhs as u64%MOD as u64)as u32)}}impl<const MOD:u32>Mul<u64>for ModInt<MOD>{type Output=Self;fn mul(self,rhs:u64)->Self::Output{Self((self.0 as u64*(rhs%MOD as u64)%MOD as u64)as u32)}}impl<const MOD:u32>MulAssign for ModInt<MOD>{fn mul_assign(&mut self,rhs:Self){*self=*self*rhs;}}impl<const MOD:u32>MulAssign<u32>for ModInt<MOD>{fn mul_assign(&mut self,rhs:u32){*self=*self*rhs;}}impl<const MOD:u32>MulAssign<u64>for ModInt<MOD>{fn mul_assign(&mut self,rhs:u64){*self=*self*rhs;}}impl<const MOD:u32>Div for ModInt<MOD>{type Output=Self;fn div(self,rhs:Self)->Self::Output{self.mul_const(rhs.inv())}}impl<const MOD:u32>DivAssign for ModInt<MOD>{fn div_assign(&mut self,rhs:Self){*self=*self/rhs;}}impl<const MOD:u32>Display for ModInt<MOD>{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{write!(f,"{}",self.0)}}}pub use modulo::*;pub use algorithm::*;}
    }

    pub(crate) mod macros {
        pub mod util {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod util {}
    }
}
0