結果
問題 | No.1889 K Consecutive Ks (Hard) |
ユーザー | akakimidori |
提出日時 | 2022-03-20 19:37:04 |
言語 | Rust (1.72.1) |
結果 |
AC
|
実行時間 | 775 ms / 6,000 ms |
コード長 | 15,584 bytes |
コンパイル時間 | 1,752 ms |
コンパイル使用メモリ | 163,872 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2023-07-29 05:15:16 |
合計ジャッジ時間 | 13,537 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 772 ms
11,136 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 2 ms
4,384 KB |
testcase_09 | AC | 764 ms
10,996 KB |
testcase_10 | AC | 769 ms
11,092 KB |
testcase_11 | AC | 165 ms
4,380 KB |
testcase_12 | AC | 353 ms
6,500 KB |
testcase_13 | AC | 184 ms
4,604 KB |
testcase_14 | AC | 356 ms
6,580 KB |
testcase_15 | AC | 396 ms
7,104 KB |
testcase_16 | AC | 772 ms
11,020 KB |
testcase_17 | AC | 170 ms
4,380 KB |
testcase_18 | AC | 767 ms
10,804 KB |
testcase_19 | AC | 771 ms
11,012 KB |
testcase_20 | AC | 773 ms
11,084 KB |
testcase_21 | AC | 774 ms
11,112 KB |
testcase_22 | AC | 772 ms
11,084 KB |
testcase_23 | AC | 373 ms
6,944 KB |
testcase_24 | AC | 775 ms
11,056 KB |
ソースコード
// ---------- begin ModInt ---------- mod modint { use std::marker::*; use std::ops::*; pub trait Modulo { fn modulo() -> u32; fn rem() -> u32; fn ini() -> u64; fn reduce(x: u64) -> u32 { debug_assert!(x < (Self::modulo() as u64) << 32); let b = (x as u32 * Self::rem()) as u64; let t = x + b * Self::modulo() as u64; let mut c = (t >> 32) as u32; if c >= Self::modulo() { c -= Self::modulo(); } c as u32 } } #[allow(dead_code)] pub enum Mod998_244_353 {} impl Modulo for Mod998_244_353 { fn modulo() -> u32 { 998_244_353 } fn rem() -> u32 { 998244351 } fn ini() -> u64 { 932051910 } } pub struct ModInt<T>(u32, PhantomData<T>); impl<T> Clone for ModInt<T> { fn clone(&self) -> Self { ModInt::build(self.0) } } impl<T> Copy for ModInt<T> {} impl<T: Modulo> Add for ModInt<T> { type Output = ModInt<T>; fn add(self, rhs: Self) -> Self::Output { let mut d = self.0 + rhs.0; if d >= T::modulo() { d -= T::modulo(); } Self::build(d) } } impl<T: Modulo> AddAssign for ModInt<T> { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl<T: Modulo> Sub for ModInt<T> { type Output = ModInt<T>; fn sub(self, rhs: Self) -> Self::Output { let mut d = self.0 - rhs.0; if self.0 < rhs.0 { d += T::modulo(); } Self::build(d) } } impl<T: Modulo> SubAssign for ModInt<T> { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl<T: Modulo> Mul for ModInt<T> { type Output = ModInt<T>; fn mul(self, rhs: Self) -> Self::Output { Self::build(T::reduce(self.0 as u64 * rhs.0 as u64)) } } impl<T: Modulo> MulAssign for ModInt<T> { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } impl<T: Modulo> Neg for ModInt<T> { type Output = ModInt<T>; fn neg(self) -> Self::Output { if self.0 == 0 { Self::zero() } else { Self::build(T::modulo() - self.0) } } } impl<T: Modulo> std::fmt::Display for ModInt<T> { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.get()) } } impl<T: Modulo> std::fmt::Debug for ModInt<T> { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.get()) } } impl<T: Modulo> std::str::FromStr for ModInt<T> { type Err = std::num::ParseIntError; fn from_str(s: &str) -> Result<Self, Self::Err> { let val = s.parse::<u32>()?; Ok(ModInt::new(val)) } } impl<T: Modulo> From<usize> for ModInt<T> { fn from(val: usize) -> ModInt<T> { ModInt::new_unchecked((val % T::modulo() as usize) as u32) } } impl<T: Modulo> From<u64> for ModInt<T> { fn from(val: u64) -> ModInt<T> { ModInt::new_unchecked((val % T::modulo() as u64) as u32) } } impl<T: Modulo> From<i64> for ModInt<T> { fn from(val: i64) -> ModInt<T> { let m = T::modulo() as i64; ModInt::new((val % m + m) as u32) } } #[allow(dead_code)] impl<T> ModInt<T> { fn build(d: u32) -> Self { ModInt(d, PhantomData) } pub fn zero() -> Self { Self::build(0) } pub fn is_zero(&self) -> bool { self.0 == 0 } } #[allow(dead_code)] impl<T: Modulo> ModInt<T> { pub fn new_unchecked(d: u32) -> Self { Self::build(T::reduce(d as u64 * T::ini())) } pub fn new(d: u32) -> Self { Self::new_unchecked(d % T::modulo()) } pub fn one() -> Self { Self::new_unchecked(1) } pub fn get(&self) -> u32 { T::reduce(self.0 as u64) } pub fn pow(&self, mut n: u64) -> Self { let mut t = Self::one(); let mut s = *self; while n > 0 { if n & 1 == 1 { t *= s; } s *= s; n >>= 1; } t } pub fn inv(&self) -> Self { assert!(!self.is_zero()); self.pow((T::modulo() - 2) as u64) } } } // ---------- end ModInt ---------- // ---------- begin Precalc ---------- mod precalc { use super::modint::*; #[allow(dead_code)] pub struct Precalc<T> { inv: Vec<ModInt<T>>, fact: Vec<ModInt<T>>, ifact: Vec<ModInt<T>>, } #[allow(dead_code)] impl<T: Modulo> Precalc<T> { pub fn new(n: usize) -> Precalc<T> { let mut inv = vec![ModInt::one(); n + 1]; let mut fact = vec![ModInt::one(); n + 1]; let mut ifact = vec![ModInt::one(); n + 1]; for i in 2..(n + 1) { fact[i] = fact[i - 1] * ModInt::new_unchecked(i as u32); } ifact[n] = fact[n].inv(); if n > 0 { inv[n] = ifact[n] * fact[n - 1]; } for i in (1..n).rev() { ifact[i] = ifact[i + 1] * ModInt::new_unchecked((i + 1) as u32); inv[i] = ifact[i] * fact[i - 1]; } Precalc { inv: inv, fact: fact, ifact: ifact, } } pub fn inv(&self, n: usize) -> ModInt<T> { assert!(n > 0); self.inv[n] } pub fn fact(&self, n: usize) -> ModInt<T> { self.fact[n] } pub fn ifact(&self, n: usize) -> ModInt<T> { self.ifact[n] } pub fn perm(&self, n: usize, k: usize) -> ModInt<T> { if k > n { return ModInt::zero(); } self.fact[n] * self.ifact[n - k] } pub fn comb(&self, n: usize, k: usize) -> ModInt<T> { if k > n { return ModInt::zero(); } self.fact[n] * self.ifact[k] * self.ifact[n - k] } } } // ---------- end Precalc ---------- use modint::*; pub trait NTTFriendly: modint::Modulo { fn order() -> usize; fn zeta() -> u32; } type M = ModInt<Mod998_244_353>; impl NTTFriendly for Mod998_244_353 { fn order() -> usize { 8388608 } fn zeta() -> u32 { 15311432 } } use std::ops::*; pub trait Zero: Sized + Add<Output = Self> { fn zero() -> Self; } pub fn zero<T: Zero>() -> T { T::zero() } impl<T: Modulo> Zero for ModInt<T> { fn zero() -> Self { Self::zero() } } impl Zero for usize { fn zero() -> Self { 0 } } pub trait ArrayAdd { type Item; fn add(&self, rhs: &[Self::Item]) -> Vec<Self::Item>; } impl<T> ArrayAdd for [T] where T: Zero + Copy, { type Item = T; fn add(&self, rhs: &[Self::Item]) -> Vec<Self::Item> { let mut c = vec![T::zero(); self.len().max(rhs.len())]; c[..self.len()].copy_from_slice(self); c.add_assign(rhs); c } } pub trait ArrayAddAssign { type Item; fn add_assign(&mut self, rhs: &[Self::Item]); } impl<T> ArrayAddAssign for [T] where T: Add<Output = T> + Copy, { type Item = T; fn add_assign(&mut self, rhs: &[Self::Item]) { assert!(self.len() >= rhs.len()); self.iter_mut().zip(rhs).for_each(|(x, a)| *x = *x + *a); } } impl<T> ArrayAddAssign for Vec<T> where T: Zero + Add<Output = T> + Copy, { type Item = T; fn add_assign(&mut self, rhs: &[Self::Item]) { if self.len() < rhs.len() { self.resize(rhs.len(), T::zero()); } self.as_mut_slice().add_assign(rhs); } } pub trait ArraySub { type Item; fn sub(&self, rhs: &[Self::Item]) -> Vec<Self::Item>; } impl<T> ArraySub for [T] where T: Zero + Sub<Output = T> + Copy, { type Item = T; fn sub(&self, rhs: &[Self::Item]) -> Vec<Self::Item> { let mut c = vec![T::zero(); self.len().max(rhs.len())]; c[..self.len()].copy_from_slice(self); c.sub_assign(rhs); c } } pub trait ArraySubAssign { type Item; fn sub_assign(&mut self, rhs: &[Self::Item]); } impl<T> ArraySubAssign for [T] where T: Sub<Output = T> + Copy, { type Item = T; fn sub_assign(&mut self, rhs: &[Self::Item]) { assert!(self.len() >= rhs.len()); self.iter_mut().zip(rhs).for_each(|(x, a)| *x = *x - *a); } } impl<T> ArraySubAssign for Vec<T> where T: Zero + Sub<Output = T> + Copy, { type Item = T; fn sub_assign(&mut self, rhs: &[Self::Item]) { if self.len() < rhs.len() { self.resize(rhs.len(), T::zero()); } self.as_mut_slice().sub_assign(rhs); } } pub trait ArrayDot { type Item; fn dot(&self, rhs: &[Self::Item]) -> Vec<Self::Item>; } impl<T> ArrayDot for [T] where T: Mul<Output = T> + Copy, { type Item = T; fn dot(&self, rhs: &[Self::Item]) -> Vec<Self::Item> { assert!(self.len() == rhs.len()); self.iter().zip(rhs).map(|p| *p.0 * *p.1).collect() } } pub trait ArrayDotAssign { type Item; fn dot_assign(&mut self, rhs: &[Self::Item]); } impl<T> ArrayDotAssign for [T] where T: MulAssign + Copy, { type Item = T; fn dot_assign(&mut self, rhs: &[Self::Item]) { assert!(self.len() == rhs.len()); self.iter_mut().zip(rhs).for_each(|(x, a)| *x *= *a); } } pub trait ArrayMul { type Item; fn mul(&self, rhs: &[Self::Item]) -> Vec<Self::Item>; } impl<T> ArrayMul for [T] where T: Zero + Mul<Output = T> + Copy, { type Item = T; fn mul(&self, rhs: &[Self::Item]) -> Vec<Self::Item> { if self.is_empty() || rhs.is_empty() { return vec![]; } let mut res = vec![zero(); self.len() + rhs.len() - 1]; for (i, a) in self.iter().enumerate() { for (c, b) in res[i..].iter_mut().zip(rhs) { *c = *c + *a * *b; } } res } } pub trait ArrayNTT { type Item; fn ntt(&mut self); fn intt(&mut self); fn multiply(&self, rhs: &[Self::Item]) -> Vec<Self::Item>; } impl<T> ArrayNTT for [ModInt<T>] where T: NTTFriendly, { type Item = ModInt<T>; fn ntt(&mut self) { let f = self; let n = f.len(); assert!(n.count_ones() == 1); assert!(n <= T::order()); let len = n.trailing_zeros() as usize; let mut es = [ModInt::zero(); 30]; let mut ies = [ModInt::zero(); 30]; let mut sum_e = [ModInt::zero(); 30]; let cnt2 = T::order().trailing_zeros() as usize; let mut e = ModInt::new_unchecked(T::zeta()); let mut ie = e.inv(); for i in (2..=cnt2).rev() { es[i - 2] = e; ies[i - 2] = ie; e = e * e; ie = ie * ie; } let mut now = ModInt::one(); for i in 0..(cnt2 - 1) { sum_e[i] = es[i] * now; now *= ies[i]; } for ph in 1..=len { let p = 1 << (len - ph); let mut now = ModInt::one(); for (i, f) in f.chunks_exact_mut(2 * p).enumerate() { let (x, y) = f.split_at_mut(p); for (x, y) in x.iter_mut().zip(y.iter_mut()) { let l = *x; let r = *y * now; *x = l + r; *y = l - r; } now *= sum_e[(!i).trailing_zeros() as usize]; } } } fn intt(&mut self) { let f = self; let n = f.len(); assert!(n.count_ones() == 1); assert!(n <= T::order()); let len = n.trailing_zeros() as usize; let mut es = [ModInt::zero(); 30]; let mut ies = [ModInt::zero(); 30]; let mut sum_ie = [ModInt::zero(); 30]; let cnt2 = T::order().trailing_zeros() as usize; let mut e = ModInt::new_unchecked(T::zeta()); let mut ie = e.inv(); for i in (2..=cnt2).rev() { es[i - 2] = e; ies[i - 2] = ie; e = e * e; ie = ie * ie; } let mut now = ModInt::one(); for i in 0..(cnt2 - 1) { sum_ie[i] = ies[i] * now; now *= es[i]; } for ph in (1..=len).rev() { let p = 1 << (len - ph); let mut inow = ModInt::one(); for (i, f) in f.chunks_exact_mut(2 * p).enumerate() { let (x, y) = f.split_at_mut(p); for (x, y) in x.iter_mut().zip(y.iter_mut()) { let l = *x; let r = *y; *x = l + r; *y = (l - r) * inow; } inow *= sum_ie[(!i).trailing_zeros() as usize]; } } let ik = ModInt::new_unchecked((T::modulo() + 1) >> 1).pow(len as u64); for f in f.iter_mut() { *f *= ik; } } fn multiply(&self, rhs: &[Self::Item]) -> Vec<Self::Item> { if self.len().min(rhs.len()) <= 32 { return self.mul(rhs); } let size = (self.len() + rhs.len() - 1).next_power_of_two(); let mut f = vec![ModInt::zero(); size]; let mut g = vec![ModInt::zero(); size]; f[..self.len()].copy_from_slice(self); g[..rhs.len()].copy_from_slice(rhs); f.ntt(); g.ntt(); f.dot_assign(&g); f.intt(); f.truncate(self.len() + rhs.len() - 1); f } } fn read() -> (usize, usize) { let mut s = String::new(); use std::io::Read; std::io::stdin().read_to_string(&mut s).unwrap(); let a = s.trim().split_whitespace().flat_map(|s| s.parse()).collect::<Vec<_>>(); let (n, m) = (a[0], a[1]); assert!(1 <= n && n <= 200_000); assert!(1 <= m && m <= 200_000); (n, m) } fn divide_and_conquer(ok: &mut [M], ng: &mut [M], a: &[M], b: &[M]) { if ok.len() == 1 { ok[0] -= ng[0]; return; } let m = ok.len() / 2; divide_and_conquer(&mut ok[..m], &mut ng[..m], a, b); let len = ok.len(); let x = ok[..m].multiply(&a[..len]); let y = ng[..m].multiply(&b[..len]); for (((ok, ng), x), y) in ok.iter_mut().zip(ng.iter_mut()).zip(x).zip(y).skip(m) { *ok -= y; *ng += x; } divide_and_conquer(&mut ok[m..], &mut ng[m..], a, b); } fn main() { let (n, m) = read(); let mut a = vec![M::zero(); n + 1]; for i in 1..=m { for j in 1..=(n / i) { a[i * j] += M::one(); } } let mut b = vec![M::zero(); n + 1]; for i in 1..=n { b[i] = M::from(m - 1) * M::from(m).pow(i as u64 - 1); } let mut ng = vec![M::zero(); n + 1]; let mut ok = vec![M::zero(); n + 1]; for (i, ok) in ok.iter_mut().enumerate() { *ok = M::from(m).pow(i as u64); } divide_and_conquer(&mut ok, &mut ng, &a, &b); let ans = M::from(m).pow(n as u64) - ok[n]; println!("{}", ans); }