QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #879303 | #9700. Ying’s Cup | ucup-team296# | TL | 684ms | 8832kb | Rust | 82.8kb | 2025-02-01 23:24:46 | 2025-02-01 23:24:47 |
Judging History
answer
// https://contest.ucup.ac/contest/1903/problem/9700
use crate::algo_lib::collections::slice_ext::indices::Indices;
use crate::algo_lib::collections::vec_ext::gen_vec::VecGen;
use crate::algo_lib::collections::vec_ext::inc_dec::IncDec;
use crate::algo_lib::graph::edges::edge_trait::EdgeTrait;
use crate::algo_lib::graph::lca::LCATrait;
use crate::algo_lib::graph::Graph;
use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::output::Output;
use crate::algo_lib::misc::recursive_function::{Callable2, RecursiveFunction2};
use crate::algo_lib::misc::test_type::TaskType;
use crate::algo_lib::misc::test_type::TestType;
use crate::algo_lib::numbers::mod_int::mod_utils::Combinations;
use crate::algo_lib::numbers::mod_int::prime_fft::PrimeFFT;
use crate::algo_lib::numbers::mod_int::ModIntF;
use crate::algo_lib::numbers::num_traits::algebra::{One, Zero};
type PreCalc = ();
fn solve(input: &mut Input, out: &mut Output, _test_case: usize, _data: &mut PreCalc) {
let n = input.read_size();
let edges = input.read_size_pair_vec(n - 1).dec();
type Mod = ModIntF;
let graph = Graph::with_biedges(n, &edges);
let lca = graph.lca();
let c = Combinations::<Mod>::new(n + 1);
let mut fft = PrimeFFT::<Mod>::new();
fn strip_zero(v: &mut Vec<Mod>) {
while !v.is_empty() && v.last().unwrap() == &Mod::zero() {
v.pop();
}
}
let mut mem = RecursiveFunction2::new(|
mem,
vert: usize,
edge: usize,
| -> Vec<(Vec<Mod>, Vec<Mod>)> {
if edge == graph[vert].len() {
vec![(vec![Mod::zero()], vec![Mod::one()])]
} else if Some(graph[vert][edge].to()) == lca.parent(vert) {
mem.call(vert, edge + 1)
} else {
let down = mem.call(graph[vert][edge].to(), 0);
let right = mem.call(vert, edge + 1);
let ps: Vec<(Vec<Mod>, Vec<Mod>)> = Vec::with_gen_prefix(
down.len() + 1,
|i, ps: &Vec<(Vec<Mod>, Vec<Mod>)>| {
if i == 0 {
(vec![Mod::zero(); down.len()], vec![Mod::zero(); down.len()])
} else {
let mut res = ps[i - 1].clone();
for j in 0..down.len() {
res.0[j]
+= down[i - 1].0.get(j).copied().unwrap_or(Mod::zero());
res.1[j]
+= down[i - 1].1.get(j).copied().unwrap_or(Mod::zero());
}
res
}
},
);
let mut res = Vec::with_gen(
down.len() + right.len(),
|_| {
(
vec![Mod::zero(); down.len() + right.len()],
vec![Mod::zero(); down.len() + right.len()],
)
},
);
let mut r01 = Vec::with_capacity(right.len());
let mut ps01 = Vec::with_capacity(down.len());
let mut psk = Vec::with_capacity(down.len() + 1);
let mut temp = vec![Mod::zero(); down.len() + right.len()];
for i in 0..right.len() {
for k in 0..=down.len() {
let mult = c.c(i + k, k)
* c.c(right.len() - 1 - i + down.len() - k, down.len() - k);
r01.clear();
r01.gen_append(
right.len(),
|j, _| {
(right[i].0.get(j).copied().unwrap_or(Mod::zero())
+ right[i].1.get(j).copied().unwrap_or(Mod::zero())) * mult
},
);
strip_zero(&mut r01);
ps01.clear();
ps01.gen_append(
down.len(),
|j, _| {
(ps[down.len()].0[j] - ps[k].0[j] + ps[down.len()].1[j]
- ps[k].1[j]) * mult
},
);
strip_zero(&mut ps01);
psk.clear();
psk.gen_append(
down.len() + 1,
|j, _| {
let mut res = ps[k].0.get(j).copied().unwrap_or(Mod::zero());
if j > 0 {
res += ps[k].1[j - 1];
}
res
},
);
fft.multiply_fix_len(&r01, &psk, &mut temp);
for j in 0..right.len() + down.len() {
res[i + k].0[j] += temp[j];
}
fft.multiply_fix_len(&right[i].0, &ps01, &mut temp);
for j in 0..right.len() + down.len() - 1 {
res[i + k].0[j] += temp[j];
}
fft.multiply_fix_len(&right[i].1, &ps01, &mut temp);
for j in 0..right.len() + down.len() - 1 {
res[i + k].1[j] += temp[j];
}
}
}
for i in res.indices() {
strip_zero(&mut res[i].0);
strip_zero(&mut res[i].1);
}
res
}
});
let call = mem.call(0, 0);
let mut ans = vec![Mod::zero(); n];
for i in 0..n {
for j in 0..n {
ans[j] += call[i].1.get(j).copied().unwrap_or(Mod::zero());
if j > 0 {
ans[j - 1] += call[i].0.get(j).copied().unwrap_or(Mod::zero());
}
}
}
out.print_per_line(&ans);
}
pub static TEST_TYPE: TestType = TestType::Single;
pub static TASK_TYPE: TaskType = TaskType::Classic;
pub(crate) fn run(mut input: Input, mut output: Output) -> bool {
let mut pre_calc = ();
match TEST_TYPE {
TestType::Single => solve(&mut input, &mut output, 1, &mut pre_calc),
TestType::MultiNumber => {
let t = input.read();
for i in 1..=t {
solve(&mut input, &mut output, i, &mut pre_calc);
}
}
TestType::MultiEof => {
let mut i = 1;
while input.peek().is_some() {
solve(&mut input, &mut output, i, &mut pre_calc);
i += 1;
}
}
}
output.flush();
match TASK_TYPE {
TaskType::Classic => input.is_empty(),
TaskType::Interactive => true,
}
}
fn main() {
let input = crate::algo_lib::io::input::Input::stdin();
let output = crate::algo_lib::io::output::Output::stdout();
run(input, output);
}
pub mod algo_lib {
pub mod collections {
pub mod dsu {
use crate::algo_lib::collections::slice_ext::bounds::Bounds;
use crate::algo_lib::collections::slice_ext::indices::Indices;
use std::cell::Cell;
#[derive(Clone)]
pub struct DSU {
id: Vec<Cell<i32>>,
count: usize,
}
impl DSU {
pub fn new(n: usize) -> Self {
Self {
id: vec![Cell::new(- 1); n],
count: n,
}
}
pub fn size(&self, i: usize) -> usize {
(-self.id[self.find(i)].get()) as usize
}
#[allow(clippy::len_without_is_empty)]
pub fn len(&self) -> usize {
self.id.len()
}
pub fn iter(&self) -> impl Iterator<Item = usize> + '_ {
self.id
.iter()
.enumerate()
.filter_map(|(i, id)| if id.get() < 0 { Some(i) } else { None })
}
pub fn set_count(&self) -> usize {
self.count
}
pub fn union(&mut self, mut a: usize, mut b: usize) -> bool {
a = self.find(a);
b = self.find(b);
if a == b {
false
} else {
self.id[a].set(self.id[a].get() + self.id[b].get());
self.id[b].set(a as i32);
self.count -= 1;
true
}
}
pub fn find(&self, i: usize) -> usize {
if self.id[i].get() >= 0 {
let res = self.find(self.id[i].get() as usize);
self.id[i].set(res as i32);
res
} else {
i
}
}
pub fn clear(&mut self) {
self.count = self.id.len();
self.id.fill(Cell::new(-1));
}
pub fn parts(&self) -> Vec<Vec<usize>> {
let roots: Vec<_> = self.iter().collect();
let mut res = vec![Vec::new(); roots.len()];
for i in self.id.indices() {
res[roots.as_slice().bin_search(&self.find(i)).unwrap()].push(i);
}
res
}
}
}
pub mod fx_hash_map {
use crate::algo_lib::misc::lazy_lock::LazyLock;
use std::convert::TryInto;
use std::time::SystemTime;
use std::{
collections::{HashMap, HashSet},
hash::{BuildHasherDefault, Hasher},
ops::BitXor,
};
pub type FxHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FxHasher>>;
pub type FxHashSet<V> = HashSet<V, BuildHasherDefault<FxHasher>>;
#[derive(Default)]
pub struct FxHasher {
hash: usize,
}
static K: LazyLock<usize> = LazyLock::new(|| {
((SystemTime::UNIX_EPOCH.elapsed().unwrap().as_nanos().wrapping_mul(2) + 1)
& 0xFFFFFFFFFFFFFFFF) as usize
});
impl FxHasher {
#[inline]
fn add_to_hash(&mut self, i: usize) {
self.hash = self.hash.rotate_left(5).bitxor(i).wrapping_mul(*K);
}
}
impl Hasher for FxHasher {
#[inline]
fn write(&mut self, mut bytes: &[u8]) {
let read_usize = |bytes: &[u8]| u64::from_ne_bytes(
bytes[..8].try_into().unwrap(),
);
let mut hash = FxHasher { hash: self.hash };
while bytes.len() >= 8 {
hash.add_to_hash(read_usize(bytes) as usize);
bytes = &bytes[8..];
}
if bytes.len() >= 4 {
hash.add_to_hash(
u32::from_ne_bytes(bytes[..4].try_into().unwrap()) as usize,
);
bytes = &bytes[4..];
}
if bytes.len() >= 2 {
hash.add_to_hash(
u16::from_ne_bytes(bytes[..2].try_into().unwrap()) as usize,
);
bytes = &bytes[2..];
}
if !bytes.is_empty() {
hash.add_to_hash(bytes[0] as usize);
}
self.hash = hash.hash;
}
#[inline]
fn write_u8(&mut self, i: u8) {
self.add_to_hash(i as usize);
}
#[inline]
fn write_u16(&mut self, i: u16) {
self.add_to_hash(i as usize);
}
#[inline]
fn write_u32(&mut self, i: u32) {
self.add_to_hash(i as usize);
}
#[inline]
fn write_u64(&mut self, i: u64) {
self.add_to_hash(i as usize);
}
#[inline]
fn write_usize(&mut self, i: usize) {
self.add_to_hash(i);
}
#[inline]
fn finish(&self) -> u64 {
self.hash as u64
}
}
}
pub mod md_arr {
pub mod arr2d {
use crate::algo_lib::io::input::{Input, Readable};
use crate::algo_lib::io::output::{Output, Writable};
use std::iter::{Skip, StepBy, Take};
use std::mem::MaybeUninit;
use std::ops::{Index, IndexMut, Range};
use std::slice::{Iter, IterMut};
use std::vec::IntoIter;
#[derive(Clone, Eq, PartialEq, Default, Debug, Hash, Ord, PartialOrd)]
pub struct Arr2d<T> {
d1: usize,
d2: usize,
data: Vec<T>,
}
impl<T: Clone> Arr2d<T> {
pub fn new(d1: usize, d2: usize, value: T) -> Self {
Self {
d1,
d2,
data: vec![value; d1 * d2],
}
}
}
impl<T> Arr2d<T> {
pub fn with_gen<F>(d1: usize, d2: usize, mut g: F) -> Self
where
F: FnMut(usize, usize) -> T,
{
let mut data = Vec::with_capacity(d1 * d2);
for i in 0usize..d1 {
for j in 0usize..d2 {
data.push(g(i, j));
}
}
Self { d1, d2, data }
}
pub fn d1(&self) -> usize {
self.d1
}
pub fn d2(&self) -> usize {
self.d2
}
pub fn iter(&self) -> Iter<'_, T> {
self.data.iter()
}
pub fn iter_mut(&mut self) -> IterMut<'_, T> {
self.data.iter_mut()
}
pub fn row(&self, row: usize) -> Take<Skip<Iter<'_, T>>> {
assert!(row < self.d1);
self.data.iter().skip(row * self.d2).take(self.d2)
}
pub fn row_mut(&mut self, row: usize) -> Take<Skip<IterMut<'_, T>>> {
assert!(row < self.d1);
self.data.iter_mut().skip(row * self.d2).take(self.d2)
}
pub fn col(&self, col: usize) -> StepBy<Skip<Iter<'_, T>>> {
assert!(col < self.d2);
self.data.iter().skip(col).step_by(self.d2)
}
pub fn col_mut(&mut self, col: usize) -> StepBy<Skip<IterMut<'_, T>>> {
assert!(col < self.d2);
self.data.iter_mut().skip(col).step_by(self.d2)
}
pub fn swap(&mut self, r1: usize, c1: usize, r2: usize, c2: usize) {
assert!(c1 < self.d2);
assert!(c2 < self.d2);
self.data.swap(r1 * self.d2 + c1, r2 * self.d2 + c2);
}
pub fn rows(&self) -> Range<usize> {
0..self.d1
}
pub fn cols(&self) -> Range<usize> {
0..self.d2
}
pub fn swap_rows(&mut self, r1: usize, r2: usize) {
if r1 == r2 {
assert!(r1 < self.d1);
return;
}
let (r1, r2) = (r1.min(r2), r1.max(r2));
let (head, tail) = self.data.split_at_mut(r2 * self.d2);
head[r1 * self.d2..(r1 + 1) * self.d2].swap_with_slice(&mut tail[..self.d2]);
}
pub fn rotate_clockwise(self) -> Self {
unsafe {
let d1 = self.d1;
let d2 = self.d2;
let mut res = MaybeUninit::new(Vec::with_capacity(d1 * d2));
(*res.as_mut_ptr()).set_len(d1 * d2);
for (id, element) in self.into_iter().enumerate() {
let (i, j) = (id / d2, id % d2);
let ptr: *mut T = (*res.as_mut_ptr()).as_mut_ptr();
ptr.add(j * d1 + d1 - i - 1).write(element);
}
Self {
d1: d2,
d2: d1,
data: res.assume_init(),
}
}
}
pub fn rotate_counterclockwise(self) -> Self {
unsafe {
let d1 = self.d1;
let d2 = self.d2;
let mut res = MaybeUninit::new(Vec::with_capacity(d1 * d2));
(*res.as_mut_ptr()).set_len(d1 * d2);
for (id, element) in self.into_iter().enumerate() {
let (i, j) = (id / d2, id % d2);
let ptr: *mut T = (*res.as_mut_ptr()).as_mut_ptr();
ptr.add((d2 - j - 1) * d1 + i).write(element);
}
Self {
d1: d2,
d2: d1,
data: res.assume_init(),
}
}
}
pub fn transpose(self) -> Self {
unsafe {
let d1 = self.d1;
let d2 = self.d2;
let mut res = MaybeUninit::new(Vec::with_capacity(d1 * d2));
(*res.as_mut_ptr()).set_len(d1 * d2);
for (id, element) in self.into_iter().enumerate() {
let (i, j) = (id / d2, id % d2);
let ptr: *mut T = (*res.as_mut_ptr()).as_mut_ptr();
ptr.add(j * d1 + i).write(element);
}
Self {
d1: d2,
d2: d1,
data: res.assume_init(),
}
}
}
pub fn as_slice(&self) -> &[T] {
&self.data
}
}
impl<T: Clone> Arr2d<T> {
pub fn fill(&mut self, elem: T) {
self.data.fill(elem);
}
}
impl<T> Index<(usize, usize)> for Arr2d<T> {
type Output = T;
fn index(&self, (row, col): (usize, usize)) -> &Self::Output {
assert!(col < self.d2);
&self.data[self.d2 * row + col]
}
}
impl<T> Index<usize> for Arr2d<T> {
type Output = [T];
fn index(&self, index: usize) -> &Self::Output {
&self.data[self.d2 * index..self.d2 * (index + 1)]
}
}
impl<T> IndexMut<(usize, usize)> for Arr2d<T> {
fn index_mut(&mut self, (row, col): (usize, usize)) -> &mut T {
assert!(col < self.d2);
&mut self.data[self.d2 * row + col]
}
}
impl<T> IndexMut<usize> for Arr2d<T> {
fn index_mut(&mut self, index: usize) -> &mut [T] {
&mut self.data[self.d2 * index..self.d2 * (index + 1)]
}
}
impl<T> AsRef<Vec<T>> for Arr2d<T> {
fn as_ref(&self) -> &Vec<T> {
&self.data
}
}
impl<T> AsMut<Vec<T>> for Arr2d<T> {
fn as_mut(&mut self) -> &mut Vec<T> {
&mut self.data
}
}
impl<T: Writable> Writable for Arr2d<T> {
fn write(&self, output: &mut Output) {
let mut at = 0usize;
for i in 0usize..self.d1 {
if i != 0 {
output.put(b'\n');
}
for j in 0usize..self.d2 {
if j != 0 {
output.put(output.separator());
}
self.data[at].write(output);
at += 1;
}
}
}
}
impl<T> IntoIterator for Arr2d<T> {
type Item = T;
type IntoIter = IntoIter<T>;
fn into_iter(self) -> Self::IntoIter {
self.data.into_iter()
}
}
impl<'a, T> IntoIterator for &'a Arr2d<T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
pub trait Arr2dRead {
fn read_table<T: Readable>(&mut self, d1: usize, d2: usize) -> Arr2d<T>;
fn read_int_table(&mut self, d1: usize, d2: usize) -> Arr2d<i32>;
fn read_long_table(&mut self, d1: usize, d2: usize) -> Arr2d<i64>;
fn read_size_table(&mut self, d1: usize, d2: usize) -> Arr2d<usize>;
fn read_char_table(&mut self, d1: usize, d2: usize) -> Arr2d<u8>;
}
impl Arr2dRead for Input {
fn read_table<T: Readable>(&mut self, d1: usize, d2: usize) -> Arr2d<T> {
Arr2d::with_gen(d1, d2, |_, _| self.read())
}
fn read_int_table(&mut self, d1: usize, d2: usize) -> Arr2d<i32> {
self.read_table(d1, d2)
}
fn read_long_table(&mut self, d1: usize, d2: usize) -> Arr2d<i64> {
self.read_table(d1, d2)
}
fn read_size_table(&mut self, d1: usize, d2: usize) -> Arr2d<usize> {
self.read_table(d1, d2)
}
fn read_char_table(&mut self, d1: usize, d2: usize) -> Arr2d<u8> {
self.read_table(d1, d2)
}
}
pub trait Arr2dCharWrite {
fn print_table(&mut self, table: &Arr2d<u8>);
}
impl Arr2dCharWrite for Output<'_> {
fn print_table(&mut self, table: &Arr2d<u8>) {
let mut at = 0usize;
for _ in 0..table.d1 {
for _ in 0..table.d2 {
self.put(table.data[at]);
at += 1;
}
self.put(b'\n');
}
}
}
impl<T: Readable> Readable for Arr2d<T> {
fn read(input: &mut Input) -> Self {
let d1 = input.read();
let d2 = input.read();
input.read_table(d1, d2)
}
}
}
}
pub mod slice_ext {
pub mod bounds {
use std::ops::{Bound, RangeBounds};
pub trait Bounds<T: PartialOrd> {
fn lower_bound(&self, el: &T) -> usize;
fn upper_bound(&self, el: &T) -> usize;
fn bin_search(&self, el: &T) -> Option<usize>;
fn more(&self, el: &T) -> usize;
fn more_or_eq(&self, el: &T) -> usize;
fn less(&self, el: &T) -> usize {
self.lower_bound(el)
}
fn less_or_eq(&self, el: &T) -> usize {
self.upper_bound(el)
}
fn inside<'a>(&self, bounds: impl RangeBounds<&'a T>) -> usize
where
T: 'a;
}
impl<T: PartialOrd> Bounds<T> for [T] {
fn lower_bound(&self, el: &T) -> usize {
let mut left = 0;
let mut right = self.len();
while left < right {
let mid = left + ((right - left) >> 1);
if &self[mid] < el {
left = mid + 1;
} else {
right = mid;
}
}
left
}
fn upper_bound(&self, el: &T) -> usize {
let mut left = 0;
let mut right = self.len();
while left < right {
let mid = left + ((right - left) >> 1);
if &self[mid] <= el {
left = mid + 1;
} else {
right = mid;
}
}
left
}
fn bin_search(&self, el: &T) -> Option<usize> {
let at = self.lower_bound(el);
if at == self.len() || &self[at] != el { None } else { Some(at) }
}
fn more(&self, el: &T) -> usize {
self.len() - self.upper_bound(el)
}
fn more_or_eq(&self, el: &T) -> usize {
self.len() - self.lower_bound(el)
}
fn inside<'a>(&self, bounds: impl RangeBounds<&'a T>) -> usize
where
T: 'a,
{
let to = match bounds.end_bound() {
Bound::Included(el) => self.less_or_eq(el),
Bound::Excluded(el) => self.less(el),
Bound::Unbounded => self.len(),
};
let from = match bounds.start_bound() {
Bound::Included(el) => self.less(el),
Bound::Excluded(el) => self.less_or_eq(el),
Bound::Unbounded => 0,
};
to - from
}
}
}
pub mod indices {
use std::ops::Range;
pub trait Indices {
fn indices(&self) -> Range<usize>;
}
impl<T> Indices for [T] {
fn indices(&self) -> Range<usize> {
0..self.len()
}
}
}
}
pub mod vec_ext {
pub mod default {
pub fn default_vec<T: Default>(len: usize) -> Vec<T> {
let mut v = Vec::with_capacity(len);
for _ in 0..len {
v.push(T::default());
}
v
}
}
pub mod gen_vec {
use crate::algo_lib::collections::vec_ext::default::default_vec;
pub trait VecGen<T> {
fn with_gen(n: usize, f: impl FnMut(usize) -> T) -> Vec<T>;
fn with_gen_prefix(n: usize, f: impl FnMut(usize, &Self) -> T) -> Vec<T>;
fn gen_append(&mut self, n: usize, f: impl FnMut(usize, &Self) -> T);
fn with_gen_back(n: usize, f: impl FnMut(usize, &Self) -> T) -> Vec<T>
where
T: Default;
}
impl<T> VecGen<T> for Vec<T> {
fn with_gen(n: usize, mut f: impl FnMut(usize) -> T) -> Vec<T> {
Self::with_gen_prefix(n, |i, _| f(i))
}
fn with_gen_prefix(n: usize, f: impl FnMut(usize, &Self) -> T) -> Vec<T> {
let mut vec = Vec::with_capacity(n);
vec.gen_append(n, f);
vec
}
fn gen_append(&mut self, n: usize, mut f: impl FnMut(usize, &Self) -> T) {
self.reserve(n);
let len = self.len();
for i in 0..n {
self.push(f(len + i, self));
}
}
fn with_gen_back(n: usize, mut f: impl FnMut(usize, &Self) -> T) -> Vec<T>
where
T: Default,
{
let mut vec = default_vec(n);
for i in (0..n).rev() {
vec[i] = f(i, &vec);
}
vec
}
}
}
pub mod inc_dec {
use crate::algo_lib::numbers::num_traits::algebra::{AdditionMonoidWithSub, One};
pub trait IncDec {
#[must_use]
fn inc(self) -> Self;
#[must_use]
fn dec(self) -> Self;
}
impl<T: AdditionMonoidWithSub + One> IncDec for T {
fn inc(self) -> Self {
self + T::one()
}
fn dec(self) -> Self {
self - T::one()
}
}
impl<T: AdditionMonoidWithSub + One> IncDec for Vec<T> {
fn inc(mut self) -> Self {
self.iter_mut().for_each(|i| *i += T::one());
self
}
fn dec(mut self) -> Self {
self.iter_mut().for_each(|i| *i -= T::one());
self
}
}
impl<T: AdditionMonoidWithSub + One> IncDec for Vec<Vec<T>> {
fn inc(mut self) -> Self {
self.iter_mut().for_each(|v| v.iter_mut().for_each(|i| *i += T::one()));
self
}
fn dec(mut self) -> Self {
self.iter_mut().for_each(|v| v.iter_mut().for_each(|i| *i -= T::one()));
self
}
}
impl<T: AdditionMonoidWithSub + One, U: AdditionMonoidWithSub + One> IncDec
for Vec<(T, U)> {
fn inc(mut self) -> Self {
self.iter_mut()
.for_each(|(i, j)| {
*i += T::one();
*j += U::one();
});
self
}
fn dec(mut self) -> Self {
self.iter_mut()
.for_each(|(i, j)| {
*i -= T::one();
*j -= U::one();
});
self
}
}
impl<T: AdditionMonoidWithSub + One, U: AdditionMonoidWithSub + One, V> IncDec
for Vec<(T, U, V)> {
fn inc(mut self) -> Self {
self.iter_mut()
.for_each(|(i, j, _)| {
*i += T::one();
*j += U::one();
});
self
}
fn dec(mut self) -> Self {
self.iter_mut()
.for_each(|(i, j, _)| {
*i -= T::one();
*j -= U::one();
});
self
}
}
impl<T: AdditionMonoidWithSub + One, U: AdditionMonoidWithSub + One, V, W> IncDec
for Vec<(T, U, V, W)> {
fn inc(mut self) -> Self {
self.iter_mut()
.for_each(|(i, j, ..)| {
*i += T::one();
*j += U::one();
});
self
}
fn dec(mut self) -> Self {
self.iter_mut()
.for_each(|(i, j, ..)| {
*i -= T::one();
*j -= U::one();
});
self
}
}
impl<T: AdditionMonoidWithSub + One, U: AdditionMonoidWithSub + One, V, W, X> IncDec
for Vec<(T, U, V, W, X)> {
fn inc(mut self) -> Self {
self.iter_mut()
.for_each(|(i, j, ..)| {
*i += T::one();
*j += U::one();
});
self
}
fn dec(mut self) -> Self {
self.iter_mut()
.for_each(|(i, j, ..)| {
*i -= T::one();
*j -= U::one();
});
self
}
}
impl<T: AdditionMonoidWithSub + One, U: AdditionMonoidWithSub + One> IncDec for (T, U) {
fn inc(mut self) -> Self {
self.0 += T::one();
self.1 += U::one();
self
}
fn dec(mut self) -> Self {
self.0 -= T::one();
self.1 -= U::one();
self
}
}
}
}
}
pub mod graph {
use crate::algo_lib::collections::dsu::DSU;
use crate::algo_lib::graph::edges::bi_edge::BiEdge;
use crate::algo_lib::graph::edges::edge::Edge;
use crate::algo_lib::graph::edges::edge_trait::{BidirectionalEdgeTrait, EdgeTrait};
use std::ops::{Index, IndexMut};
#[derive(Clone)]
pub struct Graph<E: EdgeTrait> {
edges: Vec<Vec<E>>,
edge_count: usize,
}
impl<E: EdgeTrait> Graph<E> {
pub fn new(vertex_count: usize) -> Self {
Self {
edges: vec![Vec::new(); vertex_count],
edge_count: 0,
}
}
pub fn add_edge(&mut self, (from, mut edge): (usize, E)) -> usize {
let to = edge.to();
assert!(to < self.vertex_count());
let direct_id = self.edges[from].len();
edge.set_id(self.edge_count);
self.edges[from].push(edge);
if E::REVERSABLE {
let rev_id = self.edges[to].len();
self.edges[from][direct_id].set_reverse_id(rev_id);
let mut rev_edge = self.edges[from][direct_id].reverse_edge(from);
rev_edge.set_id(self.edge_count);
rev_edge.set_reverse_id(direct_id);
self.edges[to].push(rev_edge);
}
self.edge_count += 1;
direct_id
}
pub fn add_vertices(&mut self, cnt: usize) {
self.edges.resize(self.edges.len() + cnt, Vec::new());
}
pub fn clear(&mut self) {
self.edge_count = 0;
for ve in self.edges.iter_mut() {
ve.clear();
}
}
pub fn vertex_count(&self) -> usize {
self.edges.len()
}
pub fn edge_count(&self) -> usize {
self.edge_count
}
pub fn degrees(&self) -> Vec<usize> {
self.edges.iter().map(|v| v.len()).collect()
}
}
impl<E: BidirectionalEdgeTrait> Graph<E> {
pub fn is_tree(&self) -> bool {
if self.edge_count + 1 != self.vertex_count() {
false
} else {
self.is_connected()
}
}
pub fn is_forest(&self) -> bool {
let mut dsu = DSU::new(self.vertex_count());
for i in 0..self.vertex_count() {
for e in self[i].iter() {
if i <= e.to() && !dsu.union(i, e.to()) {
return false;
}
}
}
true
}
pub fn is_connected(&self) -> bool {
let mut dsu = DSU::new(self.vertex_count());
for i in 0..self.vertex_count() {
for e in self[i].iter() {
dsu.union(i, e.to());
}
}
dsu.set_count() == 1
}
}
impl<E: EdgeTrait> Index<usize> for Graph<E> {
type Output = [E];
fn index(&self, index: usize) -> &Self::Output {
&self.edges[index]
}
}
impl<E: EdgeTrait> IndexMut<usize> for Graph<E> {
fn index_mut(&mut self, index: usize) -> &mut Self::Output {
&mut self.edges[index]
}
}
impl Graph<Edge<()>> {
pub fn with_edges(n: usize, edges: &[(usize, usize)]) -> Self {
let mut graph = Self::new(n);
for &(from, to) in edges {
graph.add_edge(Edge::new(from, to));
}
graph
}
}
impl<P: Clone> Graph<Edge<P>> {
pub fn with_edges_with_payload(n: usize, edges: &[(usize, usize, P)]) -> Self {
let mut graph = Self::new(n);
for (from, to, p) in edges.iter() {
graph.add_edge(Edge::with_payload(*from, *to, p.clone()));
}
graph
}
}
impl Graph<BiEdge<()>> {
pub fn with_biedges(n: usize, edges: &[(usize, usize)]) -> Self {
let mut graph = Self::new(n);
for &(from, to) in edges {
graph.add_edge(BiEdge::new(from, to));
}
graph
}
}
impl<P: Clone> Graph<BiEdge<P>> {
pub fn with_biedges_with_payload(n: usize, edges: &[(usize, usize, P)]) -> Self {
let mut graph = Self::new(n);
for (from, to, p) in edges.iter() {
graph.add_edge(BiEdge::with_payload(*from, *to, p.clone()));
}
graph
}
}
pub mod edges {
pub mod bi_edge {
use crate::algo_lib::graph::edges::bi_edge_trait::BiEdgeTrait;
use crate::algo_lib::graph::edges::edge_id::{EdgeId, NoId, WithId};
use crate::algo_lib::graph::edges::edge_trait::{BidirectionalEdgeTrait, EdgeTrait};
#[derive(Clone)]
pub struct BiEdgeRaw<Id: EdgeId, P> {
to: u32,
id: Id,
payload: P,
}
impl<Id: EdgeId> BiEdgeRaw<Id, ()> {
pub fn new(from: usize, to: usize) -> (usize, Self) {
(
from,
Self {
to: to as u32,
id: Id::new(),
payload: (),
},
)
}
}
impl<Id: EdgeId, P> BiEdgeRaw<Id, P> {
pub fn with_payload(from: usize, to: usize, payload: P) -> (usize, Self) {
(from, Self::with_payload_impl(to, payload))
}
fn with_payload_impl(to: usize, payload: P) -> BiEdgeRaw<Id, P> {
Self {
to: to as u32,
id: Id::new(),
payload,
}
}
}
impl<Id: EdgeId, P: Clone> BidirectionalEdgeTrait for BiEdgeRaw<Id, P> {}
impl<Id: EdgeId, P: Clone> EdgeTrait for BiEdgeRaw<Id, P> {
type Payload = P;
const REVERSABLE: bool = true;
fn to(&self) -> usize {
self.to as usize
}
fn id(&self) -> usize {
self.id.id()
}
fn set_id(&mut self, id: usize) {
self.id.set_id(id);
}
fn reverse_id(&self) -> usize {
panic!("no reverse id")
}
fn set_reverse_id(&mut self, _: usize) {}
fn reverse_edge(&self, from: usize) -> Self {
Self::with_payload_impl(from, self.payload.clone())
}
fn payload(&self) -> &P {
&self.payload
}
}
impl<Id: EdgeId, P: Clone> BiEdgeTrait for BiEdgeRaw<Id, P> {}
pub type BiEdge<P> = BiEdgeRaw<NoId, P>;
pub type BiEdgeWithId<P> = BiEdgeRaw<WithId, P>;
}
pub mod bi_edge_trait {
use crate::algo_lib::graph::edges::edge_trait::EdgeTrait;
pub trait BiEdgeTrait: EdgeTrait {}
}
pub mod edge {
use crate::algo_lib::graph::edges::edge_id::{EdgeId, NoId, WithId};
use crate::algo_lib::graph::edges::edge_trait::EdgeTrait;
#[derive(Clone)]
pub struct EdgeRaw<Id: EdgeId, P> {
to: u32,
id: Id,
payload: P,
}
impl<Id: EdgeId> EdgeRaw<Id, ()> {
pub fn new(from: usize, to: usize) -> (usize, Self) {
(
from,
Self {
to: to as u32,
id: Id::new(),
payload: (),
},
)
}
}
impl<Id: EdgeId, P> EdgeRaw<Id, P> {
pub fn with_payload(from: usize, to: usize, payload: P) -> (usize, Self) {
(from, Self::with_payload_impl(to, payload))
}
fn with_payload_impl(to: usize, payload: P) -> Self {
Self {
to: to as u32,
id: Id::new(),
payload,
}
}
}
impl<Id: EdgeId, P: Clone> EdgeTrait for EdgeRaw<Id, P> {
type Payload = P;
const REVERSABLE: bool = false;
fn to(&self) -> usize {
self.to as usize
}
fn id(&self) -> usize {
self.id.id()
}
fn set_id(&mut self, id: usize) {
self.id.set_id(id);
}
fn reverse_id(&self) -> usize {
panic!("no reverse")
}
fn set_reverse_id(&mut self, _: usize) {
panic!("no reverse")
}
fn reverse_edge(&self, _: usize) -> Self {
panic!("no reverse")
}
fn payload(&self) -> &P {
&self.payload
}
}
pub type Edge<P> = EdgeRaw<NoId, P>;
pub type EdgeWithId<P> = EdgeRaw<WithId, P>;
}
pub mod edge_id {
pub trait EdgeId: Clone {
fn new() -> Self;
fn id(&self) -> usize;
fn set_id(&mut self, id: usize);
}
#[derive(Clone)]
pub struct WithId {
id: u32,
}
impl EdgeId for WithId {
fn new() -> Self {
Self { id: 0 }
}
fn id(&self) -> usize {
self.id as usize
}
fn set_id(&mut self, id: usize) {
self.id = id as u32;
}
}
#[derive(Clone)]
pub struct NoId {}
impl EdgeId for NoId {
fn new() -> Self {
Self {}
}
fn id(&self) -> usize {
panic!("Id called on no id")
}
fn set_id(&mut self, _: usize) {}
}
}
pub mod edge_trait {
pub trait EdgeTrait: Clone {
type Payload;
const REVERSABLE: bool;
fn to(&self) -> usize;
fn id(&self) -> usize;
fn set_id(&mut self, id: usize);
fn reverse_id(&self) -> usize;
fn set_reverse_id(&mut self, reverse_id: usize);
#[must_use]
fn reverse_edge(&self, from: usize) -> Self;
fn payload(&self) -> &Self::Payload;
}
pub trait BidirectionalEdgeTrait: EdgeTrait {}
}
}
pub mod lca {
use crate::algo_lib::collections::md_arr::arr2d::Arr2d;
use crate::algo_lib::graph::edges::edge_trait::BidirectionalEdgeTrait;
use crate::algo_lib::graph::Graph;
use crate::algo_lib::misc::owned_cell::OwnedCell;
pub struct LCA {
position: Vec<u32>,
lca_arr: Arr2d<u32>,
level: Vec<u32>,
parent: Vec<u32>,
ancestors: OwnedCell<Option<Arr2d<i32>>>,
}
impl LCA {
pub fn level(&self, vert: usize) -> usize {
self.level[vert] as usize
}
pub fn parent(&self, vert: usize) -> Option<usize> {
if (self.parent[vert] as usize) == vert {
None
} else {
Some(self.parent[vert] as usize)
}
}
pub fn lca(&self, first: usize, second: usize) -> usize {
if first == second {
first
} else {
let from = self.position[first].min(self.position[second]) as usize;
let to = self.position[first].max(self.position[second]) as usize;
let lv = (32 - ((to - from) as u32).leading_zeros() - 1) as usize;
get_min(
&self.level,
self.lca_arr[(lv, from)],
self.lca_arr[(lv, to + 1 - (1 << lv))],
) as usize
}
}
pub fn position(&self, vertex: usize) -> usize {
self.position[vertex] as usize
}
pub fn on_path(&self, a: usize, b: usize, c: usize) -> bool {
let lca = self.lca(a, b);
self.lca(a, c) == lca && self.lca(b, c) == c
|| self.lca(a, c) == c && self.lca(b, c) == lca
}
pub fn path_length(&self, first: usize, second: usize) -> usize {
(self.level[first] + self.level[second]
- 2 * self.level[self.lca(first, second)]) as usize
}
pub fn num_levels(&self) -> usize {
self.build_steps();
unsafe { self.ancestors.as_ref().as_ref().unwrap().d1() }
}
pub fn ancestor(&self, level: usize, vert: usize) -> Option<usize> {
self.build_steps();
unsafe {
if level >= self.ancestors.as_ref().as_ref().unwrap().d1() {
None
} else {
let pred = self.ancestors.as_ref().as_ref().unwrap()[(level, vert)];
if pred == -1 { None } else { Some(pred as usize) }
}
}
}
fn build_steps(&self) {
unsafe {
if self.ancestors.as_ref().is_some() {
return;
}
}
let vertex_count = self.position.len();
let len = (32 - (vertex_count as u32).leading_zeros()) as usize;
let mut predecessors = Arr2d::new(len, vertex_count, -1);
for i in 0..vertex_count {
predecessors[(0, i)] = match self.parent(i) {
None => -1,
Some(v) => v as i32,
};
}
for i in 1..len {
for j in 0..vertex_count {
let p = predecessors[(i - 1, j)];
if p == -1 {
predecessors[(i, j)] = -1;
} else {
predecessors[(i, j)] = predecessors[(i - 1, p as usize)];
}
}
}
unsafe {
self.ancestors.replace(Some(predecessors));
}
}
}
fn get_min(level: &[u32], a: u32, b: u32) -> u32 {
if level[a as usize] < level[b as usize] { a } else { b }
}
pub trait LCATrait {
fn lca_with_root(&self, root: usize) -> LCA;
fn lca(&self) -> LCA {
self.lca_with_root(0)
}
}
impl<E: BidirectionalEdgeTrait> LCATrait for Graph<E> {
fn lca_with_root(&self, root: usize) -> LCA {
debug_assert!(self.is_tree());
let vertex_count = self.vertex_count();
let mut order = vec![0u32; 2 * vertex_count - 1];
let mut position = vec![vertex_count as u32; vertex_count];
let mut level = vec![0; vertex_count];
let mut index = vec![0u32; vertex_count];
let mut parent = vec![0; vertex_count];
let mut stack = vec![0u32; vertex_count];
stack[0] = root as u32;
let mut size = 1usize;
let mut j = 0usize;
parent[root] = root as u32;
while size > 0 {
size -= 1;
let vertex = stack[size] as usize;
if (position[vertex] as usize) == vertex_count {
position[vertex] = j as u32;
}
order[j] = vertex as u32;
j += 1;
while (index[vertex] as usize) < self[vertex].len()
&& (parent[vertex] as usize) == self[vertex][index[vertex] as usize].to()
{
index[vertex] += 1;
}
if (index[vertex] as usize) < self[vertex].len() {
stack[size] = vertex as u32;
size += 1;
let to = self[vertex][index[vertex] as usize].to();
stack[size] = to as u32;
size += 1;
parent[to] = vertex as u32;
level[to] = level[vertex] + 1;
index[vertex] += 1;
}
}
let mut lca_arr = Arr2d::new(
(32 - ((2 * vertex_count - 1) as u32).leading_zeros()) as usize,
2 * vertex_count - 1,
0,
);
for i in 0..(2 * vertex_count - 1) {
lca_arr[(0, i)] = order[i];
}
for i in 1..lca_arr.d1() {
for j in 0..lca_arr.d2() {
let other = j + (1 << (i - 1));
if other < lca_arr.d2() {
lca_arr[(i, j)] = get_min(
&level,
lca_arr[(i - 1, j)],
lca_arr[(i - 1, other)],
);
} else {
lca_arr[(i, j)] = lca_arr[(i - 1, j)];
}
}
}
LCA {
position,
lca_arr,
level,
parent,
ancestors: OwnedCell::new(None),
}
}
}
}
}
pub mod io {
pub mod input {
use std::fs::File;
use std::io::{Read, Stdin};
use std::mem::MaybeUninit;
enum InputSource {
Stdin(Stdin),
File(File),
Slice,
Delegate(Box<dyn Read + Send>),
}
pub struct Input {
input: InputSource,
buf: Vec<u8>,
at: usize,
buf_read: usize,
eol: bool,
}
macro_rules! read_impl {
($t:ty, $read_name:ident, $read_vec_name:ident) => {
pub fn $read_name (& mut self) -> $t { self.read() } pub fn $read_vec_name (& mut
self, len : usize) -> Vec <$t > { self.read_vec(len) }
};
($t:ty, $read_name:ident, $read_vec_name:ident, $read_pair_vec_name:ident) => {
read_impl!($t, $read_name, $read_vec_name); pub fn $read_pair_vec_name (& mut
self, len : usize) -> Vec < ($t, $t) > { self.read_vec(len) }
};
}
impl Input {
const DEFAULT_BUF_SIZE: usize = 4096;
pub fn slice(input: &[u8]) -> Self {
Self {
input: InputSource::Slice,
buf: input.to_vec(),
at: 0,
buf_read: input.len(),
eol: true,
}
}
pub fn stdin() -> Self {
Self {
input: InputSource::Stdin(std::io::stdin()),
buf: vec![0; Self::DEFAULT_BUF_SIZE],
at: 0,
buf_read: 0,
eol: true,
}
}
pub fn file(file: File) -> Self {
Self {
input: InputSource::File(file),
buf: vec![0; Self::DEFAULT_BUF_SIZE],
at: 0,
buf_read: 0,
eol: true,
}
}
pub fn delegate(reader: impl Read + Send + 'static) -> Self {
Self {
input: InputSource::Delegate(Box::new(reader)),
buf: vec![0; Self::DEFAULT_BUF_SIZE],
at: 0,
buf_read: 0,
eol: true,
}
}
pub fn get(&mut self) -> Option<u8> {
if self.refill_buffer() {
let res = self.buf[self.at];
self.at += 1;
if res == b'\r' {
self.eol = true;
if self.refill_buffer() && self.buf[self.at] == b'\n' {
self.at += 1;
}
return Some(b'\n');
}
self.eol = res == b'\n';
Some(res)
} else {
None
}
}
pub fn peek(&mut self) -> Option<u8> {
if self.refill_buffer() {
let res = self.buf[self.at];
Some(if res == b'\r' { b'\n' } else { res })
} else {
None
}
}
pub fn skip_whitespace(&mut self) {
while let Some(b) = self.peek() {
if !b.is_ascii_whitespace() {
return;
}
self.get();
}
}
pub fn next_token(&mut self) -> Option<Vec<u8>> {
self.skip_whitespace();
let mut res = Vec::new();
while let Some(c) = self.get() {
if c.is_ascii_whitespace() {
break;
}
res.push(c);
}
if res.is_empty() { None } else { Some(res) }
}
pub fn is_exhausted(&mut self) -> bool {
self.peek().is_none()
}
pub fn is_empty(&mut self) -> bool {
self.skip_whitespace();
self.is_exhausted()
}
pub fn read<T: Readable>(&mut self) -> T {
T::read(self)
}
pub fn read_vec<T: Readable>(&mut self, size: usize) -> Vec<T> {
let mut res = Vec::with_capacity(size);
for _ in 0..size {
res.push(self.read());
}
res
}
pub fn read_char(&mut self) -> u8 {
self.skip_whitespace();
self.get().unwrap()
}
read_impl!(u32, read_unsigned, read_unsigned_vec);
read_impl!(u64, read_u64, read_u64_vec);
read_impl!(usize, read_size, read_size_vec, read_size_pair_vec);
read_impl!(i32, read_int, read_int_vec, read_int_pair_vec);
read_impl!(i64, read_long, read_long_vec, read_long_pair_vec);
read_impl!(i128, read_i128, read_i128_vec);
fn refill_buffer(&mut self) -> bool {
if self.at == self.buf_read {
self.at = 0;
self.buf_read = match &mut self.input {
InputSource::Stdin(stdin) => stdin.read(&mut self.buf).unwrap(),
InputSource::File(file) => file.read(&mut self.buf).unwrap(),
InputSource::Delegate(reader) => reader.read(&mut self.buf).unwrap(),
InputSource::Slice => 0,
};
self.buf_read != 0
} else {
true
}
}
pub fn is_eol(&self) -> bool {
self.eol
}
}
pub trait Readable {
fn read(input: &mut Input) -> Self;
}
impl Readable for u8 {
fn read(input: &mut Input) -> Self {
input.read_char()
}
}
impl<T: Readable> Readable for Vec<T> {
fn read(input: &mut Input) -> Self {
let size = input.read();
input.read_vec(size)
}
}
impl<T: Readable, const SIZE: usize> Readable for [T; SIZE] {
fn read(input: &mut Input) -> Self {
unsafe {
let mut res = MaybeUninit::<[T; SIZE]>::uninit();
for i in 0..SIZE {
let ptr: *mut T = (*res.as_mut_ptr()).as_mut_ptr();
ptr.add(i).write(input.read::<T>());
}
res.assume_init()
}
}
}
macro_rules! read_integer {
($($t:ident)+) => {
$(impl Readable for $t { fn read(input : & mut Input) -> Self { input
.skip_whitespace(); let mut c = input.get().unwrap(); let sgn = match c { b'-' =>
{ c = input.get().unwrap(); true } b'+' => { c = input.get().unwrap(); false } _
=> false, }; let mut res = 0; loop { assert!(c.is_ascii_digit()); res *= 10; let
d = (c - b'0') as $t; if sgn { res -= d; } else { res += d; } match input.get() {
None => break, Some(ch) => { if ch.is_ascii_whitespace() { break; } else { c =
ch; } } } } res } })+
};
}
read_integer!(i8 i16 i32 i64 i128 isize u16 u32 u64 u128 usize);
macro_rules! tuple_readable {
($($name:ident)+) => {
impl <$($name : Readable),+> Readable for ($($name,)+) { fn read(input : & mut
Input) -> Self { ($($name ::read(input),)+) } }
};
}
tuple_readable! {
T
}
tuple_readable! {
T U
}
tuple_readable! {
T U V
}
tuple_readable! {
T U V X
}
tuple_readable! {
T U V X Y
}
tuple_readable! {
T U V X Y Z
}
tuple_readable! {
T U V X Y Z A
}
tuple_readable! {
T U V X Y Z A B
}
tuple_readable! {
T U V X Y Z A B C
}
tuple_readable! {
T U V X Y Z A B C D
}
tuple_readable! {
T U V X Y Z A B C D E
}
tuple_readable! {
T U V X Y Z A B C D E F
}
}
pub mod output {
use std::cmp::Reverse;
use std::fs::File;
use std::io::{Stdout, Write};
#[derive(Copy, Clone)]
pub enum BoolOutput {
YesNo,
YesNoCaps,
PossibleImpossible,
Custom(&'static str, &'static str),
}
impl BoolOutput {
pub fn output(&self, output: &mut Output, val: bool) {
(if val { self.yes() } else { self.no() }).write(output);
}
fn yes(&self) -> &str {
match self {
BoolOutput::YesNo => "Yes",
BoolOutput::YesNoCaps => "YES",
BoolOutput::PossibleImpossible => "Possible",
BoolOutput::Custom(yes, _) => yes,
}
}
fn no(&self) -> &str {
match self {
BoolOutput::YesNo => "No",
BoolOutput::YesNoCaps => "NO",
BoolOutput::PossibleImpossible => "Impossible",
BoolOutput::Custom(_, no) => no,
}
}
}
enum OutputDest<'s> {
Stdout(Stdout),
File(File),
Buf(&'s mut Vec<u8>),
Delegate(Box<dyn Write + 's>),
}
pub struct Output<'s> {
output: OutputDest<'s>,
buf: Vec<u8>,
at: usize,
bool_output: BoolOutput,
precision: Option<usize>,
separator: u8,
}
impl<'s> Output<'s> {
pub fn buf(buf: &'s mut Vec<u8>) -> Self {
Self::new(OutputDest::Buf(buf))
}
pub fn delegate(delegate: impl Write + 'static) -> Self {
Self::new(OutputDest::Delegate(Box::new(delegate)))
}
fn new(output: OutputDest<'s>) -> Self {
Self {
output,
buf: vec![0; Self::DEFAULT_BUF_SIZE],
at: 0,
bool_output: BoolOutput::YesNoCaps,
precision: None,
separator: b' ',
}
}
}
impl Output<'static> {
pub fn stdout() -> Self {
Self::new(OutputDest::Stdout(std::io::stdout()))
}
pub fn file(file: File) -> Self {
Self::new(OutputDest::File(file))
}
}
impl Output<'_> {
const DEFAULT_BUF_SIZE: usize = 4096;
pub fn flush(&mut self) {
if self.at != 0 {
match &mut self.output {
OutputDest::Stdout(stdout) => {
stdout.write_all(&self.buf[..self.at]).unwrap();
stdout.flush().unwrap();
}
OutputDest::File(file) => {
file.write_all(&self.buf[..self.at]).unwrap();
file.flush().unwrap();
}
OutputDest::Buf(buf) => buf.extend_from_slice(&self.buf[..self.at]),
OutputDest::Delegate(delegate) => {
delegate.write_all(&self.buf[..self.at]).unwrap();
delegate.flush().unwrap();
}
}
self.at = 0;
}
}
pub fn print<T: Writable>(&mut self, s: T) {
s.write(self);
}
pub fn print_line<T: Writable>(&mut self, s: T) {
self.print(s);
self.put(b'\n');
}
pub fn put(&mut self, b: u8) {
self.buf[self.at] = b;
self.at += 1;
if self.at == self.buf.len() {
self.flush();
}
}
pub fn print_per_line<T: Writable>(&mut self, arg: &[T]) {
self.print_per_line_iter(arg.iter());
}
pub fn print_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
let mut first = true;
for e in iter {
if first {
first = false;
} else {
self.put(self.separator);
}
e.write(self);
}
}
pub fn print_line_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
self.print_iter(iter);
self.put(b'\n');
}
pub fn print_per_line_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
for e in iter {
e.write(self);
self.put(b'\n');
}
}
pub fn set_bool_output(&mut self, bool_output: BoolOutput) {
self.bool_output = bool_output;
}
pub fn set_precision(&mut self, precision: usize) {
self.precision = Some(precision);
}
pub fn reset_precision(&mut self) {
self.precision = None;
}
pub fn get_precision(&self) -> Option<usize> {
self.precision
}
pub fn separator(&self) -> u8 {
self.separator
}
pub fn set_separator(&mut self, separator: u8) {
self.separator = separator;
}
}
impl Write for Output<'_> {
fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
let mut start = 0usize;
let mut rem = buf.len();
while rem > 0 {
let len = (self.buf.len() - self.at).min(rem);
self.buf[self.at..self.at + len].copy_from_slice(&buf[start..start + len]);
self.at += len;
if self.at == self.buf.len() {
self.flush();
}
start += len;
rem -= len;
}
Ok(buf.len())
}
fn flush(&mut self) -> std::io::Result<()> {
self.flush();
Ok(())
}
}
pub trait Writable {
fn write(&self, output: &mut Output);
}
impl Writable for &str {
fn write(&self, output: &mut Output) {
output.write_all(self.as_bytes()).unwrap();
}
}
impl Writable for String {
fn write(&self, output: &mut Output) {
output.write_all(self.as_bytes()).unwrap();
}
}
impl Writable for char {
fn write(&self, output: &mut Output) {
output.put(*self as u8);
}
}
impl Writable for u8 {
fn write(&self, output: &mut Output) {
output.put(*self);
}
}
impl<T: Writable> Writable for [T] {
fn write(&self, output: &mut Output) {
output.print_iter(self.iter());
}
}
impl<T: Writable, const N: usize> Writable for [T; N] {
fn write(&self, output: &mut Output) {
output.print_iter(self.iter());
}
}
impl<T: Writable + ?Sized> Writable for &T {
fn write(&self, output: &mut Output) {
T::write(self, output)
}
}
impl<T: Writable> Writable for Vec<T> {
fn write(&self, output: &mut Output) {
self.as_slice().write(output);
}
}
impl Writable for () {
fn write(&self, _output: &mut Output) {}
}
macro_rules! write_to_string {
($($t:ident)+) => {
$(impl Writable for $t { fn write(& self, output : & mut Output) { self
.to_string().write(output); } })+
};
}
write_to_string!(u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);
macro_rules! tuple_writable {
($name0:ident $($name:ident : $id:tt)*) => {
impl <$name0 : Writable, $($name : Writable,)*> Writable for ($name0, $($name,)*)
{ fn write(& self, out : & mut Output) { self.0.write(out); $(out.put(out
.separator); self.$id .write(out);)* } }
};
}
tuple_writable! {
T
}
tuple_writable! {
T U : 1
}
tuple_writable! {
T U : 1 V : 2
}
tuple_writable! {
T U : 1 V : 2 X : 3
}
tuple_writable! {
T U : 1 V : 2 X : 3 Y : 4
}
tuple_writable! {
T U : 1 V : 2 X : 3 Y : 4 Z : 5
}
tuple_writable! {
T U : 1 V : 2 X : 3 Y : 4 Z : 5 A : 6
}
tuple_writable! {
T U : 1 V : 2 X : 3 Y : 4 Z : 5 A : 6 B : 7
}
tuple_writable! {
T U : 1 V : 2 X : 3 Y : 4 Z : 5 A : 6 B : 7 C : 8
}
impl<T: Writable> Writable for Option<T> {
fn write(&self, output: &mut Output) {
match self {
None => (-1).write(output),
Some(t) => t.write(output),
}
}
}
impl Writable for bool {
fn write(&self, output: &mut Output) {
let bool_output = output.bool_output;
bool_output.output(output, *self)
}
}
impl<T: Writable> Writable for Reverse<T> {
fn write(&self, output: &mut Output) {
self.0.write(output);
}
}
}
}
pub mod misc {
pub mod lazy_lock {
use std::cell::UnsafeCell;
use std::mem::ManuallyDrop;
use std::ops::Deref;
use std::sync::Once;
union Data<T, F> {
value: ManuallyDrop<T>,
f: ManuallyDrop<F>,
}
pub struct LazyLock<T, F = fn() -> T> {
once: Once,
data: UnsafeCell<Data<T, F>>,
}
impl<T, F: FnOnce() -> T> LazyLock<T, F> {
#[inline]
pub const fn new(f: F) -> LazyLock<T, F> {
LazyLock {
once: Once::new(),
data: UnsafeCell::new(Data { f: ManuallyDrop::new(f) }),
}
}
#[inline]
pub fn force(this: &LazyLock<T, F>) -> &T {
this.once
.call_once(|| {
let data = unsafe { &mut *this.data.get() };
let f = unsafe { ManuallyDrop::take(&mut data.f) };
let value = f();
data.value = ManuallyDrop::new(value);
});
unsafe { &(*this.data.get()).value }
}
}
impl<T, F: FnOnce() -> T> Deref for LazyLock<T, F> {
type Target = T;
#[inline]
fn deref(&self) -> &T {
LazyLock::force(self)
}
}
unsafe impl<T: Sync + Send, F: Send> Sync for LazyLock<T, F> {}
}
pub mod owned_cell {
use std::cell::UnsafeCell;
pub struct OwnedCell<T>(UnsafeCell<T>);
impl<T> OwnedCell<T> {
pub fn new(val: T) -> Self {
Self(UnsafeCell::new(val))
}
pub unsafe fn as_ref<'a>(&self) -> &'a T {
&*self.0.get()
}
pub unsafe fn as_mut<'a>(&self) -> &'a mut T {
&mut *self.0.get()
}
pub unsafe fn replace(&self, new_val: T) -> T {
std::mem::replace(self.as_mut(), new_val)
}
}
}
pub mod recursive_function {
use std::marker::PhantomData;
macro_rules! recursive_function {
($name:ident, $trait:ident, ($($type:ident $arg:ident,)*)) => {
pub trait $trait <$($type,)* Output > { fn call(& mut self, $($arg : $type,)*) ->
Output; } pub struct $name < F, $($type,)* Output > where F : FnMut(& mut dyn
$trait <$($type,)* Output >, $($type,)*) -> Output, { f : std::cell::UnsafeCell <
F >, $($arg : PhantomData <$type >,)* phantom_output : PhantomData < Output >, }
impl < F, $($type,)* Output > $name < F, $($type,)* Output > where F : FnMut(&
mut dyn $trait <$($type,)* Output >, $($type,)*) -> Output, { pub fn new(f : F)
-> Self { Self { f : std::cell::UnsafeCell::new(f), $($arg :
Default::default(),)* phantom_output : Default::default(), } } } impl < F,
$($type,)* Output > $trait <$($type,)* Output > for $name < F, $($type,)* Output
> where F : FnMut(& mut dyn $trait <$($type,)* Output >, $($type,)*) -> Output, {
fn call(& mut self, $($arg : $type,)*) -> Output { unsafe { (* self.f.get())
(self, $($arg,)*) } } }
};
}
recursive_function!(RecursiveFunction0, Callable0, ());
recursive_function!(RecursiveFunction, Callable, (Arg arg,));
recursive_function!(RecursiveFunction2, Callable2, (Arg1 arg1, Arg2 arg2,));
recursive_function!(RecursiveFunction3, Callable3, (Arg1 arg1, Arg2 arg2, Arg3 arg3,));
recursive_function!(
RecursiveFunction4, Callable4, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4,)
);
recursive_function!(
RecursiveFunction5, Callable5, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5
arg5,)
);
recursive_function!(
RecursiveFunction6, Callable6, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5
arg5, Arg6 arg6,)
);
recursive_function!(
RecursiveFunction7, Callable7, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5
arg5, Arg6 arg6, Arg7 arg7,)
);
recursive_function!(
RecursiveFunction8, Callable8, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5
arg5, Arg6 arg6, Arg7 arg7, Arg8 arg8,)
);
recursive_function!(
RecursiveFunction9, Callable9, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5
arg5, Arg6 arg6, Arg7 arg7, Arg8 arg8, Arg9 arg9,)
);
}
pub mod test_type {
pub enum TestType {
Single,
MultiNumber,
MultiEof,
}
pub enum TaskType {
Classic,
Interactive,
}
}
pub mod value {
use std::hash::Hash;
pub trait Value<T>: Copy + Ord + Hash + Default {
fn val() -> T;
}
pub trait ConstValue<T>: Value<T> {
const VAL: T;
}
impl<T, V: ConstValue<T>> Value<T> for V {
fn val() -> T {
Self::VAL
}
}
#[macro_export]
macro_rules! value {
($v:vis $name:ident : $t:ty = $val:expr) => {
#[derive(Copy, Clone, Eq, PartialEq, Hash, Ord, PartialOrd, Default)] $v struct
$name {} impl $crate ::algo_lib::misc::value::ConstValue <$t > for $name { const
VAL : $t = $val; }
};
}
pub trait DynamicValue<T>: Value<T> {
fn set(t: T);
}
#[macro_export]
macro_rules! dynamic_value {
($v:vis $name:ident : $t:ty) => {
thread_local! { #[allow(non_upper_case_globals)] static $name : std::cell::Cell <
Option <$t >> = std::cell::Cell::new(None); } #[derive(Copy, Clone, Eq,
PartialEq, Ord, PartialOrd, Hash, Default)] $v struct $name {} impl $crate
::algo_lib::misc::value::DynamicValue <$t > for $name { fn set(t : $t) { $name
.with(| c | c.set(Some(t))); } } impl $crate ::algo_lib::misc::value::Value <$t >
for $name { fn val() -> $t { $name .with(| c | c.get().unwrap()) } }
};
($v:vis $name:ident : $t:ty = $val:expr) => {
dynamic_value!($v $name : $t); <$name as $crate
::algo_lib::misc::value::DynamicValue <$t >>::set($val);
};
}
}
pub mod when {
#[macro_export]
macro_rules! when {
{$($cond:expr => $then:expr,)*} => {
match () { $(_ if $cond => $then,)* _ => unreachable!(), }
};
{$($cond:expr => $then:expr,)* else $(=>)? $else:expr $(,)?} => {
match () { $(_ if $cond => $then,)* _ => $else, }
};
}
}
}
pub mod numbers {
pub mod gcd {
use crate::algo_lib::numbers::num_traits::algebra::{
IntegerMultiplicationMonoid, IntegerSemiRingWithSub, Zero,
};
use std::mem::swap;
pub fn extended_gcd<T: IntegerSemiRingWithSub + Copy>(a: T, b: T) -> (T, T, T) {
if a == T::zero() {
(b, T::zero(), T::one())
} else {
let (d, y, mut x) = extended_gcd(b % a, a);
x -= b / a * y;
(d, x, y)
}
}
pub fn gcd<T: Copy + Zero + IntegerMultiplicationMonoid>(mut a: T, mut b: T) -> T {
while b != T::zero() {
a %= b;
swap(&mut a, &mut b);
}
a
}
pub fn lcm<T: Copy + Zero + IntegerMultiplicationMonoid>(a: T, b: T) -> T {
(a / gcd(a, b)) * b
}
pub fn remainder<T: IntegerSemiRingWithSub + Copy>(
a1: T,
n1: T,
a2: T,
n2: T,
) -> Option<T> {
let (d, m1, m2) = extended_gcd(n1, n2);
if (a2 - a1) % d != T::zero() {
return None;
}
let m = lcm(n1, n2);
Some(((a1 * m2) % n1 * n2 + (a2 * m1) % n2 * n1) % m)
}
}
pub mod mod_int {
use crate::algo_lib::collections::fx_hash_map::FxHashMap;
use crate::algo_lib::io::input::{Input, Readable};
use crate::algo_lib::io::output::{Output, Writable};
use crate::algo_lib::misc::value::Value;
use crate::algo_lib::numbers::gcd::extended_gcd;
use crate::algo_lib::numbers::num_traits::algebra::{Field, One, Zero};
use crate::algo_lib::numbers::num_traits::as_index::AsIndex;
use crate::algo_lib::numbers::num_traits::invertible::Invertible;
use crate::{value, when};
use std::fmt::{Display, Formatter};
use std::hash::Hash;
use std::marker::PhantomData;
use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};
pub trait BaseModInt<T>: Field + Copy {
fn from(v: T) -> Self;
fn module() -> T;
fn value(&self) -> T;
}
macro_rules! mod_int {
($name:ident, $t:ty, $s:ty, $w:ty) => {
#[derive(Copy, Clone, Eq, PartialEq, Hash, Default)] pub struct $name < V : Value
<$t >> { n : $t, phantom : PhantomData < V >, } impl < V : Value <$t >> $name < V
> { unsafe fn unchecked_new(n : $t) -> Self { debug_assert!(n < V::val()); Self {
n, phantom : Default::default(), } } unsafe fn maybe_subtract_mod(mut n : $t) ->
$t { debug_assert!(n < 2 * V::val()); if n >= V::val() { n -= V::val(); } n } }
impl < V : Value <$t >> $name < V > { pub fn new(n : $t) -> Self { unsafe {
Self::unchecked_new(n % (V::val())) } } pub fn new_signed(n : $s) -> Self {
unsafe { Self::unchecked_new(Self::maybe_subtract_mod((n % (V::val() as $s) +
V::val() as $s) as $t,)) } } pub fn val(& self) -> $t { self.n } } impl < V :
Value <$t >> $name < V > { pub fn log(& self, alpha : Self) -> $t { let mut base
= FxHashMap::default(); let mut exp = 0; let mut pow = Self::one(); let mut inv =
* self; let alpha_inv = alpha.inv().unwrap(); while exp * exp < Self::module() {
if inv == Self::one() { return exp; } base.insert(inv, exp); exp += 1; pow *=
alpha; inv *= alpha_inv; } let step = pow; let mut i = 1; loop { if let Some(b) =
base.get(& pow) { break exp * i + * b; } pow *= step; i += 1; } } } impl < V :
Value <$t >> $name < V > { pub fn new_from_wide(n : $w) -> Self { unsafe {
Self::unchecked_new(Self::maybe_subtract_mod((n % V::val() as $w + V::val() as
$w) as $t,)) } } } impl < V : Value <$t >> Invertible for $name < V > { type
Output = Self; fn inv(& self) -> Option < Self > { let (g, x, _) =
extended_gcd(self.n as $w, V::val() as $w); if g != 1 { None } else {
Some(Self::new_from_wide(x)) } } } impl < V : Value <$t >> BaseModInt <$t > for
$name < V > { fn from(v : $t) -> Self { Self::new(v) } fn module() -> $t {
V::val() } fn value(& self) -> $t { self.n } } impl < V : Value <$t >> From <$t >
for $name < V > { fn from(n : $t) -> Self { Self::new(n) } } impl < V : Value <$t
>> AddAssign for $name < V > { fn add_assign(& mut self, rhs : Self) { self.n =
unsafe { Self::maybe_subtract_mod(self.n + rhs.n) }; } } impl < V : Value <$t >>
Add for $name < V > { type Output = Self; fn add(mut self, rhs : Self) ->
Self::Output { self += rhs; self } } impl < V : Value <$t >> SubAssign for $name
< V > { fn sub_assign(& mut self, rhs : Self) { self.n = unsafe {
Self::maybe_subtract_mod(self.n + V::val() - rhs.n) }; } } impl < V : Value <$t
>> Sub for $name < V > { type Output = Self; fn sub(mut self, rhs : Self) ->
Self::Output { self -= rhs; self } } impl < V : Value <$t >> MulAssign for $name
< V > { fn mul_assign(& mut self, rhs : Self) { self.n = ((self.n as $w) * (rhs.n
as $w) % (V::val() as $w)) as $t; } } impl < V : Value <$t >> Mul for $name < V >
{ type Output = Self; fn mul(mut self, rhs : Self) -> Self::Output { self *= rhs;
self } } impl < V : Value <$t >> DivAssign for $name < V > {
#[allow(clippy::suspicious_op_assign_impl)] fn div_assign(& mut self, rhs : Self)
{ * self *= rhs.inv().unwrap(); } } impl < V : Value <$t >> Div for $name < V > {
type Output = Self; fn div(mut self, rhs : Self) -> Self::Output { self /= rhs;
self } } impl < V : Value <$t >> Neg for $name < V > { type Output = Self; fn
neg(mut self) -> Self::Output { if self.n != 0 { self.n = V::val() - self.n; }
self } } impl < V : Value <$t >> Display for $name < V > { fn fmt(& self, f : &
mut Formatter <'_ >) -> std::fmt::Result { <$t as Display >::fmt(& self.n, f) } }
impl < V : Value <$t >> Readable for $name < V > { fn read(input : & mut Input)
-> Self { Self::new(input.read()) } } impl < V : Value <$t >> Writable for $name
< V > { fn write(& self, output : & mut Output) { self.n.write(output); } } impl
< V : Value <$t >> Zero for $name < V > { fn zero() -> Self { unsafe {
Self::unchecked_new(0) } } } impl < V : Value <$t >> One for $name < V > { fn
one() -> Self { Self::new(1) } } impl < V : Value <$t >> std::fmt::Debug for
$name < V > { fn fmt(& self, f : & mut Formatter) -> std::fmt::Result { let max =
100; when! { self.n <= max => write!(f, "{}", self.n), self.n >= V::val() - max
=> write!(f, "-{}", V::val() - self.n), else => { for denominator in 1..max { for
num in 1..max { if Self::new(num) / Self::new(denominator) == * self { return
write!(f, "{}/{}", num, denominator); } if - Self::new(num) /
Self::new(denominator) == * self { return write!(f, "-{}/{}", num, denominator);
} } } write!(f, "(?? {} ??)", self.n) }, } } } impl < V : Value <$t >> AsIndex
for $name < V > { fn from_index(idx : usize) -> Self { let v = idx as $w; if v >=
V::val() as $w { Self::new_from_wide(v) } else { unsafe { Self::unchecked_new(v
as $t) } } } fn to_index(self) -> usize { self.n.to_index() } }
};
}
mod_int!(ModInt, u32, i32, i64);
mod_int!(ModInt64, u64, i64, i128);
value!(pub Val7 : u32 = 1_000_000_007);
pub type ModInt7 = ModInt<Val7>;
value!(pub Val9 : u32 = 1_000_000_009);
pub type ModInt9 = ModInt<Val9>;
value!(pub ValF : u32 = 998_244_353);
pub type ModIntF = ModInt<ValF>;
pub mod mod_utils {
use crate::algo_lib::numbers::mod_int::{BaseModInt, ModIntF};
use crate::algo_lib::numbers::num_traits::algebra::IntegerMultiplicationMonoid;
use crate::algo_lib::numbers::num_traits::as_index::AsIndex;
use crate::algo_lib::numbers::num_utils::{factorial, factorials};
use std::marker::PhantomData;
pub fn inverses<T: AsIndex + IntegerMultiplicationMonoid, M: BaseModInt<T>>(
len: usize,
) -> Vec<M> {
let mut res = Vec::new();
if len > 0 {
res.push(M::zero());
}
if len > 1 {
res.push(M::one());
}
while res.len() < len {
res.push(
res[M::module().to_index() % res.len()]
* (-M::from(M::module() / (T::from_index(res.len())))),
);
}
res
}
pub fn inverse_factorials<T: AsIndex + IntegerMultiplicationMonoid, M: BaseModInt<T>>(
len: usize,
) -> Vec<M> {
let mut res = inverses(len);
if len > 0 {
res[0] = M::one();
}
for i in 1..len {
let last = res[i - 1];
res[i] *= last;
}
res
}
pub struct Combinations<M: BaseModInt<T> = ModIntF, T: AsIndex = u32> {
fact: Vec<M>,
inv_fact: Vec<M>,
phantom_data: PhantomData<T>,
}
impl<
T: AsIndex + IntegerMultiplicationMonoid,
M: BaseModInt<T> + AsIndex,
> Combinations<M, T> {
pub fn new(len: usize) -> Self {
Self {
fact: factorials(len),
inv_fact: inverse_factorials(len),
phantom_data: PhantomData,
}
}
pub fn c(&self, n: usize, k: usize) -> M {
if n < k {
M::zero()
} else {
self.fact[n] * self.inv_fact[k] * self.inv_fact[n - k]
}
}
pub fn comb_with_rep(&self, n: usize, k: usize) -> M {
self.c(n + k - 1, k)
}
pub fn c_inv(&self, n: usize, k: usize) -> M {
self.inv_fact[n] * self.fact[k] * self.fact[n - k]
}
pub fn fact(&self, n: usize) -> M {
self.fact[n]
}
pub fn inv_fact(&self, n: usize) -> M {
self.inv_fact[n]
}
}
pub fn combinations<T, M: BaseModInt<T> + AsIndex>(n: usize, mut k: usize) -> M {
if k > n {
return M::zero();
}
if k > n - k {
k = n - k;
}
let mut res = M::one();
for i in n - k + 1..=n {
res *= M::from_index(i);
}
res /= factorial(k);
res
}
}
pub mod prime_fft {
use crate::algo_lib::numbers::mod_int::BaseModInt;
use crate::algo_lib::numbers::number_ext::Power;
pub struct PrimeFFT<M: BaseModInt<u32>> {
root: M,
reverse_root: M,
root_power: u32,
aa: Vec<M>,
bb: Vec<M>,
}
impl<M: BaseModInt<u32>> Default for PrimeFFT<M> {
fn default() -> Self {
Self::new()
}
}
impl<M: BaseModInt<u32>> PrimeFFT<M> {
pub fn new() -> Self {
let mut exp = 0;
let mut root_power = 1;
while (M::module() - 1) % (2 * root_power) == 0 {
exp = root_power;
root_power += root_power;
}
let mut i = M::from(2);
let rem = (M::module() - 1) / root_power;
loop {
let j = i.power(rem);
if j.power(exp) != M::one() && j.power(root_power) == M::one() {
break Self {
root: j,
reverse_root: j.inv().unwrap(),
root_power,
aa: Vec::new(),
bb: Vec::new(),
};
}
i += M::one();
}
}
pub fn multiply_res(&mut self, a: &[M], b: &[M], res: &mut Vec<M>) {
if a.is_empty() || b.is_empty() {
res.fill(M::zero());
return;
}
let res_len = a.len() + b.len() - 1;
if res.len() < res_len {
res.resize(res_len, M::zero());
}
self.multiply_fix_len(a, b, res);
}
pub fn multiply_fix_len(&mut self, a: &[M], b: &[M], res: &mut [M]) {
let res_len = res.len();
if a.len().min(b.len()) <= Self::BORDER_LEN {
res.fill(M::zero());
for (i, f) in a.iter().enumerate() {
for (j, s) in b.iter().enumerate() {
if i + j < res.len() {
res[i + j] += (*f) * (*s);
} else {
break;
}
}
}
return;
}
let mut size = 1;
while size < res_len {
size *= 2;
}
if self.root_power < size as u32 {
panic!("unsuitable modulo");
}
copy(&mut self.aa, a, size);
Self::fft(&mut self.aa[..size], false, self.root, self.root_power, size);
if a == b {
for i in self.aa[..size].iter_mut() {
*i *= *i;
}
} else {
copy(&mut self.bb, b, size);
Self::fft(&mut self.bb[..size], false, self.root, self.root_power, size);
for (i, j) in self.aa[..size].iter_mut().zip(self.bb[..size].iter()) {
*i *= *j;
}
}
Self::fft(&mut self.aa[..size], true, self.reverse_root, self.root_power, size);
res.copy_from_slice(&self.aa[..res_len]);
}
pub fn multiply(&mut self, a: &[M], b: &[M]) -> Vec<M> {
if a.is_empty() || b.is_empty() {
Vec::new()
} else {
let mut res = vec![M::zero(); a.len() + b.len() - 1];
self.multiply_res(a, b, &mut res);
res
}
}
pub fn power(&mut self, a: &[M], exp: usize) -> Vec<M> {
let mut res = Vec::new();
let mut temp = Vec::new();
self.power_impl(a, exp, &mut res, &mut temp);
res
}
fn power_impl(&mut self, a: &[M], exp: usize, res: &mut Vec<M>, temp: &mut Vec<M>) {
if exp == 0 {
res.push(M::one());
return;
}
if exp % 2 == 0 {
self.power_impl(a, exp / 2, temp, res);
self.multiply_res(temp, temp, res);
} else {
self.power_impl(a, exp - 1, temp, res);
self.multiply_res(temp, a, res);
}
}
const BORDER_LEN: usize = 80;
fn fft(a: &mut [M], invert: bool, root: M, root_power: u32, size_t: usize) {
let mut j = 0usize;
for i in 1..a.len() {
let mut bit = a.len() >> 1;
while j >= bit {
j -= bit;
bit >>= 1;
}
j += bit;
if i < j {
a.swap(i, j);
}
}
let mut len = 2;
let mut len_t = 2;
while len <= a.len() {
let mut w_len = root;
let mut i = len_t;
while i < root_power {
w_len *= w_len;
i += i;
}
let half = len >> 1;
for i in (0..a.len()).step_by(len) {
let mut w = M::one();
for j in 0..half {
let u = a[i + j];
let v = a[i + j + half] * w;
a[i + j] = u + v;
a[i + j + half] = u - v;
w *= w_len;
}
}
len <<= 1;
len_t += len_t;
}
if invert {
let inv_size = M::from(size_t as u32).inv().unwrap();
for i in a {
*i *= inv_size;
}
}
}
}
fn copy<M: BaseModInt<u32>>(aa: &mut Vec<M>, a: &[M], size: usize) {
if aa.len() < size {
let was_len = aa.len();
aa[..was_len.min(a.len())].copy_from_slice(&a[..was_len.min(a.len())]);
aa[was_len.min(a.len())..].fill(M::zero());
aa.reserve(size - aa.len());
aa.extend_from_slice(&a[was_len.min(a.len())..]);
aa.resize(size, M::zero());
} else {
aa[..a.len()].copy_from_slice(a);
aa[a.len()..size].fill(M::zero());
}
}
}
}
pub mod num_traits {
pub mod algebra {
use crate::algo_lib::numbers::num_traits::invertible::Invertible;
use std::ops::{
Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Rem, RemAssign, Sub, SubAssign,
};
pub trait Zero {
fn zero() -> Self;
}
pub trait One {
fn one() -> Self;
}
pub trait AdditionMonoid: Add<Output = Self> + AddAssign + Zero + Eq + Sized {}
impl<T: Add<Output = Self> + AddAssign + Zero + Eq> AdditionMonoid for T {}
pub trait AdditionMonoidWithSub: AdditionMonoid + Sub<Output = Self> + SubAssign {}
impl<T: AdditionMonoid + Sub<Output = Self> + SubAssign> AdditionMonoidWithSub for T {}
pub trait AdditionGroup: AdditionMonoidWithSub + Neg<Output = Self> {}
impl<T: AdditionMonoidWithSub + Neg<Output = Self>> AdditionGroup for T {}
pub trait MultiplicationMonoid: Mul<Output = Self> + MulAssign + One + Eq + Sized {}
impl<T: Mul<Output = Self> + MulAssign + One + Eq> MultiplicationMonoid for T {}
pub trait IntegerMultiplicationMonoid: MultiplicationMonoid + Div<
Output = Self,
> + Rem<Output = Self> + DivAssign + RemAssign {}
impl<
T: MultiplicationMonoid + Div<Output = Self> + Rem<Output = Self> + DivAssign
+ RemAssign,
> IntegerMultiplicationMonoid for T {}
pub trait MultiplicationGroup: MultiplicationMonoid + Div<
Output = Self,
> + DivAssign + Invertible<Output = Self> {}
impl<
T: MultiplicationMonoid + Div<Output = Self> + DivAssign + Invertible<Output = Self>,
> MultiplicationGroup for T {}
pub trait SemiRing: AdditionMonoid + MultiplicationMonoid {}
impl<T: AdditionMonoid + MultiplicationMonoid> SemiRing for T {}
pub trait SemiRingWithSub: AdditionMonoidWithSub + SemiRing {}
impl<T: AdditionMonoidWithSub + SemiRing> SemiRingWithSub for T {}
pub trait Ring: SemiRing + AdditionGroup {}
impl<T: SemiRing + AdditionGroup> Ring for T {}
pub trait IntegerSemiRing: SemiRing + IntegerMultiplicationMonoid {}
impl<T: SemiRing + IntegerMultiplicationMonoid> IntegerSemiRing for T {}
pub trait IntegerSemiRingWithSub: SemiRingWithSub + IntegerSemiRing {}
impl<T: SemiRingWithSub + IntegerSemiRing> IntegerSemiRingWithSub for T {}
pub trait IntegerRing: IntegerSemiRing + Ring {}
impl<T: IntegerSemiRing + Ring> IntegerRing for T {}
pub trait Field: Ring + MultiplicationGroup {}
impl<T: Ring + MultiplicationGroup> Field for T {}
macro_rules! zero_one_integer_impl {
($($t:ident)+) => {
$(impl Zero for $t { fn zero() -> Self { 0 } } impl One for $t { fn one() -> Self
{ 1 } })+
};
}
zero_one_integer_impl!(i128 i64 i32 i16 i8 isize u128 u64 u32 u16 u8 usize);
}
pub mod as_index {
pub trait AsIndex {
fn from_index(idx: usize) -> Self;
fn to_index(self) -> usize;
}
macro_rules! from_index_impl {
($($t:ident)+) => {
$(impl AsIndex for $t { fn from_index(idx : usize) -> Self { idx as $t } fn
to_index(self) -> usize { self as usize } })+
};
}
from_index_impl!(i128 i64 i32 i16 i8 isize u128 u64 u32 u16 u8 usize);
}
pub mod invertible {
pub trait Invertible {
type Output;
fn inv(&self) -> Option<Self::Output>;
}
}
}
pub mod num_utils {
use crate::algo_lib::numbers::num_traits::algebra::{
AdditionMonoid, IntegerSemiRingWithSub, MultiplicationMonoid,
};
use crate::algo_lib::numbers::num_traits::as_index::AsIndex;
pub fn factorials<T: MultiplicationMonoid + Copy + AsIndex>(len: usize) -> Vec<T> {
let mut res = Vec::new();
if len > 0 {
res.push(T::one());
}
while res.len() < len {
res.push((*res.last().unwrap()) * T::from_index(res.len()));
}
res
}
pub fn powers<T: MultiplicationMonoid + Copy>(base: T, len: usize) -> Vec<T> {
let mut res = Vec::new();
if len > 0 {
res.push(T::one());
}
while res.len() < len {
res.push((*res.last().unwrap()) * base);
}
res
}
pub struct Powers<T: MultiplicationMonoid + Copy> {
small: Vec<T>,
big: Vec<T>,
}
impl<T: MultiplicationMonoid + Copy> Powers<T> {
pub fn new(base: T, len: usize) -> Self {
let small = powers(base, len);
let big = powers(small[len - 1] * base, len);
Self { small, big }
}
pub fn power(&self, exp: usize) -> T {
debug_assert!(exp < self.small.len() * self.small.len());
self.big[exp / self.small.len()] * self.small[exp % self.small.len()]
}
}
pub fn factorial<T: MultiplicationMonoid + AsIndex>(n: usize) -> T {
let mut res = T::one();
for i in 1..=n {
res *= T::from_index(i);
}
res
}
pub trait PartialSums<T> {
fn partial_sums(&self) -> Vec<T>;
}
impl<T: AdditionMonoid + Copy> PartialSums<T> for [T] {
fn partial_sums(&self) -> Vec<T> {
let mut res = Vec::with_capacity(self.len() + 1);
res.push(T::zero());
for i in self.iter() {
res.push(*res.last().unwrap() + *i);
}
res
}
}
pub trait UpperDiv {
fn upper_div(self, other: Self) -> Self;
}
impl<T: IntegerSemiRingWithSub + Copy> UpperDiv for T {
fn upper_div(self, other: Self) -> Self {
(self + other - Self::one()) / other
}
}
}
pub mod number_ext {
use crate::algo_lib::numbers::num_traits::algebra::{
IntegerSemiRing, MultiplicationMonoid,
};
use crate::algo_lib::numbers::num_traits::as_index::AsIndex;
use std::ops::Mul;
pub trait Power {
#[must_use]
fn power<T: IntegerSemiRing + Copy>(&self, exp: T) -> Self;
}
impl<S: MultiplicationMonoid + Copy> Power for S {
fn power<T: IntegerSemiRing + Copy>(&self, exp: T) -> Self {
if exp == T::zero() {
S::one()
} else {
let mut res = self.power(exp / (T::one() + T::one()));
res *= res;
if exp % (T::one() + T::one()) == T::one() {
res *= *self;
}
res
}
}
}
pub fn num_digs<S: IntegerSemiRing + AsIndex + Copy>(mut copy: S) -> usize {
let ten = S::from_index(10);
let mut res = 0;
while copy != S::zero() {
copy /= ten;
res += 1;
}
res
}
pub fn sum_digs<S: IntegerSemiRing + AsIndex + Copy>(mut copy: S) -> S {
let ten = S::from_index(10);
let mut res = S::zero();
while copy != S::zero() {
res += copy % ten;
copy /= ten;
}
res
}
pub fn digits<S: IntegerSemiRing + AsIndex + Copy>(
mut copy: S,
) -> impl Iterator<Item = S> {
let ten = S::from_index(10);
std::iter::from_fn(move || {
if copy == S::zero() {
None
} else {
let res = copy % ten;
copy /= ten;
Some(res)
}
})
}
pub trait Square {
fn square(self) -> Self;
}
impl<T: Mul<Output = T> + Copy> Square for T {
fn square(self) -> Self {
self * self
}
}
}
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 2304kb
input:
5 1 2 1 3 2 4 2 5
output:
28 54 38 0 0
result:
ok 5 number(s): "28 54 38 0 0"
Test #2:
score: 0
Accepted
time: 0ms
memory: 2176kb
input:
10 6 10 5 9 10 3 9 10 7 4 4 1 3 2 3 7 8 4
output:
11540 253870 957220 1439080 737000 230090 0 0 0 0
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 2176kb
input:
10 8 4 4 7 3 1 6 10 6 4 9 10 2 5 5 6 9 1
output:
7140 204390 1027380 1597560 731880 60450 0 0 0 0
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 2176kb
input:
10 2 4 2 5 8 9 7 10 10 9 2 8 3 9 1 3 6 10
output:
14200 210620 1137900 1210580 811660 243840 0 0 0 0
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 2048kb
input:
9 9 8 4 1 9 1 2 7 8 5 8 7 6 5 1 3
output:
2472 34356 162036 107292 56724 0 0 0 0
result:
ok 9 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 2176kb
input:
10 3 8 4 7 8 6 4 6 6 10 9 1 3 2 4 5 9 10
output:
8800 148400 1210800 1396880 798640 65280 0 0 0 0
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 2176kb
input:
15 14 9 7 13 7 8 3 6 1 15 4 15 7 11 8 1 2 7 14 8 15 5 10 6 2 10 12 1
output:
56289600 967779134 923981730 96060068 10686262 235209478 265673053 195831107 217488197 0 0 0 0 0 0
result:
ok 15 numbers
Test #8:
score: 0
Accepted
time: 0ms
memory: 2176kb
input:
15 6 9 10 12 6 10 7 15 9 7 8 15 4 12 11 1 13 6 2 9 3 12 1 3 9 14 7 5
output:
31011120 397655661 546345792 817109204 257395717 479471757 323343241 216283820 898626670 0 0 0 0 0 0
result:
ok 15 numbers
Test #9:
score: 0
Accepted
time: 0ms
memory: 2176kb
input:
15 9 3 9 5 9 6 11 15 5 11 4 14 1 15 2 1 13 14 8 1 9 7 7 14 10 2 12 2
output:
7023120 201832948 304836830 97923512 115869813 704294252 680848885 806741309 252218772 795653541 0 0 0 0 0
result:
ok 15 numbers
Test #10:
score: 0
Accepted
time: 0ms
memory: 2048kb
input:
14 5 4 3 7 9 4 3 8 10 9 1 2 10 7 4 11 14 2 5 1 2 12 4 13 6 11
output:
1277136 187034232 817102492 231238823 482826933 368166096 908219189 329900647 0 0 0 0 0 0
result:
ok 14 numbers
Test #11:
score: 0
Accepted
time: 0ms
memory: 1920kb
input:
15 9 12 1 9 13 10 7 4 11 6 7 3 14 1 11 3 15 14 11 10 2 10 5 12 1 13 12 8
output:
9790200 299361307 878733115 457013044 633916410 202070873 627253395 427436036 431668602 0 0 0 0 0 0
result:
ok 15 numbers
Test #12:
score: 0
Accepted
time: 0ms
memory: 2304kb
input:
30 21 17 4 6 30 28 12 19 3 6 18 11 5 17 13 30 3 27 5 28 7 30 3 25 3 7 27 24 4 16 20 26 30 1 5 9 9 2 23 12 13 20 17 19 22 14 18 20 17 14 11 29 10 27 15 23 11 8
output:
476665504 833146853 594913132 343840733 858440316 821830796 654815681 964050488 845418488 904523186 295267527 167669554 262061667 391216026 785126836 458297537 593077098 789556990 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 30 numbers
Test #13:
score: 0
Accepted
time: 0ms
memory: 2176kb
input:
30 13 21 15 29 9 3 22 8 3 15 15 25 14 8 19 8 24 27 28 4 12 27 8 18 28 25 24 25 8 9 21 5 7 17 11 23 11 16 3 11 26 10 10 16 8 7 11 20 27 21 26 30 15 6 1 6 2 28
output:
249311566 811045480 794072210 750170140 651800148 196077467 477989528 572918836 242191488 523238077 544740575 334825331 251208738 982415005 179148017 25972277 259519791 198540679 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 30 numbers
Test #14:
score: 0
Accepted
time: 0ms
memory: 2176kb
input:
30 10 11 7 29 9 30 4 12 20 18 30 15 3 30 18 16 23 1 22 6 29 25 29 5 16 14 25 27 15 13 24 5 14 22 23 5 1 19 2 11 7 15 26 29 12 21 26 14 12 20 15 28 27 10 17 26 8 26
output:
951802166 75337913 968695388 666501385 268553896 268591487 700091004 819234540 144322774 215302608 21960660 240875748 383482009 549084481 792698573 853681515 56586856 68382350 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 30 numbers
Test #15:
score: 0
Accepted
time: 0ms
memory: 2176kb
input:
29 5 13 18 19 7 2 10 16 2 3 28 22 17 14 25 29 14 8 27 17 9 6 15 11 7 20 8 1 15 12 13 18 9 26 10 23 10 5 17 7 9 24 10 17 21 29 22 1 16 24 4 28 20 21 20 11
output:
183093936 736732472 832827292 220921133 411064273 11608335 442961727 541248342 443664563 614435954 805482321 716726563 537008113 6091735 691949655 359540208 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 29 numbers
Test #16:
score: 0
Accepted
time: 0ms
memory: 2304kb
input:
30 1 17 27 23 2 19 28 7 17 22 20 23 9 27 9 5 11 13 7 24 9 11 13 28 16 9 8 3 22 16 29 16 8 24 22 18 22 14 10 11 13 6 4 18 21 9 25 28 17 12 16 30 27 15 24 2 26 24
output:
808671184 292518367 616199530 559639988 739602615 50200053 943966753 160098660 786551596 68220094 4828146 85859498 850152734 502065476 849914909 707591022 19104728 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 30 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 2176kb
input:
30 2 1 3 1 1 4 4 5 6 5 4 7 8 6 9 8 9 10 9 11 9 12 11 13 14 11 12 15 13 16 15 17 18 17 19 16 19 20 20 21 19 22 22 23 22 24 22 25 26 24 24 27 28 26 29 26 27 30
output:
797780008 686571598 512601217 172589162 229077536 547622293 778878933 995407067 370565763 781815547 856193170 12039270 113119304 865952842 482288625 709423510 10626583 120877278 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 30 numbers
Test #18:
score: 0
Accepted
time: 2ms
memory: 2176kb
input:
70 48 32 5 25 9 43 42 18 13 35 32 28 17 66 53 36 21 52 47 17 20 34 67 13 34 40 52 36 49 50 11 66 30 32 44 43 20 51 47 56 6 66 11 24 69 50 39 19 11 30 9 62 18 21 68 34 69 39 28 10 14 24 4 30 67 47 44 6 66 22 65 1 42 16 59 8 12 50 32 45 24 60 46 17 69 8 43 41 33 61 27 2 22 2 8 67 60 52 55 15 13 61 37 ...
output:
943526961 320961617 166604850 701811460 389268693 738553375 215044618 451762417 891005935 810701751 125288699 585534137 985892828 931011067 707058487 7650954 536390154 943272279 709112563 723959681 929197521 402121766 553250601 260050045 712455754 1522617 370081754 452796510 644890353 36138167 57584...
result:
ok 70 numbers
Test #19:
score: 0
Accepted
time: 4ms
memory: 2176kb
input:
70 55 32 44 27 40 6 52 42 39 67 56 64 21 43 7 48 62 59 1 26 31 13 44 1 18 39 15 64 46 48 28 5 12 47 39 19 30 66 43 56 37 22 4 26 2 40 9 2 34 12 18 15 18 6 28 68 30 40 37 31 30 57 24 52 43 47 22 15 20 29 47 62 18 10 2 70 61 12 47 28 1 52 23 38 58 16 4 49 49 28 57 3 23 24 15 17 70 16 51 8 31 69 60 29 ...
output:
25910015 163992214 232378033 119711775 187475131 195677641 426749502 361226824 176083776 463491958 727433469 889576680 332436759 809785997 718639576 39870971 540913995 428104678 799845288 976730249 521491333 365953390 479106938 328510082 604649102 755282530 253636597 836671759 332287833 682395480 50...
result:
ok 70 numbers
Test #20:
score: 0
Accepted
time: 2ms
memory: 2304kb
input:
69 63 5 59 5 4 15 52 14 57 60 7 34 9 68 33 62 62 31 59 27 29 60 64 58 63 39 27 30 1 39 55 62 69 47 68 17 6 46 26 1 50 25 35 56 37 46 59 12 30 2 35 24 19 16 64 21 51 43 55 41 37 58 55 16 41 67 7 11 35 66 28 58 13 17 54 32 3 44 67 21 54 68 42 1 35 4 23 69 39 8 53 61 23 10 27 52 54 35 59 46 43 53 34 46...
output:
433178845 749347039 483550824 961302408 490763456 38943809 258235571 249129284 529624467 919699700 478839438 51132901 227139138 693529588 232856595 372323915 931822866 275207593 647509343 892538620 833150204 409551669 583012730 465413566 580934706 626121538 241910322 407826554 329925651 11988244 568...
result:
ok 69 numbers
Test #21:
score: 0
Accepted
time: 4ms
memory: 2176kb
input:
70 16 59 15 31 4 36 1 16 68 9 64 23 52 25 51 25 27 9 7 44 49 65 35 37 21 26 32 4 33 37 69 7 58 62 41 44 54 30 19 21 45 12 13 44 51 33 64 33 10 16 69 64 24 16 5 61 58 69 38 11 69 30 45 18 9 24 56 35 1 51 40 13 6 69 3 40 20 46 50 64 61 68 49 29 22 58 15 63 68 55 70 23 29 22 70 42 35 14 21 17 66 1 22 1...
output:
913892556 512515359 307932596 208166439 923812488 787814883 926522725 861402576 943667618 243713276 714542402 21996395 555468493 726536623 346707943 782684467 820344669 880144284 606053876 228354729 25060139 991208882 163764214 614834489 971165918 436603249 472900353 884414168 364542656 330974777 32...
result:
ok 70 numbers
Test #22:
score: 0
Accepted
time: 3ms
memory: 2432kb
input:
70 2 1 3 1 3 4 3 5 6 3 7 6 8 6 9 7 10 7 10 11 12 11 10 13 13 14 15 13 13 16 17 15 18 17 17 19 17 20 21 18 21 22 23 22 21 24 25 22 26 25 27 24 28 26 27 29 30 28 28 31 32 31 30 33 34 33 35 32 36 33 34 37 35 38 39 38 38 40 39 41 41 42 43 40 41 44 42 45 45 46 45 47 45 48 49 46 50 48 48 51 52 50 53 50 54...
output:
770169934 954555437 202257555 347334878 830323432 768480462 270384736 663728843 213556185 822256151 64172800 679424659 434554033 132510570 315113252 187753192 669137644 184968401 682886109 217514370 981985189 19129665 347549366 96071198 773619812 940957399 146067192 241287331 513595468 194094689 270...
result:
ok 70 numbers
Test #23:
score: 0
Accepted
time: 3ms
memory: 2432kb
input:
70 63 48 17 68 8 15 31 51 23 9 19 27 10 2 51 53 56 5 59 7 42 14 36 45 58 41 24 52 70 21 29 42 16 40 35 38 51 57 50 24 54 29 47 20 36 41 51 70 51 12 32 23 68 51 28 11 19 43 58 55 61 35 6 69 65 10 38 32 5 25 42 67 45 10 43 68 64 54 36 9 13 11 3 56 43 58 45 64 69 42 46 69 70 25 49 53 3 59 25 34 9 44 62...
output:
264422203 259298436 524867369 934958379 512456582 915748464 236380955 958526478 624343335 46856122 857595835 988798351 913132871 742485039 771978513 861720636 383944358 713516744 979650053 426134061 462415499 160845205 625982509 264284599 857319056 336185780 669646687 739448821 735484325 401233653 2...
result:
ok 70 numbers
Test #24:
score: 0
Accepted
time: 684ms
memory: 8832kb
input:
499 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 5...
output:
154029661 845001665 588557122 331004513 87119293 243589628 266481846 147445671 723892377 953399570 23874206 699082355 636337437 324612961 626615378 446859683 694059168 787587513 149004470 635734612 621444756 210884890 779365620 551506117 15704724 403748771 906444429 246784225 846106948 640128219 739...
result:
ok 499 numbers
Test #25:
score: 0
Accepted
time: 671ms
memory: 8832kb
input:
498 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 5...
output:
576137007 698536 705959869 459350169 613887621 376422552 900328015 918425372 851033096 643279868 515045927 107782280 474198026 593065562 958399880 98812746 600959826 162247473 259978802 763053996 89480037 867722997 92715192 529872829 910853989 935119642 95654181 955573778 151180755 97383478 30815805...
result:
ok 498 numbers
Test #26:
score: 0
Accepted
time: 496ms
memory: 7552kb
input:
449 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 5...
output:
751815647 426017185 189946231 837605210 831032354 558518285 609712385 770376473 693334904 134936351 532982601 250533254 139517032 523182123 20943426 27206945 383519608 556767776 27517590 500413486 826823026 418022166 434103911 995245814 561462243 103918631 698821468 459687218 593594456 251057760 800...
result:
ok 449 numbers
Test #27:
score: 0
Accepted
time: 342ms
memory: 6528kb
input:
398 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 5...
output:
816865800 985467713 971327665 632395692 196446727 434030679 627560633 627485844 690518955 454995971 243792985 450549538 100043661 886174999 104714586 987473276 24532275 653353159 139211535 243040095 979920292 162798353 813215115 604552457 213219564 149285135 67591743 54703787 644578633 662367371 938...
result:
ok 398 numbers
Test #28:
score: 0
Accepted
time: 47ms
memory: 3584kb
input:
205 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 5...
output:
753130417 109881001 685399927 861559523 151807032 22067972 614582330 316790429 378783717 575992167 91660065 720021539 865352199 971813962 435797246 865719812 619611866 937412322 908785703 927403083 612136223 897290670 901657475 401254407 359043429 459501291 47347742 420861174 906213402 353842071 581...
result:
ok 205 numbers
Test #29:
score: 0
Accepted
time: 176ms
memory: 4864kb
input:
317 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 5...
output:
537692343 70332772 131269515 673005701 470271276 733808699 437387223 925852785 517665139 598305587 815114704 735338355 630639875 169905755 142417305 877665425 232910454 933440866 86065313 658117379 740478559 66328597 653130205 664013451 540141148 375663590 811732978 974656532 822687271 842318519 648...
result:
ok 317 numbers
Test #30:
score: 0
Accepted
time: 41ms
memory: 3584kb
input:
195 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 5...
output:
77748471 398477838 589876897 629903989 552184816 787052062 874959254 688197019 964544174 66654714 385501062 703342362 923033837 26511983 988277234 187746498 191143482 840098727 119964152 811499910 309252543 763245158 468083088 423007512 670157523 205395175 724354927 254415808 210586892 252761012 319...
result:
ok 195 numbers
Test #31:
score: 0
Accepted
time: 60ms
memory: 2560kb
input:
150 116 71 34 7 65 101 5 46 111 13 137 101 1 55 44 21 38 41 106 137 78 59 100 46 35 28 124 1 89 91 19 68 18 99 138 3 69 84 121 51 86 148 96 8 136 114 78 10 45 59 62 111 17 121 76 133 128 57 10 82 45 22 82 14 62 54 9 12 147 75 93 118 66 100 77 36 48 84 13 108 115 89 29 98 150 99 54 39 2 16 24 104 62 ...
output:
221296425 233619510 597093928 590289712 520646361 398787779 484565637 451952423 966808834 186744490 419775993 552896963 156815267 588385113 462237525 747539400 791215426 62461466 329133131 749412389 946770150 966106474 801575459 480097895 759451763 96057697 309781826 691936385 16597521 943612018 664...
result:
ok 150 numbers
Test #32:
score: 0
Accepted
time: 44ms
memory: 2688kb
input:
150 61 85 45 79 111 108 96 19 76 12 127 104 82 1 117 31 109 57 23 101 51 36 74 137 144 123 34 15 144 53 60 124 98 106 114 45 39 66 54 4 8 37 108 56 58 96 118 43 62 135 127 134 67 123 31 42 10 32 12 105 135 8 16 75 103 119 68 146 18 14 84 117 35 109 54 136 135 50 28 9 148 6 94 42 74 113 79 148 56 13 ...
output:
713725525 805562334 96433020 546123807 550691934 597527928 6533268 108784302 346228487 668175131 725745656 308268308 531991783 504805897 823191919 88577010 559908403 373437029 643168298 582685816 738472610 829730996 92704611 527426356 551119256 512680311 249734977 802231938 430120193 835729579 72788...
result:
ok 150 numbers
Test #33:
score: 0
Accepted
time: 49ms
memory: 2688kb
input:
149 97 65 112 85 97 21 38 85 32 58 4 94 46 87 24 97 96 149 79 95 40 132 112 82 149 34 65 86 114 16 149 68 116 118 61 4 114 38 139 21 55 87 116 79 84 105 107 94 97 142 28 121 112 134 144 41 60 109 114 20 140 7 15 95 136 105 120 31 95 57 36 67 98 131 69 98 95 102 109 7 90 1 82 124 95 30 81 47 7 84 75 ...
output:
98042867 96892318 375476331 826808672 387356478 182904951 224552511 300909834 67785767 440277040 630023108 621935275 500093521 693308446 637811355 460126499 782411882 191034277 114291640 20098658 552825174 692896813 21273264 935546769 696524278 370374643 992604036 460222526 768855555 296709495 79758...
result:
ok 149 numbers
Test #34:
score: 0
Accepted
time: 64ms
memory: 2688kb
input:
150 67 64 16 91 106 96 83 97 6 66 53 64 70 17 97 76 6 112 14 1 37 52 42 78 118 139 97 125 5 62 50 33 81 107 42 116 129 42 63 32 103 124 143 34 23 85 133 35 132 15 117 82 70 27 29 66 142 57 33 49 79 31 146 12 136 126 65 97 64 131 88 145 102 30 150 9 41 8 69 92 66 126 143 128 144 93 40 27 12 65 131 97...
output:
862895765 456420712 402639020 89112608 995034647 608820005 960561754 120569939 231419101 990088535 848221961 910262651 930666128 527873138 347606922 469727448 814427204 644774591 489780107 639337324 629765393 695760351 536267340 159127690 102994880 377510967 123705146 521753217 395619906 902275239 2...
result:
ok 150 numbers
Test #35:
score: 0
Accepted
time: 21ms
memory: 2816kb
input:
150 2 1 1 3 3 4 5 2 6 4 6 7 6 8 8 9 7 10 11 10 9 12 10 13 14 12 13 15 13 16 16 17 18 15 16 19 20 18 21 18 19 22 23 20 22 24 25 24 26 25 27 25 27 28 27 29 30 28 31 28 29 32 33 30 33 34 34 35 36 33 37 34 38 36 39 37 38 40 40 41 42 39 40 43 44 42 44 45 46 43 47 46 48 46 49 46 49 50 51 48 52 50 52 53 52...
output:
920670062 463733942 472140513 386651320 175691980 779851065 972743419 650713153 164206870 690737598 81968990 395149724 99382252 586595508 489378741 783502764 517111220 246324086 47612930 773952049 323656923 176968903 301570017 467644419 59081691 49338463 448048355 90082381 753381881 189847025 747786...
result:
ok 150 numbers
Test #36:
score: 0
Accepted
time: 62ms
memory: 2560kb
input:
150 36 119 42 147 121 60 72 65 69 11 91 4 46 55 39 129 19 136 112 110 147 86 73 84 126 65 98 33 95 111 13 123 101 59 5 42 51 141 64 35 129 101 136 122 119 140 115 27 1 149 77 93 85 143 16 21 107 114 115 18 56 135 133 25 38 51 52 69 102 12 34 56 74 25 36 11 8 105 82 94 32 92 51 144 62 106 51 57 103 2...
output:
850082776 26004871 338267392 751281655 138411800 883677482 879611326 79151046 600215417 244678741 534465903 12453393 959482755 578220125 493219092 852056214 140518474 465654507 482847096 252282939 128985349 205480431 318675845 692762577 866275797 136996062 175465110 512401807 673518901 890548146 384...
result:
ok 150 numbers
Test #37:
score: 0
Accepted
time: 19ms
memory: 2944kb
input:
150 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 5...
output:
863397297 563570776 698316583 440383599 991396522 763829634 23113903 491282516 312338255 649052955 767053627 955088494 935433077 235695296 840027517 835088017 95680139 128426743 911697339 58888643 136149623 665701675 849916677 743050511 301268970 866071625 497117417 770475232 505934278 730317443 895...
result:
ok 150 numbers
Test #38:
score: 0
Accepted
time: 99ms
memory: 2688kb
input:
150 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 27 5...
output:
795549660 575116415 34771012 784418026 567016119 962178455 356109035 805358863 230506273 15689356 285843982 826705870 997188588 568990161 688127903 930740453 788088247 197589842 390445164 105719055 190866841 472055214 129652900 500774519 153294491 277517303 9666229 791923011 721258429 727084906 6832...
result:
ok 150 numbers
Test #39:
score: 0
Accepted
time: 76ms
memory: 2432kb
input:
150 1 2 3 2 4 1 1 5 6 5 7 5 8 6 9 7 10 7 3 11 12 6 13 3 14 2 15 2 16 10 6 17 18 7 19 15 20 1 5 21 10 22 10 23 24 1 3 25 1 26 27 3 28 24 8 29 30 1 19 31 32 5 33 16 34 23 21 35 24 36 37 31 38 15 12 39 29 40 2 41 42 18 26 43 29 44 4 45 18 46 47 45 35 48 49 35 50 11 34 51 17 52 34 53 54 14 55 15 37 56 5...
output:
477892339 861107133 91499080 18411298 828050894 925278484 138752131 923950221 694917313 62650040 13353244 783106978 159036537 611695535 525448272 927188500 758881145 332461574 906090868 263018229 824205178 740612904 97994176 425045475 460658948 881189832 902324169 743475670 1454614 491700138 9382768...
result:
ok 150 numbers
Test #40:
score: 0
Accepted
time: 20ms
memory: 2688kb
input:
150 2 1 3 1 2 4 5 3 3 6 4 7 8 7 9 7 10 7 10 11 9 12 10 13 14 13 15 13 16 14 17 16 15 18 16 19 20 17 20 21 22 19 21 23 23 24 25 22 25 26 26 27 28 27 28 29 27 30 31 30 30 32 33 30 32 34 32 35 33 36 37 34 37 38 39 36 39 40 38 41 40 42 40 43 43 44 45 43 45 46 46 47 45 48 49 48 47 50 51 49 51 52 53 50 54...
output:
392650722 592029195 112331471 474015453 836899789 119059153 643097913 968773580 203367894 260515872 362187408 180805394 320775982 233905889 334788497 544076554 446302051 858931094 165682096 313555562 755816689 829847569 896736777 545716931 968232429 380436982 85523190 910186860 638752557 984428996 9...
result:
ok 150 numbers
Test #41:
score: -100
Time Limit Exceeded
input:
500 223 142 220 10 470 426 370 270 80 297 332 12 420 84 452 154 33 84 500 189 454 67 483 192 218 366 83 337 496 101 393 196 380 236 1 453 442 114 220 245 363 248 26 72 217 263 91 243 65 315 122 455 120 210 263 31 47 327 407 170 253 195 189 471 349 239 393 107 159 217 274 288 261 141 351 381 425 394 ...