結果
| 問題 |
No.3364 Push_back Operation
|
| コンテスト | |
| ユーザー |
 magurofly
|
| 提出日時 | 2025-11-17 22:08:40 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 123 ms / 2,000 ms |
| コード長 | 9,622 bytes |
| コンパイル時間 | 11,746 ms |
| コンパイル使用メモリ | 400,528 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2025-11-17 22:08:58 |
| 合計ジャッジ時間 | 16,058 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 53 |
ソースコード
#![allow(dead_code, unused_imports, unused_macros, non_snake_case)]
pub use __cargo_equip::prelude::*;
fn main() {
input! {
N: i64,
}
// ans = (1 ..= N).map(|L| (N / L).pow(L) ).sum()
// L <= sqrt(N) のときは L で考える
// L > sqrt(N) のときは N/L で考える
let sqrt_N = (N as f64).sqrt().ceil() as i64;
// eprintln!("sqrt({N}) = {sqrt_N}");
let mut ans = 0;
let mut prev_L = 0;
for L in 1..=sqrt_N {
ans = (ans + pow(N / L % MOD, L)) % MOD;
prev_L = L;
}
for N_L in (1..=N / prev_L).rev() {
let min_L = ((N / (N_L + 1)) + 1).max(prev_L + 1);
let max_L = N / N_L;
if max_L < min_L {
continue;
}
let sum = if N_L == 1 {
(max_L - min_L + 1) % MOD
} else {
let a0 = pow(N_L, min_L);
a0 * (pow(N_L % MOD, max_L - min_L + 1) + MOD - 1) % MOD * pow((N_L - 1) % MOD, MOD - 2)
% MOD
};
// eprintln!("N_L={N_L}: {sum}");
ans = (ans + sum) % MOD;
prev_L = max_L;
}
say(ans.rem_euclid(MOD));
}
fn pow(mut a: i64, mut b: i64) -> i64 {
let mut r = 1;
while b > 0 {
if b & 1 != 0 {
r = (r * a) % MOD;
}
a = a * a % MOD;
b >>= 1;
}
r
}
type Int = i64;
const MOD: Int = 998244353;
// const MOD: Int = 1_000_000_007;
const INF: Int = 1_000_000_000_000_000_000;
const YESNO: [&'static str; 2] = ["Yes", "No"];
use cmp::{self, Reverse};
use collections::*; // (BTree|Hash)(Set|Map), BinaryHeap, VecDeque, LinkedList
use proconio::{
input,
marker::{Bytes, Chars, Usize1},
};
use std::ops::*;
use std::*; // cmp::{min, max}
fn yes() {
println!("{}", YESNO[0]);
}
fn no() {
println!("{}", YESNO[1]);
}
fn yesno(c: bool) {
println!("{}", if c { YESNO[0] } else { YESNO[1] });
}
fn say<T: std::fmt::Display>(x: T) -> T {
println!("{}", x);
x
}
fn neighbor4<F: FnMut(usize, usize)>(i: usize, j: usize, h: usize, w: usize, mut f: F) {
if i > 0 {
(f)(i - 1, j);
}
if i < h - 1 {
(f)(i + 1, j);
}
if j > 0 {
(f)(i, j - 1);
}
if j < w - 1 {
(f)(i, j + 1);
}
}
trait MyItertools: Iterator + Sized {
fn to_vec(self) -> Vec<Self::Item> {
self.collect::<Vec<_>>()
}
fn to_vec_rev(self) -> Vec<Self::Item> {
let mut v = self.collect::<Vec<_>>();
v.reverse();
v
}
fn tally(self) -> HashMap<Self::Item, usize>
where
Self::Item: Copy + Eq + hash::Hash,
{
let mut counts = HashMap::new();
self.for_each(|item| *counts.entry(item).or_default() += 1);
counts
}
fn count_if<P: Fn(Self::Item) -> bool>(self, predicate: P) -> usize {
self.map(predicate).filter(|&x| x).count()
}
fn implode(self, sep: &str) -> String
where
Self::Item: std::string::ToString,
{
self.map(|x| x.to_string()).to_vec().join(sep)
}
fn mex(self, gen: impl IntoIterator<Item = Self::Item>) -> Self::Item
where
Self::Item: Ord,
{
let mut v = self.collect::<Vec<_>>();
v.sort();
v.dedup();
let mut it = v.into_iter();
gen.into_iter()
.find(|a| {
if let Some(x) = it.next() {
a != &x
} else {
true
}
})
.unwrap()
}
}
impl<T: ?Sized> MyItertools for T where T: Iterator + Sized {}
trait MyOrd: PartialOrd + Sized {
fn chmax(&mut self, mut rhs: Self) -> bool {
if self < &mut rhs {
*self = rhs;
true
} else {
false
}
}
fn chmin(&mut self, mut rhs: Self) -> bool {
if self > &mut rhs {
*self = rhs;
true
} else {
false
}
}
}
impl<T: Sized + PartialOrd> MyOrd for T {}
// The following code was expanded by `cargo-equip`.
/// # Bundled libraries
///
/// - `permutohedron 0.2.4 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT/Apache-2.0` as `crate::__cargo_equip::crates::permutohedron`
///
/// # License and Copyright Notices
///
/// - `permutohedron 0.2.4 (registry+https://github.com/rust-lang/crates.io-index)`
///
/// ```text
/// Copyright (c) 2015-2017 Ulrik Sverdrup "bluss"
///
/// Permission is hereby granted, free of charge, to any
/// person obtaining a copy of this software and associated
/// documentation files (the "Software"), to deal in the
/// Software without restriction, including without
/// limitation the rights to use, copy, modify, merge,
/// publish, distribute, sublicense, and/or sell copies of
/// the Software, and to permit persons to whom the Software
/// is furnished to do so, subject to the following
/// conditions:
///
/// The above copyright notice and this permission notice
/// shall be included in all copies or substantial portions
/// of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
/// ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
/// TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
/// PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
/// SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
/// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
/// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
/// IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
/// DEALINGS IN THE SOFTWARE.
/// ```
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
pub(crate) mod crates {
pub mod permutohedron {use std::marker::PhantomData;pub use lexical::LexicalPermutation;mod lexical{pub trait LexicalPermutation{fn next_permutation(&mut self)->bool;fn prev_permutation(&mut self)->bool;}impl<T>LexicalPermutation for[T]where T:Ord{fn next_permutation(&mut self)->bool{if self.len()<2{return false;}let mut i=self.len()-1;while i>0&&self[i-1]>=self[i]{i-=1;}if i==0{return false;}let mut j=self.len()-1;while j>=i&&self[j]<=self[i-1]{j-=1;}self.swap(j,i-1);self[i..].reverse();true}fn prev_permutation(&mut self)->bool{if self.len()<2{return false;}let mut i=self.len()-1;while i>0&&self[i-1]<=self[i]{i-=1;}if i==0{return false;}self[i..].reverse();let mut j=self.len()-1;while j>=i&&self[j-1]<self[i-1]{j-=1;}self.swap(i-1,j);true}}#[test]fn lexical(){let mut data=[1,2,3];data.next_permutation();assert_eq!(&data,&[1,3,2]);data.next_permutation();assert_eq!(&data,&[2,1,3]);data.prev_permutation();assert_eq!(&data,&[1,3,2]);data.prev_permutation();assert_eq!(&data,&[1,2,3]);assert!(!data.prev_permutation());let mut c=0;while data.next_permutation(){c+=1;}assert_eq!(c,5);}}#[macro_use]pub mod control{macro_rules!try_control{($e:expr)=>{match$e{x=>if x.should_break(){return x;}}}}#[derive(Copy,Clone,Debug)]pub enum Control<B>{Continue,Break(B),}impl<B>Control<B>{pub fn breaking()->Control<()>{Control::Break(())}pub fn break_value(self)->Option<B>{match self{Control::Continue=>None,Control::Break(b)=>Some(b),}}}pub trait ControlFlow{fn continuing()->Self;#[inline]fn should_break(&self)->bool{false}}impl ControlFlow for(){fn continuing(){}}impl<B>ControlFlow for Control<B>{fn continuing()->Self{Control::Continue}fn should_break(&self)->bool{if let Control::Break(_)=*self{true}else{false}}}impl<E>ControlFlow for Result<(),E>{fn continuing()->Self{Ok(())}fn should_break(&self)->bool{if let Err(_)=*self{true}else{false}}}}use control::ControlFlow;pub fn heap_recursive<T,F,C>(xs:&mut[T],mut f:F)->C where F:FnMut(&mut[T])->C,C:ControlFlow,{match xs.len(){0|1=>f(xs),2=>{try_control!(f(xs));xs.swap(0,1);f(xs)}n=>heap_unrolled_(n,xs,&mut f),}}fn heap_unrolled_<T,F,C>(n:usize,xs:&mut[T],f:&mut F)->C where F:FnMut(&mut[T])->C,C:ControlFlow,{debug_assert!(n>=3);match n{3=>{try_control!(f(xs));xs.swap(0,1);try_control!(f(xs));xs.swap(0,2);try_control!(f(xs));xs.swap(0,1);try_control!(f(xs));xs.swap(0,2);try_control!(f(xs));xs.swap(0,1);f(xs)}n=>{for i in 0..n-1{try_control!(heap_unrolled_(n-1,xs,f));let j=if n%2==0{i}else{0};xs.swap(j,n-1);}heap_unrolled_(n-1,xs,f)}}}pub const MAXHEAP:usize=16;#[repr(C)]pub struct Heap<'a,Data:'a+?Sized,T:'a>{data:&'a mut Data,n:u32,c:[u8;MAXHEAP-1],_element:PhantomData<&'a mut T>}impl<'a,T,Data:?Sized>Heap<'a,Data,T>where Data:AsMut<[T]>{pub fn new(data:&'a mut Data)->Self{assert!(data.as_mut().len()<=MAXHEAP);Heap{data:data,c:[0;MAXHEAP-1],n:!0,_element:PhantomData,}}pub fn get(&self)->&Data{self.data}pub fn get_mut(&mut self)->&mut Data{self.data}pub fn reset(&mut self){self.n=!0;for c in&mut self.c[..]{*c=0;}}pub fn next_permutation(&mut self)->Option<&mut Data>{if self.n==!0{self.n=0;Some(self.data)}else{while 1+(self.n as usize)<self.data.as_mut().len(){let n=self.n as u8;let nu=self.n as usize;let c=&mut self.c;if c[nu]<=n{let j=if nu%2==0{c[nu]as usize}else{0};self.data.as_mut().swap(j,nu+1);c[nu]+=1;self.n=0;return Some(self.data);}else{c[nu]=0;self.n+=1;}}None}}}impl<'a,Data:?Sized,T>Iterator for Heap<'a,Data,T>where Data:AsMut<[T]>+ToOwned,{type Item=Data::Owned;fn next(&mut self)->Option<Self::Item>{match self.next_permutation(){None=>None,Some(perm)=>Some(perm.to_owned()),}}}pub fn factorial(n:usize)->usize{(1..n+1).fold(1,|a,b|a*b)}}
}
pub(crate) mod macros {
pub mod permutohedron {}
}
pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
mod preludes {
pub mod permutohedron {}
}
}