結果
| 問題 |
No.3118 Increment or Multiply
|
| ユーザー |
 solalyth
|
| 提出日時 | 2025-04-20 15:21:33 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 33,284 bytes |
| コンパイル時間 | 20,031 ms |
| コンパイル使用メモリ | 402,964 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2025-04-20 15:21:56 |
| 合計ジャッジ時間 | 16,935 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 20 WA * 15 |
コンパイルメッセージ
warning: unused imports: `Bytes as bytes`, `Chars as chars`, `Isize1 as isize1`, `Usize1 as usize1`, and `input_interactive`
--> src/main.rs:85:31017
|
85 | ... proconio::{ input, input_interactive, marker::{Bytes as bytes, Chars as chars, Usize1 as usize1, Isize1 as isize1} }, }; }
| ^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
ソースコード
#![allow(unused_must_use, non_snake_case)]
#[allow(unused_imports)]
use {external::*, mylib::*, prelude::*};
const INTERACTIVE: bool = false;
fn solve() {
input! {
T: usize, Q: [(usize, usize); T]
}
let m = 998244353;
for (N, A) in Q {
if A == 1 {
let mut tmp = (N%m) * ((N-1)%m);
if tmp % 2 == 1 { tmp += m; }
out << (tmp/2) << end;
continue;
}
let mut tmp = N;
let mut na = vec![];
let mut B = vec![N];
while tmp != 0 { na.push(tmp%A); tmp /= A; B.push(tmp); }
let mut wa = vec![0];
for i in 0..na.len() { wa.push(wa[i] + na[i]); }
na.reverse();
B.reverse();
wa.reverse();
epr!("na = {na:?}");
epr!("wa = {wa:?}");
epr!("B = {B:?}");
// wa[i] = na[i..];
let mut ans = 0;
for i in 1..B.len() {
// for B[i-1] < k <= B[i]
// B[i] - k
// B.len() - i - 1 + na[i..]
let l = (B[i] - B[i-1]) % m;
let a1 = (B.len() - i - 1 + wa[i]) % m;
ans += (l*a1) % m;
let mut a2 = l*(l+m-1) % m;
if a2 % 2 == 1 { a2 += m; }
a2 /= 2;
// epr!("loop: {l}, {a1}, {a2}");
ans += a2;
ans %= m;
}
// let mut ans2 = 0;
// for mut i in 1..N {
// for j in 1..B.len() {
// if i <= B[j] {
// ans2 += B[j]-i;
// i = B[j];
// if i != N {
// i *= A;
// ans2 += 1;
// }
// }
// }
// assert!(i == N);
// ans2 %= m;
// }
// assert_eq!(ans, ans2);
out << ans << end;
}
}
fn main() { out.init(if INTERACTIVE || !SUBMISSION { EndFlag::Print } else { EndFlag::LineFeed }); solve(); out.print() }
// You can view my library at https://github.com/solalyth/atcoder-env-rs
#[cfg(not(debug_assertions))] #[allow(unused)] mod mylib { #![allow(non_upper_case_globals)] pub const SUBMISSION: bool = true; pub use { util::{ printer::{out, end, EndFlag}, traits::*, func::binary_search } }; pub mod prelude { pub use std::{ collections::{VecDeque, HashMap, HashSet, BTreeMap, BTreeSet, BinaryHeap}, cmp::Ordering, mem::{swap, replace} }; } pub mod ds { pub mod unionfind { pub use crate::mylib::abstracts::{Group, Nop}; #[derive(Clone)] pub struct UnionFind<Op: Group> { par: Vec<usize>, size: Vec<usize>, diff: Vec<Op::T> } impl UnionFind<Nop> { pub fn new_nop(len: usize) -> Self { Self::new(len) } } impl<Op: Group> UnionFind<Op> { pub fn new(len: usize) -> Self { UnionFind { par: (0..len).collect(), size: vec![1; len], diff: vec![Op::e(); len] } } pub fn extend(&mut self, len: usize) { self.par.extend(self.size.len()..len); self.size.resize(len, 1); self.diff.resize(len, Op::e()); } pub fn len(&self) -> usize { self.par.len() } pub fn leader(&mut self, i: usize) -> usize { let p = self.par[i]; if self.par[p] == p { return p; } let u = self.leader(p); self.diff[i] = Op::add(&self.diff[i], &self.diff[p]); self.par[i] = u; u } pub fn size(&mut self, mut i: usize) -> usize { i = self.leader(i); self.size[i] } pub fn is_same(&mut self, i: usize, j: usize) -> bool { self.leader(i) == self.leader(j) } pub fn diff(&mut self, i: usize, j: usize) -> Option<Op::T> { if self.is_same(i, j) { Some(Op::sub(&self.diff[i], &self.diff[j])) } else { None } } pub fn merge(&mut self, i: usize, j: usize, mut w: Op::T) -> Option<Option<(usize, usize)>> { let (mut u, mut v) = (self.leader(i), self.leader(j)); w = Op::sub(&Op::add(&w, &self.diff[j]), &self.diff[i]); if u == v { return if w == Op::e() { Some(None) } else { None } } if self.size[u] > self.size[v] { (u, v) = (v, u); w = Op::inv(&w); } self.par[u] = v; self.diff[u] = w; self.size[v] += self.size[u]; Some(Some((v, u))) } pub fn groups(&mut self) -> Vec<Vec<usize>> { let mut res = crate::nest![void; self.len()]; for i in 0..self.len() { res[self.leader(i)].push(i); } res.retain(|v| v.len() != 0); res } pub fn leaders(&self) -> Vec<usize> { (0..self.len()).filter(|&i| self.par[i] == i).collect() } } impl<Op: Group> std::fmt::Debug for UnionFind<Op> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { use crate::mylib::util::func::join; let mut uf = self.clone(); let g = uf.groups().into_iter().map(|s| { join(s.into_iter().map(|i| format!("{i}({:?})", uf.diff[i]).trim_end_matches("(())").into())).unwrap() }); write!(f, "[{}]", join(g.into_iter().map(|s| format!("{{{s}}}"))).unwrap_or(String::new())) } } } pub mod foldable_deque { use std::{collections::VecDeque, fmt::Debug}; pub use crate::mylib::abstracts::Monoid; pub struct FoldableDeque<Op: Monoid> { deque: VecDeque<Op::T>, front: Vec<Op::T>, back: Vec<Op::T>, e: Op::T } impl<Op: Monoid> FoldableDeque<Op> { pub fn new() -> Self { Self { deque: VecDeque::new(), front: vec![], back: vec![], e: Op::e() } } pub fn deque(&self) -> &VecDeque<Op::T> { &self.deque } pub fn len(&self) -> usize { self.deque.len() } fn fold_front(&self) -> &Op::T { self.front.last().unwrap_or(&self.e) } fn fold_back(&self) -> &Op::T { self.back.last().unwrap_or(&self.e) } pub fn fold(&self) -> Op::T { Op::prod(&self.fold_front(), &self.fold_back()) } pub fn push_front(&mut self, v: Op::T) { self.front.push(Op::prod(&v, self.fold_front())); self.deque.push_front(v); } pub fn push_back(&mut self, v: Op::T) { self.back.push(Op::prod(self.fold_back(), &v)); self.deque.push_back(v); } pub fn pop_front(&mut self) -> Option<Op::T> { let res = self.deque.pop_front(); if self.front.pop().is_none() { self.rebuild(); } res } pub fn pop_back(&mut self) -> Option<Op::T> { let res = self.deque.pop_back(); if self.back.pop().is_none() { self.rebuild(); } res } fn rebuild(&mut self) { self.front.clear(); self.back.clear(); let len = self.deque.len(); let mut tmp = Op::e(); for i in (0..len/2).rev() { tmp = Op::prod(&self.deque[i], &tmp); self.front.push(tmp.clone()); } tmp = Op::e(); for i in len/2..len { tmp = Op::prod(&tmp, &self.deque[i]); self.back.push(tmp.clone()); } } } impl<Op: Monoid> FromIterator<Op::T> for FoldableDeque<Op> { fn from_iter<T: IntoIterator<Item = Op::T>>(iter: T) -> Self { let mut deq = Self::new(); for v in iter { deq.push_back(v); } deq } } impl<Op: Monoid> Clone for FoldableDeque<Op> { fn clone(&self) -> Self { Self { deque: self.deque.clone(), front: self.front.clone(), back: self.back.clone(), e: self.e.clone() } } } impl<Op: Monoid> Debug for FoldableDeque<Op> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{{ fold: {:?}, deque: {:?} }}", self.fold(), self.deque) } } } pub mod segtree { use std::{fmt::Debug, mem, ops::{Index, IndexMut, RangeBounds}, slice::SliceIndex}; use crate::mylib::util::func::to_bounds; pub struct Segtree<Op: SegtreeOp> { tree: Vec<Op::Value>, lazy: Vec<Option<Op::Lazy>>, depth: u32 } #[allow(unused_variables)] pub trait SegtreeOp: Sized { type Value: Clone; type Lazy: Clone; fn id_value() -> Self::Value; fn prod_value(lhs: &Self::Value, rhs: &Self::Value) -> Self::Value; fn act_value(value: &mut Self::Value, lazy: &Self::Lazy) {} fn comp_lazy(lazy: &mut Self::Lazy, ad: &Self::Lazy) {} fn new(len: usize) -> Segtree<Self> { Segtree::<Self>::new(len) } fn from_iter(iter: impl Iterator<Item = Self::Value>) -> Segtree<Self> { Segtree::<Self>::from_iter(iter) } } impl<Op: SegtreeOp> Segtree<Op> { pub fn new(len: usize) -> Self { let depth = (len.max(2)-1).ilog2() + 2; Segtree { tree: vec![Op::id_value(); 1<<depth], lazy: vec![None; 1<<depth], depth } } pub fn len(&self) -> usize { 1 << self.depth-1 } pub fn get(&mut self, mut i: usize) -> &Op::Value { i += self.len(); for j in (1..self.depth).rev() { self.push(i >> j); } &self.tree[i] } pub fn set(&mut self, mut i: usize, value: Op::Value) -> Op::Value { i += self.len(); for j in (1..self.depth).rev() { self.push(i >> j); } let res = mem::replace(&mut self.tree[i], value); for j in 1..self.depth { self.update(i >> j); } res } pub fn entry(&mut self, range: impl RangeBounds<usize>) -> Entry<'_, Op> { let [l, r] = to_bounds(range, self.len()).map(|v| v+self.len()); if r != self.len() { for i in (1..self.depth).rev() { for j in (l >> i)..=(r-1 >> i) { self.push(j); } } } Entry { seg: self, l, r, changed: false } } pub fn fold(&mut self, range: impl RangeBounds<usize>) -> Op::Value { let [mut l, mut r] = to_bounds(range, self.len()).map(|v| v+self.len()); if r == self.len() { return Op::id_value(); } let (mut rl, mut rr) = (Op::id_value(), Op::id_value()); for i in (1..self.depth).rev() { self.push(l >> i); self.push(r-1 >> i); } while l < r { if l&1 == 1 { rl = Op::prod_value(&rl, &self.tree[l]); l += 1; } if r&1 == 1 { rr = Op::prod_value(&self.tree[r-1], &rr); } l >>= 1; r >>= 1; } Op::prod_value(&rl, &rr) } pub fn apply_lazy(&mut self, range: impl RangeBounds<usize>, lazy: Op::Lazy) { let [l, r] = to_bounds(range, self.len()).map(|v| v + self.len()); if r == 0 { return; } for i in (1..self.depth).rev() { self.push(l >> i); self.push(r-1 >> i); } { let (mut l, mut r) = (l, r); while l < r { if l&1 == 1 { Op::act_value(&mut self.tree[l], &lazy); self.comp_lazy(l, &lazy); l += 1; } if r&1 == 1 { r -= 1; Op::act_value(&mut self.tree[r], &lazy); self.comp_lazy(r, &lazy); } l >>= 1; r >>= 1; } } for i in 1..self.depth { self.update(l >> i); self.update(r-1 >> i); } } pub fn max_right(&mut self, l: usize, f: impl Fn(&Op::Value) -> bool) -> usize { assert!(l <= self.len()); if l == self.len() { return self.len(); } let (mut r, mut val) = (l + self.len(), Op::id_value()); for i in (1..self.depth).rev() { self.push(r >> i); } loop { while r&1 == 0 { r /= 2; } let tmp = Op::prod_value(&val, &self.tree[r]); if !f(&tmp) { break; } val = tmp; r += 1; if { let r = r as isize; (r & -r) != r } { return self.len(); } } while r < self.len() { self.push(r); r <<= 1; let tmp = Op::prod_value(&val, &self.tree[r]); if f(&tmp) { val = tmp; r += 1; } } r - self.len() } pub fn min_left(&mut self, r: usize, f: impl Fn(&Op::Value) -> bool) -> usize { assert!(r <= self.len()); if r == 0 { return 0; } let (mut l, mut val) = (r + self.len(), Op::id_value()); for i in (1..self.depth).rev() { self.push(l-1 >> i); } loop { l -= 1; l >>= l.trailing_zeros(); let tmp = Op::prod_value(&self.tree[l], &val); if !f(&tmp) { break; } val = tmp; } while l < self.len() { l = 2*l+1; self.push(l); let tmp = Op::prod_value(&self.tree[l], &val); if f(&tmp) { val = tmp; l -= 1; } } l+1 - self.len() } fn push(&mut self, i: usize) { debug_assert!(i < self.len()); let Some(lazy) = mem::replace(&mut self.lazy[i], None) else { return }; Op::act_value(&mut self.tree[2*i], &lazy); Op::act_value(&mut self.tree[2*i+1], &lazy); self.comp_lazy(2*i, &lazy); self.comp_lazy(2*i+1, &lazy); } fn update(&mut self, i: usize) { debug_assert!(i < self.len()); self.tree[i] = Op::prod_value(&self.tree[2*i], &self.tree[2*i+1]); } fn comp_lazy(&mut self, i: usize, ad: &Op::Lazy) { if let Some(lazy) = &mut self.lazy[i] { Op::comp_lazy(lazy, ad); } else { self.lazy[i] = Some(ad.clone()); } } } impl<Op: SegtreeOp> Clone for Segtree<Op> { fn clone(&self) -> Self { Self { tree: self.tree.clone(), lazy: self.lazy.clone(), depth: self.depth.clone() } } } impl<Op: SegtreeOp> Debug for Segtree<Op> where Op::Value: Debug { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { let mut seg = self.clone(); for i in 1..seg.tree.len() { seg.push(i); } write!(f, "{:?}", &seg.tree[self.len()..]) } } impl<Op: SegtreeOp> FromIterator<Op::Value> for Segtree<Op> { fn from_iter<T: IntoIterator<Item = Op::Value>>(iter: T) -> Self { let v = iter.into_iter().collect::<Vec<_>>(); let mut seg = Self::new(v.len()); { let mut seg = seg.entry(..); for (i, v) in v.into_iter().enumerate() { seg[i] = v; } } seg } } pub struct Entry<'a, Op: SegtreeOp> { seg: &'a mut Segtree<Op>, l: usize, r: usize, changed: bool } impl<Op: SegtreeOp> Entry<'_, Op> { pub fn len(&self) -> usize { self.r - self.l } pub fn to_relative(&self, i: usize) -> usize { i - self.l } } impl<Op: SegtreeOp, I: SliceIndex<[Op::Value]>> Index<I> for Entry<'_, Op> { type Output = I::Output; fn index(&self, index: I) -> &Self::Output { Index::index(&self.seg.tree[self.l..self.r], index) } } impl<Op: SegtreeOp, I: SliceIndex<[Op::Value]>> IndexMut<I> for Entry<'_, Op> { fn index_mut(&mut self, index: I) -> &mut Self::Output { self.changed = true; IndexMut::index_mut(&mut self.seg.tree[self.l..self.r], index) } } impl<Op: SegtreeOp> Drop for Entry<'_, Op> { fn drop(&mut self) { if self.changed { for i in (1..self.seg.depth).rev() { for j in (self.l >> i)..=(self.r-1 >> i) { self.seg.update(j); } } } } } } pub mod multiset { use std::{collections::{BTreeMap, HashMap}, hash::Hash, ops::RangeBounds, ptr::eq as ptr_eq}; pub use { btree_multi_set::BTreeMultiSet, hash_multi_set::HashMultiSet }; pub struct BlockItem<'a, V> { pub value: &'a V, pub len: usize, pub idx: usize, } mod btree_multi_set { use super::*; use std::collections::btree_map::Iter as BIter; #[derive(Clone, Debug, PartialEq, Eq)] pub struct BTreeMultiSet<V: Ord + Clone> { inner: BTreeMap<V, usize>, len: usize } impl<V: Ord + Clone> BTreeMultiSet<V> { pub fn clear(&mut self) { self.inner.clear(); self.len = 0; } pub fn contains(&self, value: &V) -> bool { self.inner.contains_key(&value) } pub fn insert(&mut self, value: &V, n: usize) { self.modify(value, |befn| befn+n); } pub fn is_empty(&self) -> bool { self.len == 0 } pub fn len(&self) -> usize { self.len } pub fn remove(&mut self, value: &V, n: usize, strict: bool) -> bool { let mut ret = true; self.modify(value, |befn| { if strict && befn < n { ret = false; befn } else { befn.saturating_sub(n) } }); ret } pub fn remove_block(&mut self, value: &V) -> Option<usize> { let mut ret = None; self.modify(value, |n| { if n != 0 { ret = Some(n); } 0 }); ret } pub fn len_blocks(&self) -> usize { self.inner.len() } pub fn len_block(&self, value: &V) -> usize { *self.inner.get(value).unwrap_or(&0) } pub fn modify(&mut self, value: &V, f: impl FnOnce(usize) -> usize) { if let Some(n) = self.inner.get_mut(value) { self.len -= *n; *n = f(*n); self.len += *n; if *n == 0 { self.inner.remove(value); } } else { let n = f(0); if n != 0 { self.inner.insert(value.clone(), n); self.len += n; } } } pub fn iter(&self) -> Iter<V> { Iter::new(self) } pub fn iter_blocks(&self) -> impl Iterator<Item = (&V, usize)> + DoubleEndedIterator { self.inner.iter().map(|(v, &n)| (v, n)) } pub fn new() -> Self { Self { inner: BTreeMap::new(), len: 0 } } pub fn first(&self) -> Option<(&V, usize)> { self.inner.first_key_value().map(|v| (v.0, *v.1)) } pub fn last(&self) -> Option<(&V, usize)> { self.inner.last_key_value().map(|v| (v.0, *v.1)) } pub fn pop_first(&mut self) -> Option<V> { let Some(mut entry) = self.inner.first_entry() else { return None; }; let (v, &n) = (entry.key().clone(), entry.get()); if n == 1 { entry.remove(); } else { entry.insert(n-1); } self.len -= 1; Some(v) } pub fn pop_last(&mut self) -> Option<V> { let Some(mut entry) = self.inner.last_entry() else { return None; }; let (v, &n) = (entry.key().clone(), entry.get()); if n == 1 { entry.remove(); } else { entry.insert(n-1); } self.len -= 1; Some(v) } pub fn range_blocks(&self, range: impl RangeBounds<V>) -> impl Iterator<Item = (&V, usize)> + DoubleEndedIterator { self.inner.range(range).map(|(v, &n)| (v, n)) } pub fn pop_first_block(&mut self) -> Option<(V, usize)> { if let Some(v) = self.inner.pop_first() { self.len -= v.1; Some(v) } else { None } } pub fn pop_last_block(&mut self) -> Option<(V, usize)> { if let Some(v) = self.inner.pop_last() { self.len -= v.1; Some(v) } else { None } } } impl<V: Ord + Clone> FromIterator<V> for BTreeMultiSet<V> { fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self { let mut res = Self::new(); for v in iter { res.insert(&v, 1); } res } } pub enum Iter<'a, V> { Empty, Some { src: BIter<'a, V, usize>, f: (&'a V, &'a usize), b: (&'a V, &'a usize), fidx: usize, bidx: usize } } impl<'a, V: Ord + Clone> Iter<'a, V> { fn new(src: &'a BTreeMultiSet<V>) -> Self { if src.is_empty() { return Self::Empty; } let mut src = src.inner.iter(); let f = src.next().unwrap(); let b = src.next_back().unwrap_or(f); Self::Some { src, f, b, fidx: 0, bidx: *b.1 } } } impl<'a, V> Iterator for Iter<'a, V> { type Item = BlockItem<'a, V>; fn next(&mut self) -> Option<Self::Item> { let Self::Some { src, f, b, fidx, bidx } = self else { return None; }; let res = BlockItem { value: f.0, len: *f.1, idx: *fidx }; *fidx += 1; if ptr_eq(f.0, b.0) && fidx == bidx { *self = Self::Empty; return Some(res); } if fidx == f.1 { *f = src.next().unwrap_or(*b); *fidx = 0; } Some(res) } } impl<'a, V> DoubleEndedIterator for Iter<'a, V> { fn next_back(&mut self) -> Option<Self::Item> { let Self::Some { src, f, b, fidx, bidx } = self else { return None; }; *bidx -= 1; let res = BlockItem { value: b.0, len: *b.1, idx: *bidx }; if ptr_eq(f.0, b.0) && fidx == bidx { *self = Self::Empty; return Some(res); } if *bidx == 0 { *b = src.next().unwrap_or(*f); *bidx = *b.1; } Some(res) } } } mod hash_multi_set { use super::*; use std::collections::hash_map::Iter as HIter; pub struct HashMultiSet<V: Clone + Hash + Eq> { inner: HashMap<V, usize>, len: usize } impl<V: Clone + Hash + Eq> HashMultiSet<V> { pub fn clear(&mut self) { self.inner.clear(); self.len = 0; } pub fn contains(&self, value: &V) -> bool { self.inner.contains_key(&value) } pub fn insert(&mut self, value: &V, n: usize) { self.modify(value, |befn| befn+n); } pub fn is_empty(&self) -> bool { self.len == 0 } pub fn len(&self) -> usize { self.len } pub fn remove(&mut self, value: &V, n: usize, strict: bool) -> bool { let mut ret = true; self.modify(value, |befn| { if strict && befn < n { ret = false; befn } else { befn.saturating_sub(n) } }); ret } pub fn remove_block(&mut self, value: &V) -> Option<usize> { let mut ret = None; self.modify(value, |n| { if n != 0 { ret = Some(n); } 0 }); ret } pub fn len_blocks(&self) -> usize { self.inner.len() } pub fn len_block(&self, value: &V) -> usize { *self.inner.get(value).unwrap_or(&0) } pub fn modify(&mut self, value: &V, f: impl FnOnce(usize) -> usize) { if let Some(n) = self.inner.get_mut(value) { self.len -= *n; *n = f(*n); self.len += *n; if *n == 0 { self.inner.remove(value); } } else { let n = f(0); if n != 0 { self.inner.insert(value.clone(), n); self.len += n; } } } pub fn iter(&self) -> Iter<V> { Iter::new(self) } pub fn iter_blocks(&self) -> impl Iterator<Item = (&V, usize)> { self.inner.iter().map(|(v, &n)| (v, n)) } pub fn new() -> Self { Self { inner: HashMap::new(), len: 0} } } impl<V: Clone + Hash + Eq> FromIterator<V> for HashMultiSet<V> { fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self { let mut res = Self::new(); for v in iter { res.insert(&v, 1); } res } } pub enum Iter<'a, V> { Empty, Some { src: HIter<'a, V, usize>, f: (&'a V, &'a usize), fidx: usize, } } impl<'a, V: Clone + Hash + Eq> Iter<'a, V> { fn new(src: &'a HashMultiSet<V>) -> Self { if src.is_empty() { return Self::Empty; } let mut src = src.inner.iter(); let f = src.next().unwrap(); Self::Some { src, f, fidx: 0 } } } impl<'a, V> Iterator for Iter<'a, V> { type Item = BlockItem<'a, V>; fn next(&mut self) -> Option<Self::Item> { let Self::Some { src, f, fidx } = self else { return None; }; let res = BlockItem { value: f.0, len: *f.1, idx: *fidx }; *fidx += 1; if fidx == f.1 { if let Some(tmp) = src.next() { *f = tmp; *fidx = 0; } else { *self = Self::Empty; return Some(res); } } Some(res) } } } } } pub mod algo { pub mod rolling_hash { use crate::mylib::abstracts::Monoid; #[derive(Clone)] pub struct RollingHash; impl Monoid for RollingHash { type T = (u128, usize); fn e() -> Self::T { (0, 0) } fn prod(&l: &Self::T, &r: &Self::T) -> Self::T { Self::prod(l, r) } } impl RollingHash { pub const MOD: u128 = 2u128.pow(61) - 1; pub const BASE: u128 = 998244353; pub const BASELEN: usize = 30; pub const BASEEXP: [u128; Self::BASELEN] = { let mut res = [Self::BASE; Self::BASELEN]; let mut i = 1; while i < Self::BASELEN { res[i] = Self::modulo(res[i-1]*res[i-1]); i += 1; } res }; pub const fn modulo(mut v: u128) -> u128 { v = (v >> 61) + (v & Self::MOD); if Self::MOD <= v { v - Self::MOD } else { v } } pub fn prod((mut lv, ls): (u128, usize), (rv, rs): (u128, usize)) -> (u128, usize) { for i in 0..Self::BASELEN { if rs>>i & 1 == 1 { lv = Self::modulo(lv*Self::BASEEXP[i]); } } lv += rv; (if Self::MOD <= lv { lv-Self::MOD } else { lv }, ls+rs) } pub fn fold(iter: impl Iterator<Item = u128>) -> u128 { iter.reduce(|acc, v| Self::modulo(acc*Self::BASE + v)).unwrap_or(0) } } } pub mod tree { pub struct Tree { pub n: usize, pub e: Vec<Vec<usize>> } impl Tree { pub fn new(n: usize, e_iter: impl Iterator<Item = (usize, usize)>) -> Self { let mut e = vec![vec![]; n]; for (u, v) in e_iter { e[u].push(v); e[v].push(u); } Self { n, e } } pub fn calc(&self, root: usize) -> (Vec<usize>, Vec<usize>, Vec<usize>) { let (mut par, mut bfs, mut dist) = (vec![usize::MAX; self.n], vec![root], vec![0; self.n]); dist[root] = 0; for i in 0..self.n { let i = bfs[i]; for &j in &self.e[i] { if j != par[i] { par[j] = i; dist[j] = dist[i]+1; bfs.push(j); } } } (par, bfs, dist) } pub fn diameter(&self) -> ([usize; 2], usize) { let dist1 = self.calc(0).2; let x = (0..self.n).max_by_key(|&i| dist1[i]).unwrap(); let dist2 = self.calc(x).2; let y= (0..self.n).max_by_key(|&i| dist2[i]).unwrap(); ([x, y], dist2[y]) } } } } pub mod abstracts { use std::fmt::Debug; #[derive(Clone)] pub struct Nop; pub trait Monoid: Clone { type T: Clone + PartialEq + Debug; fn e() -> Self::T; fn prod(l: &Self::T, r: &Self::T) -> Self::T; } pub trait Group: Clone { type T: Clone + PartialEq + Debug; fn e() -> Self::T; fn add(l: &Self::T, r: &Self::T) -> Self::T; fn inv(x: &Self::T) -> Self::T; #[doc(hidden)] fn sub(l: &Self::T, r: &Self::T) -> Self::T { Self::add(l, &Self::inv(r)) } } impl Group for Nop { type T = (); fn e() {} fn add(_: &(), _: &()) {} fn inv(_: &()) {} } } pub mod math { pub mod prime { use super::montgomery::Montgomery; const MASK_29bit: usize = (1<<29)-1; pub struct LpfSieve { primes: Vec<usize>, table: Vec<usize> } impl LpfSieve { pub fn new(mut max: usize) -> Self { assert!(usize::BITS == 64); assert!(max <= 10_000_000); max = max.max(10); let mut primes = vec![]; let mut table = vec![0; max+1]; for i in 2..=max { if table[i] == 0 { primes.push(i); table[i] = (1 << 58) + (i << 29) + 1; } let lpf_i = (table[i] >> 29) & MASK_29bit; for &p in &primes { if !(p <= lpf_i && i*p <= max) { break; } table[p*i] = if p == lpf_i { table[i] + (1 << 58) } else { (1 << 58) + (p << 29) + i }; } } Self { primes, table } } pub fn max(&self) -> usize { self.table.len()-1 } pub fn primes(&self) -> &[usize] { &self.primes } pub fn is_prime(&self, n: usize) -> bool { (self.table[n] >> 29) & MASK_29bit == n } pub fn data(&self, n: usize) -> (usize, usize, usize) { assert!(n != 0 && n != 1); ((self.table[n] >> 29) & MASK_29bit, self.table[n] >> 58, self.table[n] & MASK_29bit) } pub fn fold<T>(&self, mut n: usize, mut init: T, mut f_vpe: impl FnMut(&mut T, usize, usize)) -> T { assert!(n != 0); while n != 1 { let (lpf, exp, nx) = self.data(n); f_vpe(&mut init, lpf, exp); n = nx; } init } pub fn fact(&self, n: usize) -> Vec<(usize, usize)> { self.fold(n, vec![], |v, p, e| { v.push((p, e)); } ) } pub fn divisors(&self, n: usize) -> Vec<usize> { assert!(n != 0); let mut res = self.fold(n, vec![1], |v, p, e| { for i in 0..v.len() { let mut k = 1; for _ in 0..e { k *= p; v.push(v[i]*k); } } }); res.sort_unstable(); res } pub fn totient(&self, n: usize) -> usize { self.fold(n, n, |v, p, _e| { *v -= *v/p; }) } pub fn totient_table(&self, n: usize) -> Vec<usize> { let mut res = vec![0; n+1]; res[1] = 1; for i in 2..=n { let (lpf, exp, _nx) = self.data(i); res[i] = res[i/lpf] * if exp == 1 { lpf-1 } else { lpf }; } res } pub fn mobius(&self, n: usize) -> i64 { self.fold(n, 1, |v, _p, e| { *v = if e == 1 { -*v } else { 0 }; }) } pub fn mobius_table(&self, n: usize) -> Vec<i64> { let mut res = vec![0; n+1]; res[1] = 1; for i in 2..=n { let (_lpf, exp, nx) = self.data(i); if exp == 1 { res[i] = -res[nx]; } } res } } pub fn millar_rabin(n: u64) -> bool { assert!(n != 0); if n == 2 { return true; } if n == 1 || n%2 == 0 { return false; } let (mut s, mut d) = (0, n); while d%2 == 0 { s += 1; d /= 2; } let mnt = Montgomery::new(n); let al: &[u64] = if n < 4759123141 { &[2, 7, 61] } else { &[2, 325, 9375, 28178, 450775, 9780504, 1795265022] }; 'a: for &a in al { let mut x = mnt.pow(mnt.prod_r(a), d); if x == 1 { continue; } for _ in 0..s { if x == n-1 { continue 'a; } x = mnt.prod_rinv(x*x); } return false; } true } } pub mod montgomery { pub struct Montgomery { m: u64, r2: u64, mont: u32 } impl Montgomery { pub fn new(m: u64) -> Self { assert!(m < 1<<32 && m%2 == 1); let r2 = (!m+1) % m; let mut tmp = m as u32; for _ in 0..4 { tmp = tmp.wrapping_mul(2u32.wrapping_sub(tmp.wrapping_mul(m as u32))); } Self { m, r2, mont: !tmp+1 } } pub fn prod_r(&self, x: u64) -> u64 { self.prod_rinv(x * self.r2) } pub fn prod_rinv(&self, x: u64) -> u64 { let a = self.mont.wrapping_mul(x as u32) as u64; let b = (x + a*self.m) >> 32; if self.m <= b { b - self.m } else { b } } pub fn rem(&self, mut x: u64) -> u64 { if x <= self.m * 8 { while self.m <= x { x -= self.m; } x } else { self.prod_r(self.prod_rinv(x)) } } pub fn pow(&self, mut xr: u64, mut n: u64) -> u64 { if n == 0 { return self.prod_r(1); } let mut res = 1<<32; while n != 0 { if n&1 == 1 { res = self.prod_rinv(res*xr); } xr = self.prod_rinv(xr*xr); n >>= 1; } res } } } } pub mod util { pub mod printer { #![allow(non_camel_case_types)] use std::{mem::{replace, transmute}, ops::{Not, Shl}, sync::{Mutex, MutexGuard, OnceLock}}; static INTERNAL: OnceLock<Mutex<Internal>> = OnceLock::new(); pub static out: Printer = Printer(&INTERNAL); pub struct Internal { buf: String, endf: EndFlag, prvf: PreviousFlag } #[derive(PartialEq, Eq)] pub enum EndFlag { DoNothing, LineFeed, Print } use PreviousFlag::*; #[derive(PartialEq, Eq, Clone, Copy)] enum PreviousFlag { Space, NoSpace, LineHead, } pub struct end; #[derive(Clone, Copy)] pub struct Printer<const sp: bool = true>(&'static OnceLock<Mutex<Internal>>); impl<const sp: bool> Printer<sp> { pub fn init(&self, endf: EndFlag) { let is_err = self.0.set(Mutex::new(Internal { buf: String::new(), endf, prvf: LineHead })).is_err(); if is_err { panic!("[@printer] Error: Second call of Printer::init"); } } fn get(&self) -> MutexGuard<Internal> { self.0.get().unwrap().lock().unwrap() } fn push(&self, v: impl PrinterDisplay) { self.get().push(v, sp); } pub fn print(&self) { self.get().print(); } } impl Internal { fn push(&mut self, v: impl PrinterDisplay, sp: bool) { let prvf = replace(&mut self.prvf, if sp {Space} else {NoSpace}); let buf = &mut self.buf; if prvf != LineHead && (prvf == Space || sp) { *buf += " "; } v.pdisp(sp, buf); } fn print(&mut self) { let prvf = replace(&mut self.prvf, LineHead); let buf = &mut self.buf; if prvf == LineHead { buf.pop(); } if buf.is_empty() { return; } if crate::mylib::SUBMISSION { println!("{buf}"); } else { eprint!("\x1b[32m"); for (i, s) in buf.split('\n').enumerate() { eprint!("{}", if i == 0 {">> "} else {" "}); println!("{s}"); } eprint!("\x1b[0m"); } buf.clear(); } } impl<T: PrinterDisplay, const sp: bool> Shl<T> for Printer<sp> { type Output = Self; fn shl(self, v: T) -> Self { self.push(v); self } } impl Not for Printer<true> { type Output = Printer<false>; fn not(self) -> Printer<false> { unsafe { transmute(self) } } } impl<const sp: bool> Shl<end> for Printer<sp> { type Output = Self; fn shl(self, _: end) -> Self { let mut itn = self.0.get().unwrap().lock().unwrap(); use EndFlag::*; match itn.endf { Print => { itn.print(); } LineFeed => { itn.buf += "\n"; itn.prvf = LineHead; } DoNothing => {} } self } } trait PrinterDisplay { fn pdisp(&self, sp: bool, buf: &mut String); } macro_rules! fall { ($($t:ty),+) => { $( impl PrinterDisplay for $t { fn pdisp(&self, _: bool, buf: &mut String) { *buf += &format!("{self}"); } } )+ }; } fall!( u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, f32, f64/* , ac_library::ModInt998244353, ac_library::ModInt1000000007 */); impl PrinterDisplay for char { fn pdisp(&self, _: bool, buf: &mut String) { buf.push(*self); } } impl PrinterDisplay for &str { fn pdisp(&self, _: bool, buf: &mut String) { buf.push_str(self); } } impl PrinterDisplay for &String { fn pdisp(&self, _: bool, buf: &mut String) { buf.push_str(self); } } impl PrinterDisplay for bool { fn pdisp(&self, _: bool, buf: &mut String) { *buf += if *self {"Yes"} else{ "No" }; } } impl<T: PrinterDisplay> PrinterDisplay for &[T] { fn pdisp(&self, sp: bool, buf: &mut String) { for e in *self { e.pdisp(sp, buf); if sp { *buf += " "; } } if sp && !self.is_empty() { buf.pop(); } } } } pub mod traits { pub trait Grid: Sized + Copy { type Rhs: Copy; const LRUD: [Self::Rhs; 4]; fn add_grid(self, rhs: Self::Rhs) -> Self; fn lrud(self) -> [Self; 4]; } impl Grid for [usize; 2] { type Rhs = [isize; 2]; const LRUD: [Self::Rhs; 4] = [[0, -1], [0, 1], [-1, 0], [1, 0]]; fn add_grid(mut self, rhs: Self::Rhs) -> Self { for i in 0..2 { self[i] = self[i].wrapping_add_signed(rhs[i]); } self } fn lrud(self) -> [Self; 4] { Self::LRUD.map(|d| self.add_grid(d)) } } impl Grid for [usize; 3] { type Rhs = [isize; 3]; const LRUD: [Self::Rhs; 4] = unimplemented!(); fn add_grid(mut self, rhs: Self::Rhs) -> Self { for i in 0..3 { self[i] = self[i].wrapping_add_signed(rhs[i]); } self } fn lrud(self) -> [Self; 4] { unimplemented!() } } pub trait CharUtil: Clone { const lower: [Self; 26]; const upper: [Self; 26]; fn lower_to_us(self) -> usize; fn upper_to_us(self) -> usize; fn flip(self) -> Self; fn as_lrud(self) -> usize; } impl CharUtil for char { const lower: [char; 26] = { let (mut out, mut i) = (['_'; 26], 0); while i < 26 { out[i] = (i+97) as u8 as char; i += 1; } out }; const upper: [char; 26] = { let (mut out, mut i) = (['_'; 26], 0); while i < 26 { out[i] = (i+65) as u8 as char; i += 1; } out }; fn lower_to_us(self) -> usize { debug_assert!('a' <= self && self <= 'z'); self as usize - 97 } fn upper_to_us(self) -> usize { debug_assert!('A' <= self && self <= 'Z'); self as usize - 65 } fn flip(self) -> Self { (self as u8 ^ 32) as char } fn as_lrud(mut self) -> usize { self = self.to_ascii_uppercase(); ['L', 'R', 'U', 'D'].into_iter().position(|v| v == self).unwrap() } } pub trait IntUtil: Copy { fn bit(self, n: usize) -> bool; } impl IntUtil for usize { fn bit(self, n: usize) -> bool { self>>n & 1 == 1 } } } pub mod macros { #[macro_export] macro_rules! assume { ($cond:expr) => { if !$cond { unsafe { std::hint::unreachable_unchecked() } } }; } #[macro_export] macro_rules! epr { ($($args:tt)*) => { if !$crate::SUBMISSION { eprint!("\x1b[31m"); print!("{}", format!($($args)*).split('\n').map(|s| format!(">> {s}\n")).reduce(|acc,s| acc+&s).unwrap()); eprint!("\x1b[0m"); } } } #[macro_export] macro_rules! oj_local { ($oj:expr; $local:expr) => { if $crate::SUBMISSION { $oj } else { $local } }; } #[macro_export] macro_rules! nest { (void; $n:expr) => { vec![vec![]; $n] }; (void; $n:expr $(;$m:expr)+) => { vec![nest![void$(;$m)+]; $n] }; () => { vec![] }; ($e:expr; $n:expr) => { vec![$e; $n] }; ($e:expr; $n:expr $(;$m:expr)+) => { vec![nest![$e$(;$m)+]; $n] }; } #[macro_export] macro_rules! min { ($($vl:expr),+) => { [$($vl),+].into_iter().reduce(|x,y| if x <= y {x} else {y}).unwrap() } } #[macro_export] macro_rules! max { ($($vl:expr),+) => { [$($vl),+].into_iter().reduce(|x,y| if x >= y {x} else {y}).unwrap() } } #[macro_export] macro_rules! chmin { ($dst:expr; $v:expr) => { { let v = $v; if v < $dst { $dst = v; true } else { false } } }; ($dst:expr; $($vl:expr),+) => { crate::chmin!($dst; crate::min!($($vl),+)) } } #[macro_export] macro_rules! chmax { ($dst:expr; $v:expr) => { { let v = $v; if $dst < v { $dst = v; true } else { false } } }; ($dst:expr; $($vl:expr),+) => { crate::chmax!($dst; crate::max!($($vl),+)) } } /* macro_rules! impl_for { ($trait:ty; $($type:ty),+) => { $( impl $trait for $type {} )+ } } pub(crate) use impl_for; */ } pub mod func { use std::ops::{RangeBounds, Bound}; pub fn binary_search(low: usize, high: usize) -> Option<usize> { if 1 < high.wrapping_sub(low) { Some(low.wrapping_add(high)/2) } else { None } } pub fn to_bounds(range: impl RangeBounds<usize>, sup: usize) -> [usize; 2] { let mut l = match range.start_bound() { Bound::Included(&v) => v, Bound::Excluded(&v) => v+1, Bound::Unbounded => 0 }; let mut r = match range.end_bound() { Bound::Included(&v) => v+1, Bound::Excluded(&v) => v, Bound::Unbounded => sup }; if l >= r { l = 0; r = 0; } assert!(r <= sup, "valid: 0..{sup}, input: {l}..{r}"); [l, r] } pub(crate) fn join(s: impl Iterator<Item = String>) -> Option<String> { let mut res = s.into_iter().fold(String::new(), |mut acc, e| { acc += &e; acc += ", "; acc }); if res.is_empty() { return None; } res.truncate(res.len() - 2); Some(res) } } } } mod external { pub use { proconio::{ input, input_interactive, marker::{Bytes as bytes, Chars as chars, Usize1 as usize1, Isize1 as isize1} }, }; }