結果
| 問題 | No.3513 Greedy Yokan Party |
| コンテスト | |
| ユーザー |
 Solalyth
|
| 提出日時 | 2026-07-23 20:07:20 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 33,248 bytes |
| 記録 | |
| コンパイル時間 | 1,001 ms |
| コンパイル使用メモリ | 218,080 KB |
| 実行使用メモリ | 7,604 KB |
| 最終ジャッジ日時 | 2026-07-23 20:07:32 |
| 合計ジャッジ時間 | 5,792 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 2 WA * 24 |
コンパイルメッセージ
warning: unused variable: `k`
--> src/main.rs:39:13
|
39 | for k in 0..2 {
| ^ help: if this is intentional, prefix it with an underscore: `_k`
|
= note: `#[warn(unused_variables)]` (part of `#[warn(unused)]`) on by default
ソースコード
#![allow(unused_must_use, non_snake_case, unused_labels, unused_imports, non_upper_case_globals)]
use external::*;
use cplib::prelude::*;
use nest as vec;
const INTERACTIVE: bool = false;
// const INTERACTIVE: bool = true; use input_interactive as input;
// #[allow(unused)] type Mint = ac_library::ModInt998244353;
// #[allow(unused)] macro_rules! fp { ($x:expr) => { Mint::new($x) }; }
fn solve() {
input! {
N: usize, L: u64, K: usize, mut A: [u64; N]
}
A.insert(0, 0);
A.push(L);
let (mut ok, mut ng) = (0, L);
while ng-ok > 1 {
let mid = (ok+ng)/2;
let mut dp = vec![0; 2; N+2];
dp[1][0] = -1<<30;
let mut s = 0;
for i in 0..N+1 {
while s+1 <= N && A[i+1] >= mid + A[s+1] { s += 1; }
if A[i+1] - A[s] >= mid {
for k in 0..2 {
chmax!(dp[k][i+1]; dp[k][s]+1);
}
}
chmax!(dp[1][i+1]; dp[0][i]);
for k in 0..2 {
chmax!(dp[k][i+1]; dp[k][i]);
}
}
epr!("bs {ok} {mid} {ng}");
for k in 0..2 {
epr!("{:?}", dp[k]);
}
if K <= dp[1][N+1] as usize { ok = mid; } else { ng = mid; }
}
out << ok;
}
fn main() {
out::init(INTERACTIVE || LOCAL);
let _T = 1;
// input! { _T: usize }
for _ in 0.._T { solve(); }
out::print();
}
mod external { pub use { proconio::{ input, input_interactive, marker::{Chars as chars, Usize1 as usize1} }, itertools::{Itertools, iproduct}, num::integer::{gcd, lcm, Roots}, }; }
// my library: https://github.com/solalyth/cplib-rs
mod cplib { #![allow(unused_macros, dead_code)] pub const LOCAL: bool = false; pub mod prelude { pub use std::{ collections::{VecDeque, HashMap, HashSet, BTreeMap, BTreeSet, BinaryHeap}, cmp::{Ordering, Reverse}, mem::{replace, take} }; pub use crate::cplib::{ *, LOCAL, ds::{segtree::*, csr::{CSR, Edge}}, algo::func::*, traits::prelude::*, util::output::{out, end}, }; } pub mod ds { pub mod unionfind { use std::fmt::Debug; pub trait Abelian { type T: Clone + Eq; fn e() -> Self::T; fn add(l: &Self::T, r: &Self::T) -> Self::T; fn inv(x: &Self::T) -> Self::T; fn sub(l: &Self::T, r: &Self::T) -> Self::T { Self::add(l, &Self::inv(r)) } } pub struct Xor; impl Abelian for Xor { type T = bool; fn e() -> bool { false } fn add(l: &bool, r: &bool) -> bool { l^r } fn inv(x: &bool) -> bool { *x } } pub struct UnionFind<Op: Abelian> { par: Vec<usize>, size: Vec<usize>, diff: Vec<Op::T>, next: Vec<usize> } impl UnionFind<Xor> { pub fn new_xor(len: usize) -> Self { Self::new(len) } } impl<Op: Abelian> UnionFind<Op> { pub fn new(len: usize) -> Self { UnionFind { par: (0..len).collect(), size: vec![1; len], diff: vec![Op::e(); len], next: (0..len).collect() } } pub fn clear(&mut self) { for i in 0..self.len() { self.par[i] = i; self.size[i] = 1; self.diff[i] = Op::e(); self.next[i] = i; } } pub fn len(&self) -> usize { self.par.len() } pub fn leader(&mut self, i: usize) -> usize { loop { let p = self.par[i]; let g = self.par[p]; if p == g { return g; } self.diff[i] = Op::add(&self.diff[i], &self.diff[p]); self.par[i] = g; } } 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) -> Op::T { assert!(self.is_same(i, j)); Op::sub(&self.diff[i], &self.diff[j]) } pub fn merge(&mut self, i: usize, j: usize, mut w: Op::T) -> (usize, usize) { let (mut old, mut new) = (self.leader(i), self.leader(j)); w = Op::sub(&Op::add(&w, &self.diff[j]), &self.diff[i]); if old == new { return if w == Op::e() { (old, !0) } else { (!0, !0) } } if !(self.size[old] <= self.size[new]) { (old, new) = (new, old); w = Op::inv(&w); } self.par[old] = new; self.diff[old] = w; self.size[new] += self.size[old]; self.next.swap(i, j); (new, old) } pub fn size_undo(&self, new: usize, old: usize) -> (usize, usize) { (self.size[new] - self.size[old], self.size[old]) } pub fn groups(&mut self) -> Vec<Vec<usize>> { let mut res = vec![vec![]; self.len()]; for i in 0..self.len() { res[self.leader(i)].push(i); } res } pub fn group(&self, i: usize) -> Vec<usize> { let (mut res, mut j) = (vec![i], self.next[i]); while j != i { res.push(j); j = self.next[j]; } res } pub fn leaders(&self) -> Vec<usize> { (0..self.len()).filter(|&i| self.par[i] == i).collect() } } impl<Op: Abelian> Clone for UnionFind<Op> { fn clone(&self) -> Self { Self { par: self.par.clone(), size: self.size.clone(), diff: self.diff.clone(), next: self.next.clone() } } } impl<Op: Abelian> std::fmt::Debug for UnionFind<Op> where Op::T: Debug { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { let mut s = String::new(); for g in self.clone().groups() { if !g.is_empty() { s += &format!("{g:?}, "); } } write!(f, "[ {} ]", &s[..s.len()-2]) } } } pub mod segtree { use std::{fmt::Debug, mem::replace, ops::Index, slice::SliceIndex}; #[allow(unused_variables)] pub trait SegtreeOp: Sized { const BEATS: bool = false; type Value: Clone; type Lazy: Clone; fn id_value() -> Self::Value; fn prod_value(lhs: &Self::Value, rhs: &Self::Value) -> Self::Value; fn id_lazy() -> Self::Lazy; fn prod_lazy(lazy: &mut Self::Lazy, ad: &Self::Lazy) {} fn act(value: &mut Self::Value, lazy: &Self::Lazy) {} fn act_beats(value: &mut Self::Value, lazy: &Self::Lazy) -> bool { panic!() } fn segtree_new(len: usize) -> Segtree<Self> { Segtree::new(len) } fn segtree_from_iter(iter: impl IntoIterator<IntoIter: ExactSizeIterator<Item = impl std::borrow::Borrow<Self::Value>>>) -> Segtree<Self> { let iter = iter.into_iter(); let mut seg = Segtree::new(iter.len()); let len = seg.len(); for (i, v) in iter.enumerate() { seg.tree[len+i] = v.borrow().clone(); } for i in (1..len).rev() { seg.update(i); } seg } } pub struct Segtree<Op: SegtreeOp> { pub tree: Vec<Op::Value>, pub lazy: Vec<Op::Lazy>, dep: u32 } impl<Op: SegtreeOp> Segtree<Op> { pub fn new(len: usize) -> Self { let dep = (len.max(2)-1).ilog2() + 2; Segtree { tree: vec![Op::id_value(); 1<<dep], lazy: vec![Op::id_lazy(); 1<<dep], dep } } pub fn len(&self) -> usize { 1 << self.dep-1 } pub fn get(&mut self, mut i: usize) -> &Op::Value { i += self.len(); for j in (1..self.dep).rev() { self.push(i >> j); } &self.tree[i] } pub fn set(&mut self, mut i: usize, x: Op::Value) { i += self.len(); for j in (1..self.dep).rev() { self.push(i >> j); } self.tree[i] = x; for j in 1..self.dep { self.update(i >> j); } } pub fn set_with<T>(&mut self, mut i: usize, f: impl FnOnce(&mut Op::Value) -> T) -> T { i += self.len(); for j in (1..self.dep).rev() { self.push(i >> j); } let res = f(&mut self.tree[i]); for j in 1..self.dep { self.update(i >> j); } res } pub fn push_all(&mut self) { for i in 1..self.len() { self.push(i); } } pub fn fold(&mut self, mut l: usize, mut r: usize) -> Op::Value { l += self.len(); r = (r+self.len()).min(self.len()*2); if l >= r { return Op::id_value(); } let (mut vl, mut vr) = (Op::id_value(), Op::id_value()); for i in (1..self.dep).rev() { self.push(l >> i); self.push(r-1 >> i); } while l < r { if l&1 == 1 { vl = Op::prod_value(&vl, &self.tree[l]); l += 1; } if r&1 == 1 { vr = Op::prod_value(&self.tree[r-1], &vr); } l >>= 1; r >>= 1; } Op::prod_value(&vl, &vr) } pub fn apply(&mut self, mut l: usize, mut r: usize, lazy: Op::Lazy) { l += self.len(); r = (r+self.len()).min(self.len()*2); if l >= r { return; } for i in (1..self.dep).rev() { self.push(l >> i); self.push(r-1 >> i); } let (mut s, mut t) = (l, r); while s < t { if s&1 == 1 { self.node_apply(s, &lazy); s += 1; } if t&1 == 1 { t -= 1; self.node_apply(t, &lazy); } s >>= 1; t >>= 1; } for i in 1..self.dep { if ((l >> i) << i) != l { self.update(l >> i); } if ((r >> i) << i) != r { self.update(r-1 >> i); } } } pub fn max_right(&mut self, l: usize, r_max: usize, f: impl Fn(&Op::Value) -> bool) -> usize { assert!(l <= self.len()); if l == self.len() { return self.len().min(r_max); } let (mut r, mut val) = (l + self.len(), Op::id_value()); for i in (1..self.dep).rev() { self.push(r >> i); } loop { while r&1 == 0 { r >>= 1; } let tmp = Op::prod_value(&val, &self.tree[r]); if !f(&tmp) { break; } val = tmp; r += 1; if r & r-1 == 0 { return self.len().min(r_max); } } while r < self.len() { self.push(r); r *= 2; let tmp = Op::prod_value(&val, &self.tree[r]); if f(&tmp) { val = tmp; r += 1; } } (r - self.len()).min(r_max) } 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.dep).rev() { self.push(l-1 >> i); } loop { l -= 1; while l != 1 && l&1 == 1 { l >>= 1; } let tmp = Op::prod_value(&self.tree[l], &val); if !f(&tmp) { break; } val = tmp; if l & l-1 == 0 { return 0; } } while l < self.len() { self.push(l); l = 2*l + 1; let tmp = Op::prod_value(&self.tree[l], &val); if f(&tmp) { val = tmp; l -= 1; } } l+1 - self.len() } fn node_apply(&mut self, i: usize, lazy: &Op::Lazy) { Op::prod_lazy(&mut self.lazy[i], lazy); if Op::BEATS { if !Op::act_beats(&mut self.tree[i], lazy) { self.push(i); self.update(i); } } else { Op::act(&mut self.tree[i], lazy); } } fn push(&mut self, i: usize) { debug_assert!(i < self.len()); if std::any::type_name::<Op::Lazy>() == "()" { return; } let lazy = replace(&mut self.lazy[i], Op::id_lazy()); self.node_apply(2*i, &lazy); self.node_apply(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]); } } impl<Op: SegtreeOp> Clone for Segtree<Op> { fn clone(&self) -> Self { Self { tree: self.tree.clone(), lazy: self.lazy.clone(), dep: self.dep.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(); seg.push_all(); write!(f, "{:?}", &seg.tree[self.len()..]) } } impl<Op: SegtreeOp, I: SliceIndex<[Op::Value]>> Index<I> for Segtree<Op> { type Output = I::Output; fn index(&self, index: I) -> &Self::Output { Index::index(&self.tree[self.len()..], index) } } } pub mod csr { use std::{fmt::Debug, ops::{Index, IndexMut}}; #[derive(Clone)] pub struct CSR<T> { dat: Vec<T>, idx: Vec<usize>, } pub type Edge = CSR<usize>; impl Edge { pub fn from_edges(n: usize, und: bool, rev: bool, uv: &[(usize, usize)]) -> Self { if rev { Self::from_edges_iter(n, und, uv.iter().map(|e| (e.1, e.0))) } else { Self::from_edges_iter(n, und, uv.iter().cloned()) } } pub fn from_edges_iter(n: usize, und: bool, iter: impl IntoIterator<Item = (usize, usize)> + Clone) -> Self { let mut idx = vec![0; n+2]; for (i, j) in iter.clone() { idx[i+2] += 1; if und { idx[j+2] += 1; } } for i in 0..=n { idx[i+1] += idx[i]; } let mut dat = vec![0; idx.pop().unwrap()]; for (i, j) in iter { dat[idx[i+1]] = j; idx[i+1] += 1; if und && i != j { dat[idx[j+1]] = i; idx[j+1] += 1; } } Self { dat, idx } } } impl<T> CSR<T> { pub fn new() -> Self { Self { dat: vec![], idx: vec![0] } } pub fn idx_len(&self) -> usize { self.idx.len()-1 } pub fn dat_len(&self) -> usize { self.dat.len() } pub fn push(&mut self, x: T) { self.dat.push(x); *self.idx.last_mut().unwrap() += 1; } pub fn next_vec(&mut self) { self.idx.push(self.dat.len()); } pub fn sort(&mut self) where T: Ord { for i in 0..self.idx_len() { self.dat[self.idx[i]..self.idx[i+1]].sort_unstable(); } } pub fn contains(&self, u: usize, x: &T) -> bool where T: Ord { self[u].binary_search(x).is_ok() } } impl<T> Index<usize> for CSR<T> { type Output = [T]; fn index(&self, i: usize) -> &Self::Output { &self.dat[self.idx[i]..self.idx[i+1]] } } impl<T> IndexMut<usize> for CSR<T> { fn index_mut(&mut self, i: usize) -> &mut Self::Output { &mut self.dat[self.idx[i]..self.idx[i+1]] } } impl<T: Clone + Debug> Debug for CSR<T> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { let mut s = String::new(); for i in 0..self.idx_len() { s += &format!("{i}: [, "); for x in &self[i] { s.pop(); s.pop(); s += &format!("{x:?}, "); } s.pop(); s.pop(); s += "], "; } s.pop(); s.pop(); write!(f, "{{ {s} }}") } } } pub mod trie { use std::fmt::Debug; const MASK: usize = (1<<32)-1; pub struct Trie<const W: usize> { dat: Vec<usize>, } impl<const W: usize> Trie<W> { pub fn new() -> Self { Self { dat: vec![!0; W+1] } } pub fn len(&self) -> usize { self.dat.len() / (W+1) } pub fn clear(&mut self) { self.dat.truncate(W+1); } pub fn parent(&self, idx: usize) -> (usize, usize) { assert!(idx != 0 && idx < self.len()); let t = self.dat[(W+1)*idx+W]; (t & MASK, t >> 32) } pub fn check_next(&self, idx: usize, c: usize) -> usize { assert!(idx < self.len() && c < W); self.dat[(W+1)*idx+c] } pub fn next(&mut self, idx: usize, c: usize) -> usize { assert!(idx < self.len() && c < W); if self.dat[(W+1)*idx+c] == !0 { let nx = self.len(); for _ in 0..W+1 { self.dat.push(!0); } self.dat[(W+1)*idx+c] = nx; self.dat[(W+1)*nx+W] = (c<<32) + idx; } self.dat[(W+1)*idx+c] } pub fn insert(&mut self, iter: impl IntoIterator<Item = usize>) -> Vec<usize> { let mut res = vec![0]; let mut cur = 0; for c in iter { cur = self.next(cur, c); res.push(cur); } res } pub fn aho_corasick(&self) -> AhoCorasick<W> { let mut dat = vec![0; (W+1)*self.len()]; let mut stk = std::collections::VecDeque::from([0]); while let Some(i) = stk.pop_front() { for c in 0..W { let (j, fj) = (self.dat[(W+1)*i+c], dat[(W+1)*dat[(W+1)*i+W]+c]); if j != !0 { dat[(W+1)*j+W] = fj; dat[(W+1)*i+c] = j; stk.push_back(j); } else { dat[(W+1)*i+c] = fj; } } } AhoCorasick { trie_len: self.len(), dat } } } impl<const W: usize> Debug for Trie<W> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { assert!(W <= 26); let mut s = vec![String::from("(deleted)"); self.len()]; s[0].clear(); for i in 0..self.len() { if &s[i] == "(deleted)" { continue; } for c in 0..W { let j = self.dat[(W+1)*i+c]; if j == !0 { continue; } s[j] = format!("{}{}", s[i], (b'a' + c as u8) as char); } } let mut res = String::new(); for s in &s[1..] { res += ", "; res += s; } write!(f, "[(empty){res}]") } } pub struct AhoCorasick<const W: usize> { trie_len: usize, dat: Vec<usize>, } impl<const W: usize> AhoCorasick<W> { pub fn next(&self, idx: usize, c: usize) -> usize { assert!(idx < self.trie_len && c < W); self.dat[(W+1)*idx+c] } pub fn fail(&self, idx: usize) -> usize { assert!(idx < self.trie_len); self.dat[(W+1)*idx+W] } } } } pub mod algo { pub mod func { pub fn next_permutation<T: Ord>(v: &mut [T]) -> bool { let Some(i) = v.windows(2).rposition(|w| w[0] < w[1]) else { return false; }; let j = v.iter().rposition(|e| e > &v[i]).unwrap(); v.swap(i, j); v[i+1..].reverse(); true } pub fn prev_permutation<T: Ord>(v: &mut [T]) -> bool { let Some(i) = v.windows(2).rposition(|w| w[0] > w[1]) else { return false; }; let j = v.iter().rposition(|e| e < &v[i]).unwrap(); v.swap(i, j); v[i+1..].reverse(); true } pub fn run_length<T: Eq>(iter: impl IntoIterator<Item = T>) -> Vec<(T, usize)> { let mut res = vec![]; for t in iter { let Some(l) = res.last_mut() else { res.push((t, 1)); continue; }; if t == l.0 { l.1 += 1; } else { res.push((t, 1)); } } res } pub fn prefix_fold<T, U>(iter: impl IntoIterator<Item = U>, init: T, mut f: impl FnMut(&T, U) -> T) -> Vec<T> { let mut res = vec![init]; for u in iter { res.push(f(res.last().unwrap(), u)); } res } pub fn suffix_fold<T, U>(iter_rev: impl IntoIterator<Item = U>, init: T, mut f: impl FnMut(&T, U) -> T) -> Vec<T> { let mut res = vec![init]; for u in iter_rev { res.push(f(res.last().unwrap(), u)); } res.reverse(); res } #[macro_export] macro_rules! binary_search { ($low:expr, $high:expr) => { if 1<$high.wrapping_sub($low) { Some($high.wrapping_add($low)/2) } else { None } } } } } pub mod graph { } pub mod math { pub mod func { #[macro_export] macro_rules! gcd { ($a:expr, $b:expr) => {{ let (mut a, mut b) = ($a, $b); while b != 0 { (a, b) = (b, a%b); } a }}; ($($x:expr),+) => {{ let mut res = 0; $( res = gcd!(res, $x); )* res }} } #[macro_export] macro_rules! lcm { ($a:expr, $b:expr) => {{ let (a, b) = ($a, $b); if (a, b) == (0, 0) { 0 } else { (a/gcd!(a, b)).saturating_mul(b) } }}; } #[macro_export] macro_rules! extgcd { ($a:expr, $b:expr) => {{ let (a, b) = ($a, $b); let (mut p0, mut q0, mut r0, mut p1, mut q1, mut r1) = (a.signum(), 0, a.abs(), 0, b.signum(), b.abs()); while r1 != 0 { let t = r0/r1; (p0, q0, r0, p1, q1, r1) = (p1, q1, r1, p0 - t*p1, q0 - t*q1, r0 - t*r1); } (p0, q0, r0) }}; } pub fn bezout(mut a: i64, mut b: i64, mut c: i64) -> Option<(i64, i64, i64, i64)> { assert!(b != 0 && a.abs().max(b.abs()) < 3.03e9 as i64); let (x, _, g) = extgcd!(a, b); if c%g != 0 { return None; } (a, b, c) = (a/g, b/g, c/g); let x = (c%b*x).rem_euclid(b); Some((x, (c-a*x)/b, b.abs(), -a*b.signum())) } #[macro_export] macro_rules! modpow { ($x:expr, $n:expr, $m:expr) => {{ let (mut x, mut n, m) = ($x, $n, $m); x %= m; let mut res = 1; while n != 0 { if n & 1 == 1 { res = res * x % m; } x = x * x % m; n /= 2; } res%m }}; } pub fn into_ary(mut n: u64, base: u64) -> Vec<u64> { let mut res = vec![]; while n != 0 { res.push(n%base); n /= base; } res } pub fn from_ary(d: &[u64], base: u64) -> u64 { let mut res = 0; for &d in d { res = res*base + d; } res } pub fn rational(mut p: i128, mut q: i128) -> (i128, i128) { assert!((p, q) != (0, 0)); if q != 0 { if q < 0 { (p, q) = (-p, -q); } let g = gcd!(p.abs(), q.abs()); (p/g, q/g) } else { (1, 0) } } pub fn into_uv([x, y]: [i128; 2], p: i128, q: i128) -> [i128; 2] { [q*x+p*y, q*y-p*x] } pub fn safe_binom(n: usize, mut k: usize) -> usize { if n < k { return 0; } if n-k < k { k = n-k; } let mut r = 1usize; for i in 0..k { if let Some(x) = r.checked_mul(n-i) { r = x/(i+1); } else { return 1<<60; } } r } } pub mod lpf_sieve { use std::ops::{Add, Sub}; const MASK: usize = (1<<16)-1; pub struct LpfSieve { primes: Vec<usize>, table: Vec<usize>, } impl LpfSieve { pub fn new(mut max: usize) -> Self { assert!(max <= 1e7 as usize); max = max.max(10); let mut primes = vec![]; let mut table = vec![0; max+1]; for i in 2..=max { let lpf = if table[i] == 0 { primes.push(i); table[i] = (1<<32) + (1<<16); i } else { table[i] & MASK }; for &p in &primes { if !(p <= lpf && i*p <= max) { break; } table[i*p] = if lpf == p { table[i] + (1<<16) | p } else { (i<<32) + (1<<16) + p }; } } Self { primes, table } } fn max(&self) -> usize { self.table.len()-1 } pub fn primes(&self) -> &[usize] { &self.primes } pub fn is_prime(&self, n: usize) -> bool { assert!(1 <= n && n <= self.max().pow(2)); if n <= self.max() { n != 1 && self.table[n]&MASK == 0 } else { for &p in &self.primes { if n%p == 0 { return true; } if n < p*p { break; } } false } } pub fn lpf(&self, n: usize) -> usize { assert!(2 <= n); let t = self.table[n] & MASK; if t == 0 { n } else { t } } fn data(&self, n: usize) -> (usize, usize, usize) { debug_assert!(2 <= n); if self.table[n] & MASK == 0 { (n, 1, 1) } else { (self.table[n] & MASK, self.table[n]>>16 & MASK, self.table[n]>>32) } } pub fn fold<T>(&self, mut n: usize, mut init: T, mut vpe: impl FnMut(&mut T, usize, usize)) -> T { assert!(n != 0); while n != 1 { let (lpf, exp, nx) = self.data(n); vpe(&mut init, lpf, exp); n = nx; } init } pub fn fact(&self, mut n: usize) -> Vec<(usize, usize)> { assert!(1 <= n && n <= self.max().pow(2)); if n <= self.max() { self.fold(n, vec![], |v, p, e| { v.push((p, e)); }) } else { let mut res = vec![]; for &p in &self.primes { let mut cnt = 0; while n%p == 0 { cnt += 1; n /= p; } if cnt != 0 { res.push((p, cnt)); } if n < p*p { break; } } if n != 1 { res.push((n, 1)); } res } } pub fn divisors(&self, n: usize) -> Vec<usize> { let mut res = vec![1]; for (p, e) in self.fact(n) { for i in 0..res.len() { let mut k = res[i]; for _ in 0..e { k *= p; res.push(k); } } } res } pub fn totient_point(&self, n: usize) -> usize { self.fold(n, n, |v, p, _| { *v -= *v/p; }) } pub fn totient(&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_point(&self, n: usize) -> i64 { self.fold(n, 1, |v, _, e| { *v = if e == 1 { -*v } else { 0 }; }) } pub fn mobius(&self, n: usize) -> Vec<i64> { let mut res = vec![0; n+1]; res[1] = 1; for i in 2..=n { let (_, exp, nx) = self.data(i); if exp == 1 { res[i] = -res[nx]; } } res } pub fn div_zeta<T: Copy + Add<Output = T>>(&self, mut f: Vec<T>) -> Vec<T> { let vl = f.len()-1; for &p in self.primes() { if vl < p { break; } for i in 1..=vl/p { f[i*p] = f[i*p] + f[i]; } } f } pub fn div_mobius<T: Copy + Sub<Output = T>>(&self, mut g: Vec<T>) -> Vec<T> { let vl = g.len()-1; for &p in self.primes() { if vl < p { break; } for i in (1..=vl/p).rev() { g[i*p] = g[i*p] - g[i]; } } g } pub fn mul_zeta<T: Copy + Add<Output = T>>(&self, mut f: Vec<T>) -> Vec<T> { let vl = f.len() - 1; for &p in self.primes() { if vl < p { break; } for i in (1..=vl/p).rev() { f[i] = f[i] + f[i*p]; } } f } pub fn mul_mobius<T: Copy + Sub<Output = T>>(&self, mut g: Vec<T>) -> Vec<T> { let vl = g.len() - 1; for &p in self.primes() { if vl < p { break; } for i in 1..=vl/p { g[i] = g[i] - g[i*p]; } } g } } } pub mod modtable { static mut P: usize = 0; static mut INV: Vec<usize> = vec![]; static mut F: Vec<usize> = vec![]; static mut FINV: Vec<usize> = vec![]; macro_rules! a { ($n:expr, $x:expr) => {{ _O::calc($n); unsafe {$x} }} } pub const O: _O = _O; pub struct _O; #[allow(non_snake_case, static_mut_refs)] impl _O { pub fn init(&self, p: usize) { unsafe { if p == P { return; } (P, INV, F, FINV) = (p, vec![0, 1], vec![1, 1], vec![1, 1]); } _O::calc(1000); } fn calc(mut n: usize) { unsafe { let len = F.len(); if n < len { return; } assert!(n < P); n = n.max(len*2)+1; for i in len..n { INV.push(P - (P/i*INV[P%i] % P)); F.push(F[i-1]*i % P); FINV.push(FINV[i-1]*INV[i] % P); } } } pub fn P(&self, n: usize, k: usize) -> usize { if n < k { 0 } else { a!(n, F[n]*FINV[n-k]%P) } } pub fn C(&self, n: usize, k: usize) -> usize { if n < k { 0 } else { a!(n, F[n]*FINV[k]%P*FINV[n-k]%P) } } pub fn MC<const N: usize>(&self, k: [usize; N]) -> usize { let s = k.iter().sum::<usize>(); a!(s, k.iter().fold(F[s], |t, &k| t*FINV[k]%P)) } pub fn color(&self, n: usize, col: usize) -> usize { if n == 0 { 1 } else { O.C(col+n-1, n) } } pub fn F(&self, n: usize) -> usize { a!(n, F[n]) } pub fn FINV(&self, n: usize) -> usize { a!(n, FINV[n]) } pub fn INV(&self, n: usize) -> usize { a!(n, INV[n]) } pub fn MOD(&self) -> usize { unsafe { P } } } } } pub mod const_fp { } pub mod traits { pub mod prelude { pub use super::{ iter_util::*, int_util::*, grid::*, char_util::*, vec_util::*, vec_split::*, }; } pub mod iter_util { pub trait IterUtil { type T; fn into_vec(self) -> Vec<Self::T>; fn count_if(self, f: impl FnMut(Self::T) -> bool) -> usize; } impl<T, U: Iterator<Item = T>> IterUtil for U { type T = T; fn into_vec(self) -> Vec<Self::T> { self.collect() } fn count_if(self, mut f: impl FnMut(T) -> bool) -> usize { let mut t = 0; for x in self { if f(x) { t += 1; } } t } } } pub mod int_util { pub fn ceil<T: IntUtil>(l: T, r: T) -> T { l.ceil(r).0 } pub fn ceil_rem<T: IntUtil>(l: T, r: T) -> T { l.ceil(r).1 } pub trait IntUtil: Sized { fn floor(self, rhs: Self) -> (Self, Self); fn ceil(self, rhs: Self) -> (Self, Self); fn width(self) -> Option<usize>; } macro_rules! int { ($($t:ty),+) => {$( impl IntUtil for $t { fn floor(self, rhs: Self) -> ($t, $t) { assert!(0 < rhs); let (q, r) = (self/rhs, self%rhs); if r < 0 { (q-1, r+rhs) } else { (q, r) } } fn ceil(self, rhs: Self) -> ($t, $t) { assert!(0 < rhs); let (q, r) = (self/rhs, self%rhs); if 0 < r { (q+1, rhs-r) } else { (q, -r) } } fn width(self) -> Option<usize> { unimplemented!() } } )+}; } int!(i32, i64, i128, isize); macro_rules! uint { ($($t:ty),+) => {$( impl IntUtil for $t { fn floor(self, rhs: Self) -> ($t, $t) { (self/rhs, self%rhs) } fn ceil(self, rhs: Self) -> ($t, $t) { let q = (self+rhs-1)/rhs; (q, q*rhs-self) } fn width(self) -> Option<usize> { if self == 0 {None} else {Some((Self::BITS-self.leading_zeros()-1) as usize)} } } )+}; } uint!(u32, u64, u128, usize); } pub mod grid { pub trait Grid: Copy + Default { const AROUND: [[i64; 2]; 8] = [[0, -1], [0, 1], [-1, 0], [1, 0], [-1, -1], [-1, 1], [1, -1], [1, 1]]; fn add(self, rhs: [i64; 2]) -> Self; fn add_char(self, c: char, n: i64) -> Self { let mut d = Self::AROUND[match c { 'L' => 2, 'R' => 3, 'U' => 1, 'D' => 0, _ => unreachable!() }]; d[0] *= n; d[1] *= n; self.add(d) } fn around4(self) -> [Self; 4] { let mut res = [Default::default(); 4]; for i in 0..4 { res[i] = self.add(Self::AROUND[i]); } res } fn around8(self) -> [Self; 8] { let mut res = [Default::default(); 8]; for i in 0..8 { res[i] = self.add(Self::AROUND[i]); } res } fn rotate(self, n: usize, m: usize, t: i64) -> Self; } impl Grid for [usize; 2] { fn add(mut self, rhs: [i64; 2]) -> Self { for i in 0..2 { self[i] = self[i].wrapping_add_signed(rhs[i] as isize); } self } fn rotate(self, h: usize, w: usize, t: i64) -> Self { let [i, j] = self; match t.rem_euclid(4) { 0 => [i, j], 1 => [j, h-1-i], 2 => [h-1-i, w-1-j], 3 => [w-1-j, i], _ => unreachable!() } } } impl Grid for [i64; 2] { fn add(mut self, rhs: [i64; 2]) -> Self { for i in 0..2 { self[i] += rhs[i]; } self } fn rotate(self, _: usize, _: usize, _: i64) -> Self { unimplemented!() } } } pub mod char_util { pub trait CharUtil: Clone { const LOWER: [Self; 26]; const UPPER: [Self; 26]; const NUMBER: [Self; 10]; fn us(self) -> usize; #[must_use] fn flip(self) -> Self; } 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 }; const NUMBER: [char; 10] = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']; fn us(self) -> usize { if self <= '9' { self as usize - 48 } else { (self as usize & 31) - 1 } } fn flip(self) -> Self { (self as u8 ^ 32) as char } } } pub mod vec_util { pub trait VecUtil { type T; fn extend_len(&mut self, len: usize, e: Self::T) where Self::T: Clone; fn adj_merge(&mut self, f: impl FnMut(&mut Self::T, &mut Self::T) -> bool); } impl<T> VecUtil for Vec<T> { type T = T; fn extend_len(&mut self, len: usize, e: T) where T: Clone { if self.len() < len { self.resize(len, e); } } fn adj_merge(&mut self, mut f: impl FnMut(&mut Self::T, &mut Self::T) -> bool) { let mut l = 0; for r in 1..self.len() { let t = unsafe { let [sl, sr] = self.get_disjoint_unchecked_mut([l, r]); f(sl, sr) }; if !t { self.swap(l+1, r); l += 1; } } self.truncate(l+1); } } } pub mod vec_split { pub trait VecSplit { type Output; fn split(self) -> Self::Output; } impl<T0, T1> VecSplit for Vec<(T0, T1)> { type Output = (Vec<T0>, Vec<T1>); fn split(self) -> Self::Output { let mut res = (vec![], vec![]); for e in self { res.0.push(e.0); res.1.push(e.1); } res } } impl<T0, T1, T2> VecSplit for Vec<(T0, T1, T2)> { type Output = (Vec<T0>, Vec<T1>, Vec<T2>); fn split(self) -> Self::Output { let mut res = (vec![], vec![], vec![]); for e in self { res.0.push(e.0); res.1.push(e.1); res.2.push(e.2); } res } } } } pub mod util { pub mod output { #![allow(static_mut_refs, non_camel_case_types)] use std::{mem::replace, ops::{Not, Shl}, fmt::Write}; static mut BUFFER: Buffer = Buffer { buf: String::new(), endp: false, prev: Previous::LineHead }; pub struct Buffer { buf: String, endp: bool, prev: Previous, } impl Buffer { fn print(&mut self) { if replace(&mut self.prev, Previous::LineHead) == Previous::LineHead { self.buf.pop(); } if crate::cplib::LOCAL { eprint!("\x1b[32m"); if self.buf.is_empty() { eprintln!("(empty)"); } else { println!("{}", self.buf); } eprint!("\x1b[0m"); } else { if !self.buf.is_empty() { println!("{}", self.buf); } } self.buf.clear(); } fn space(&mut self, sp: bool) { let prev = replace(&mut self.prev, if sp {Previous::Space} else {Previous::NoSpace}); if (sp || prev == Previous::Space) && prev != Previous::LineHead { self.buf.push(' '); } } } #[derive(Clone, Copy)] pub struct out; pub struct out_usp; pub struct end; #[derive(PartialEq, Eq, Clone, Copy)] enum Previous { Space, NoSpace, LineHead, } impl out { pub fn init(endp: bool) { unsafe { BUFFER.buf.reserve(1<<24); BUFFER.endp = endp; } } pub fn print() { unsafe { BUFFER.print(); } } fn push<T: Primitive>(v: &T) { unsafe { BUFFER.space(true); v.fmt(&mut BUFFER.buf); } } pub fn sp() { unsafe { BUFFER.prev = Previous::Space; } } pub fn ln() { unsafe { BUFFER.buf.push('\n'); BUFFER.prev = Previous::LineHead; } } } impl out_usp { fn push<T: Primitive>(v: &T) { unsafe { BUFFER.space(false); v.fmt(&mut BUFFER.buf); } } } impl Not for out { type Output = out_usp; fn not(self) -> Self::Output { out_usp } } macro_rules! impl_outs { ($($t:ty),+) => { $( impl<T: Primitive> Shl<T> for $t { type Output = Self; fn shl(self, rhs: T) -> Self::Output { Self::push(&rhs); self } } impl Shl<end> for $t { type Output = Self; fn shl(self, _: end) -> Self::Output { unsafe { if BUFFER.endp { BUFFER.print(); } else { BUFFER.buf += "\n"; BUFFER.prev = Previous::LineHead; } } self } } )+ }; } impl_outs!(out, out_usp); macro_rules! impl_for_slices { ($($t:ty),+) => { $(impl_for_slices!($t; out, out_usp);)+ }; ($t:ty; $($u:ty),+) => { $( impl<T: Primitive> Shl<$t> for $u { type Output = Self; fn shl(self, rhs: $t) -> Self::Output { for v in rhs { Self::push(v); } self } } )+} } impl_for_slices!(&[T], &Vec<T>); trait Primitive { fn fmt(&self, buf: &mut String); } macro_rules! impl_primitive { ($($t:ty),+) => { $( impl Primitive for $t { fn fmt(&self, buf: &mut String) { write!(buf, "{self}").ok(); } } )+ } } impl_primitive!(char, u32, u64, u128, usize, i32, i64, i128, f32, f64, &str, &String, String); impl Primitive for u8 { fn fmt(&self, buf: &mut String) { buf.push(*self as char); } } impl Primitive for bool { fn fmt(&self, buf: &mut String) { *buf += if *self { "Yes" } else { "No" }; } } } pub mod macros { #[macro_export] macro_rules! nest { [void; $n:expr] => { std::vec![std::vec![]; $n] }; [void; $n:expr $(;$m:expr)+] => { std::vec![crate::nest![void$(;$m)+]; $n] }; [($ev:expr) for $i:tt in $rg:expr] => { $rg.into_iter().map(|$i| $ev).collect::<Vec<_>>() }; [$($v:expr),*] => { std::vec![$($v),*] }; [$e:expr; $n:expr] => { std::vec![$e; $n] }; [$e:expr; $n:expr $(;$m:expr)+] => { std::vec![crate::nest![$e $(;$m)+]; $n] }; } #[macro_export] macro_rules! min { ($x:expr, $y:expr) => {{ let (x, y) = ($x, $y); if x <= y { x } else { y } }}; ($($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_export] macro_rules! swap { ($l:expr, $r:expr) => { ($l, $r) = ($r, $l); }; } #[macro_export] macro_rules! prefix { ($init:expr, $v:expr) => {{ let mut res = vec![$init]; for x in $v.into_iter() { res.push(*res.last().unwrap()+x); } res }}; ($v:expr) => { prefix!(0, $v) } } #[macro_export] macro_rules! sum { ($init:expr, $v:expr) => {{ let mut res = $init; for x in $v.into_iter() { res += x; } res }}; ($v:expr) => { sum!(0, $v) } } #[macro_export] macro_rules! vadd { ($v:expr, -$x:expr) => {{ let x = $x; for e in &mut $v { *e -= x; } }}; ($v:expr, $x:expr) => {{ let x = $x; for e in &mut $v { *e += x; } }} } #[macro_export] macro_rules! o { ($t0:tt $t1:tt $t2:tt $x:expr) => { let t = $x; $t0 $t1 $t2 t; }; ($t0:tt $t1:tt $t2:tt $t3:tt $x:expr) => { let t = $x; $t0 $t1 $t2 $t3 t; }; } #[macro_export] macro_rules! init { ($map:tt[$key:expr] = $value:expr) => { $map.entry($key).or_insert_with(|| $value) }; ($map:tt[$key:expr]) => { $map.entry($key).or_insert_with(|| Default::default()) }; } #[macro_export] macro_rules! counter { ($map:expr, $key:expr, $x:expr) => {{ let k = $key; let x = $x + $map.get(&k).unwrap_or(&0); if 0 < x { $map.insert(k, x); } else { $map.remove(&k); } x }} } } pub mod func { use std::ops::{RangeBounds, Bound}; pub fn to_bounds(range: impl RangeBounds<usize>, sup: usize) -> [usize; 2] { let l = match range.start_bound() { Bound::Included(&v) => v, Bound::Excluded(&v) => v+1, Bound::Unbounded => 0 }; let r = match range.end_bound() { Bound::Included(&v) => v+1, Bound::Excluded(&v) => v, Bound::Unbounded => sup }.min(sup); if l >= r { [0, 0] } else { [l, r] } } } pub mod debug { pub fn replace_inf_and_truncate(s: String) -> String { s } pub fn debug_table<T: std::fmt::Debug>(_: &Vec<Vec<T>>, _: usize, _: usize) {} #[macro_export] macro_rules! epr { ($($args:tt)*) => {} } #[macro_export] macro_rules! oj_local { ($oj:expr, $local:expr) => { if $crate::LOCAL { $local } else { $oj } }; } #[macro_export] macro_rules! table { ($t:expr, $x:expr, $y:expr) => {}; ($t:expr) => {}; } } } }