QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #310092 | #8133. When Anton Saw This Task He Reacted With 😩 | ucup-team296# | AC ✓ | 3199ms | 44432kb | Rust | 101.3kb | 2024-01-21 01:32:41 | 2024-01-21 01:32:41 |
Judging History
answer
//
pub mod solution {
//{"name":"ucup19_f","group":"Manual","url":"","interactive":false,"timeLimit":2000,"tests":[{"input":"","output":""}],"testType":"single","input":{"type":"stdin","fileName":null,"pattern":null},"output":{"type":"stdout","fileName":null,"pattern":null},"languages":{"java":{"taskClass":"ucup19_f"}}}
use crate::algo_lib::collections::bit_set::BitSet;
use crate::algo_lib::graph::edges::edge::Edge;
use crate::algo_lib::graph::graph::Graph;
use crate::algo_lib::graph::topological_sort::TopologicalSort;
use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::input::Readable;
use crate::algo_lib::io::output::Output;
use crate::algo_lib::numbers::matrix::Matrix;
use crate::algo_lib::numbers::mod_int::ModIntF;
use crate::algo_lib::numbers::num_traits::algebra::One;
use crate::algo_lib::numbers::num_traits::algebra::Zero;
type PreCalc = ();
fn solve(input: &mut Input, out: &mut Output, _test_case: usize, _data: &PreCalc) {
let n = input.read_size();
let q = input.read_size();
type Mod = ModIntF;
#[derive(Clone)]
enum Vertex {
None,
Internal(usize, usize),
Leaf(Mod, Mod, Mod),
Huynya(usize),
}
impl Readable for Vertex {
fn read(input: &mut Input) -> Self {
let tp = input.read_char();
match tp {
'x' => {
let l = input.read::<usize>() - 1;
let r = input.read::<usize>() - 1;
Vertex::Internal(l, r)
}
'v' => {
let a = input.read::<Mod>();
let b = input.read::<Mod>();
let c = input.read::<Mod>();
Vertex::Leaf(a, b, c)
}
_ => unreachable!(),
}
}
}
let mut tree = input.read_vec::<Vertex>(n);
let mut graph = Graph::new(n);
for i in 0..n {
match &tree[i] {
Vertex::Internal(l, r) => {
graph.add_edge(Edge::new(i, *l));
graph.add_edge(Edge::new(i, *r));
}
_ => {}
}
}
let mut mat = vec![Matrix::ident(3); n];
let mut order = graph.topological_sort().unwrap();
order.reverse();
let queries = input.read_vec::<(usize, Mod, Mod, Mod)>(q);
const BUBEN: usize = 350;
let mut condensed_tree = vec![Vertex::None; n];
let mut interesting = BitSet::new(n);
let mut ans = vec![(Mod::zero(), Mod::zero(), Mod::zero()); n];
// let mut temp = Matrix::ident(3);
// let mut res = Matrix::ident(3);
let mut next = vec![0; n];
for i in (0..q).step_by(BUBEN) {
interesting.fill(false);
condensed_tree.fill(Vertex::None);
for j in i..q.min(i + BUBEN) {
interesting.set(queries[j].0 - 1);
}
let mut ord = Vec::new();
for &v in &order {
match &tree[v] {
Vertex::Internal(l, r) => {
interesting.set(v);
if interesting[*l] {
if interesting[*r] {
condensed_tree[v] = Vertex::Internal(*l, *r);
ord.push(*l);
ord.push(*r);
ord.push(v);
} else {
let vert = match &condensed_tree[*l] {
Vertex::Huynya(x) => *x,
_ => {
for i in 0..3 {
for j in 0..3 {
mat[*l][(i, j)] =
if i == j { Mod::one() } else { Mod::zero() };
}
}
*l
}
};
let (wx, wy, wz) = match &condensed_tree[*r] {
Vertex::Leaf(x, y, z) => (*x, *y, *z),
_ => unreachable!(),
};
let t00 = 0;
let t01 = wz.val() as i64;
let t02 = -wy.val() as i64;
let t10 = -wz.val() as i64;
let t11 = 0;
let t12 = wx.val() as i64;
let t20 = wy.val() as i64;
let t21 = -wx.val() as i64;
let t22 = 0;
let m00 = mat[*l][(0, 0)].val() as i64;
let m01 = mat[*l][(0, 1)].val() as i64;
let m02 = mat[*l][(0, 2)].val() as i64;
let m10 = mat[*l][(1, 0)].val() as i64;
let m11 = mat[*l][(1, 1)].val() as i64;
let m12 = mat[*l][(1, 2)].val() as i64;
let m20 = mat[*l][(2, 0)].val() as i64;
let m21 = mat[*l][(2, 1)].val() as i64;
let m22 = mat[*l][(2, 2)].val() as i64;
let m = &mut mat[v];
m[(0, 0)] = Mod::new_from_wide(t00 * m00 + t01 * m10 + t02 * m20);
m[(0, 1)] = Mod::new_from_wide(t00 * m01 + t01 * m11 + t02 * m21);
m[(0, 2)] = Mod::new_from_wide(t00 * m02 + t01 * m12 + t02 * m22);
m[(1, 0)] = Mod::new_from_wide(t10 * m00 + t11 * m10 + t12 * m20);
m[(1, 1)] = Mod::new_from_wide(t10 * m01 + t11 * m11 + t12 * m21);
m[(1, 2)] = Mod::new_from_wide(t10 * m02 + t11 * m12 + t12 * m22);
m[(2, 0)] = Mod::new_from_wide(t20 * m00 + t21 * m10 + t22 * m20);
m[(2, 1)] = Mod::new_from_wide(t20 * m01 + t21 * m11 + t22 * m21);
m[(2, 2)] = Mod::new_from_wide(t20 * m02 + t21 * m12 + t22 * m22);
condensed_tree[v] = Vertex::Huynya(vert);
}
} else {
if interesting[*r] {
let vert = match &condensed_tree[*r] {
Vertex::Huynya(x) => *x,
_ => {
for i in 0..3 {
for j in 0..3 {
mat[*r][(i, j)] =
if i == j { Mod::one() } else { Mod::zero() };
}
}
*r
}
};
let (vx, vy, vz) = match &condensed_tree[*l] {
Vertex::Leaf(x, y, z) => (*x, *y, *z),
_ => unreachable!(),
};
let t00 = 0;
let t01 = -vz.val() as i64;
let t02 = vy.val() as i64;
let t10 = vz.val() as i64;
let t11 = 0;
let t12 = -vx.val() as i64;
let t20 = -vy.val() as i64;
let t21 = vx.val() as i64;
let t22 = 0;
let m00 = mat[*r][(0, 0)].val() as i64;
let m01 = mat[*r][(0, 1)].val() as i64;
let m02 = mat[*r][(0, 2)].val() as i64;
let m10 = mat[*r][(1, 0)].val() as i64;
let m11 = mat[*r][(1, 1)].val() as i64;
let m12 = mat[*r][(1, 2)].val() as i64;
let m20 = mat[*r][(2, 0)].val() as i64;
let m21 = mat[*r][(2, 1)].val() as i64;
let m22 = mat[*r][(2, 2)].val() as i64;
let m = &mut mat[v];
m[(0, 0)] = Mod::new_from_wide(t00 * m00 + t01 * m10 + t02 * m20);
m[(0, 1)] = Mod::new_from_wide(t00 * m01 + t01 * m11 + t02 * m21);
m[(0, 2)] = Mod::new_from_wide(t00 * m02 + t01 * m12 + t02 * m22);
m[(1, 0)] = Mod::new_from_wide(t10 * m00 + t11 * m10 + t12 * m20);
m[(1, 1)] = Mod::new_from_wide(t10 * m01 + t11 * m11 + t12 * m21);
m[(1, 2)] = Mod::new_from_wide(t10 * m02 + t11 * m12 + t12 * m22);
m[(2, 0)] = Mod::new_from_wide(t20 * m00 + t21 * m10 + t22 * m20);
m[(2, 1)] = Mod::new_from_wide(t20 * m01 + t21 * m11 + t22 * m21);
m[(2, 2)] = Mod::new_from_wide(t20 * m02 + t21 * m12 + t22 * m22);
condensed_tree[v] = Vertex::Huynya(vert);
} else {
interesting.unset(v);
let (vx, vy, vz) = match &condensed_tree[*l] {
Vertex::Leaf(x, y, z) => (*x, *y, *z),
_ => unreachable!(),
};
let (wx, wy, wz) = match &condensed_tree[*r] {
Vertex::Leaf(x, y, z) => (*x, *y, *z),
_ => unreachable!(),
};
let vx = vx.val() as i64;
let vy = vy.val() as i64;
let vz = vz.val() as i64;
let wx = wx.val() as i64;
let wy = wy.val() as i64;
let wz = wz.val() as i64;
condensed_tree[v] = Vertex::Leaf(
Mod::new_from_wide(vy * wz - vz * wy),
Mod::new_from_wide(vz * wx - vx * wz),
Mod::new_from_wide(vx * wy - vy * wx),
);
}
}
}
Vertex::Leaf(a, b, c) => {
condensed_tree[v] = Vertex::Leaf(*a, *b, *c);
if interesting[v] {
ord.push(v);
}
}
_ => unreachable!(),
}
}
if let Some(&x) = ord.last() {
if x != 0 {
ord.push(0);
}
}
for &vert in ord.iter() {
match &condensed_tree[vert] {
Vertex::Leaf(a, b, c) => {}
Vertex::Huynya(v) => {
next[*v] = vert;
}
Vertex::Internal(l, r) => {
next[*l] = vert;
next[*r] = vert;
}
_ => unreachable!(),
};
ans[vert] = match &condensed_tree[vert] {
Vertex::Leaf(a, b, c) => (*a, *b, *c),
Vertex::Huynya(v) => {
let (a, b, c) = ans[*v];
let a = a.val() as i64;
let b = b.val() as i64;
let c = c.val() as i64;
let m = &mat[vert];
let m00 = m[(0, 0)].val() as i64;
let m01 = m[(0, 1)].val() as i64;
let m02 = m[(0, 2)].val() as i64;
let m10 = m[(1, 0)].val() as i64;
let m11 = m[(1, 1)].val() as i64;
let m12 = m[(1, 2)].val() as i64;
let m20 = m[(2, 0)].val() as i64;
let m21 = m[(2, 1)].val() as i64;
let m22 = m[(2, 2)].val() as i64;
(
Mod::new_from_wide(m00 * a + m01 * b + m02 * c),
Mod::new_from_wide(m10 * a + m11 * b + m12 * c),
Mod::new_from_wide(m20 * a + m21 * b + m22 * c),
)
}
Vertex::Internal(l, r) => {
let (vx, vy, vz) = ans[*l];
let (wx, wy, wz) = ans[*r];
(vy * wz - vz * wy, vz * wx - vx * wz, vx * wy - vy * wx)
}
_ => unreachable!(),
};
}
for j in i..q.min(i + BUBEN) {
let (v, x, y, z) = queries[j];
condensed_tree[v - 1] = Vertex::Leaf(x, y, z);
tree[v - 1] = Vertex::Leaf(x, y, z);
let mut vert = v - 1;
loop {
ans[vert] = match &condensed_tree[vert] {
Vertex::Leaf(a, b, c) => (*a, *b, *c),
Vertex::Huynya(v) => {
let (a, b, c) = ans[*v];
let a = a.val() as i64;
let b = b.val() as i64;
let c = c.val() as i64;
let m = &mat[vert];
let m00 = m[(0, 0)].val() as i64;
let m01 = m[(0, 1)].val() as i64;
let m02 = m[(0, 2)].val() as i64;
let m10 = m[(1, 0)].val() as i64;
let m11 = m[(1, 1)].val() as i64;
let m12 = m[(1, 2)].val() as i64;
let m20 = m[(2, 0)].val() as i64;
let m21 = m[(2, 1)].val() as i64;
let m22 = m[(2, 2)].val() as i64;
(
Mod::new_from_wide(m00 * a + m01 * b + m02 * c),
Mod::new_from_wide(m10 * a + m11 * b + m12 * c),
Mod::new_from_wide(m20 * a + m21 * b + m22 * c),
)
}
Vertex::Internal(l, r) => {
let (vx, vy, vz) = ans[*l];
let (wx, wy, wz) = ans[*r];
(vy * wz - vz * wy, vz * wx - vx * wz, vx * wy - vy * wx)
}
_ => unreachable!(),
};
if vert == 0 {
break;
}
vert = next[vert];
}
/*let mut rec = RecursiveFunction::new(|rec, vert: usize| -> (Mod, Mod, Mod) {
match &condensed_tree[vert] {
Vertex::Leaf(a, b, c) => (*a, *b, *c),
Vertex::Huynya(v, mat) => {
let (a, b, c) = rec.call(*v);
let res = mat.mult(&Matrix::new(&[&[a], &[b], &[c]]));
(res[(0, 0)], res[(1, 0)], res[(2, 0)])
}
Vertex::Internal(l, r) => {
let (vx, vy, vz) = rec.call(*l);
let (wx, wy, wz) = rec.call(*r);
(vy * wz - vz * wy, vz * wx - vx * wz, vx * wy - vy * wx)
}
_ => unreachable!(),
}
});*/
// out.print_line(rec.call(0));
out.print_line(ans[0]);
}
}
}
pub(crate) fn run(mut input: Input, mut output: Output) -> bool {
let pre_calc = ();
#[allow(dead_code)]
enum TestType {
Single,
MultiNumber,
MultiEof,
}
let test_type = TestType::Single;
match test_type {
TestType::Single => solve(&mut input, &mut output, 1, &pre_calc),
TestType::MultiNumber => {
let t = input.read();
for i in 1..=t {
solve(&mut input, &mut output, i, &pre_calc);
}
}
TestType::MultiEof => {
let mut i = 1;
while input.peek().is_some() {
solve(&mut input, &mut output, i, &pre_calc);
i += 1;
}
}
}
output.flush();
input.skip_whitespace();
input.peek().is_none()
}
}
pub mod algo_lib {
pub mod collections {
pub mod bit_set {
use crate::algo_lib::collections::slice_ext::legacy_fill::LegacyFill;
use crate::algo_lib::numbers::num_traits::bit_ops::BitOps;
use std::ops::BitAndAssign;
use std::ops::BitOrAssign;
use std::ops::Index;
const TRUE: bool = true;
const FALSE: bool = false;
#[derive(Clone, Eq, PartialEq)]
pub struct BitSet {
data: Vec<u64>,
len: usize,
}
impl BitSet {
pub fn new(len: usize) -> Self {
let data_len = if len == 0 {
0
} else {
Self::index(len - 1) + 1
};
Self {
data: vec![0; data_len],
len,
}
}
pub fn from_slice(len: usize, set: &[usize]) -> Self {
let mut res = Self::new(len);
for &i in set {
res.set(i);
}
res
}
pub fn set(&mut self, at: usize) {
assert!(at < self.len);
self.data[Self::index(at)].set_bit(at & 63);
}
pub fn unset(&mut self, at: usize) {
assert!(at < self.len);
self.data[Self::index(at)].unset_bit(at & 63);
}
pub fn change(&mut self, at: usize, value: bool) {
if value {
self.set(at);
} else {
self.unset(at);
}
}
pub fn flip(&mut self, at: usize) {
self.change(at, !self[at]);
}
#[allow(clippy::len_without_is_empty)]
pub fn len(&self) -> usize {
self.len
}
pub fn fill(&mut self, value: bool) {
// 1.43
self.data.legacy_fill(if value { std::u64::MAX } else { 0 })
}
pub fn is_superset(&self, other: &Self) -> bool {
assert_eq!(self.len, other.len);
for i in 0..self.data.len() {
if self.data[i] & other.data[i] != other.data[i] {
return false;
}
}
true
}
pub fn is_subset(&self, other: &Self) -> bool {
other.is_superset(self)
}
pub fn iter(&self) -> impl Iterator<Item = usize> + '_ {
self.into_iter()
}
fn index(at: usize) -> usize {
at >> 6
}
pub fn count_ones(&self) -> usize {
self.data.iter().map(|x| x.count_ones() as usize).sum()
}
}
pub struct BitSetIter<'s> {
at: usize,
inside: usize,
set: &'s BitSet,
}
impl<'s> Iterator for BitSetIter<'s> {
type Item = usize;
fn next(&mut self) -> Option<Self::Item> {
while self.at < self.set.data.len()
&& (self.inside == 64 || (self.set.data[self.at] >> self.inside) == 0)
{
self.at += 1;
self.inside = 0;
}
if self.at == self.set.data.len() {
None
} else {
while !self.set.data[self.at].is_set(self.inside) {
self.inside += 1;
}
let res = self.at * 64 + self.inside;
if res < self.set.len {
self.inside += 1;
Some(res)
} else {
None
}
}
}
}
impl<'a> IntoIterator for &'a BitSet {
type Item = usize;
type IntoIter = BitSetIter<'a>;
fn into_iter(self) -> Self::IntoIter {
BitSetIter {
at: 0,
inside: 0,
set: self,
}
}
}
impl BitOrAssign<&BitSet> for BitSet {
fn bitor_assign(&mut self, rhs: &BitSet) {
assert_eq!(self.len, rhs.len);
for (i, &j) in self.data.iter_mut().zip(rhs.data.iter()) {
*i |= j;
}
}
}
impl BitAndAssign<&BitSet> for BitSet {
fn bitand_assign(&mut self, rhs: &BitSet) {
assert_eq!(self.len, rhs.len);
for (i, &j) in self.data.iter_mut().zip(rhs.data.iter()) {
*i &= j;
}
}
}
impl Index<usize> for BitSet {
type Output = bool;
fn index(&self, at: usize) -> &Self::Output {
assert!(at < self.len);
if self.data[Self::index(at)].is_set(at & 63) {
&TRUE
} else {
&FALSE
}
}
}
impl From<Vec<bool>> for BitSet {
fn from(data: Vec<bool>) -> Self {
let mut res = Self::new(data.len());
for (i, &value) in data.iter().enumerate() {
res.change(i, value);
}
res
}
}
}
pub mod dsu {
use crate::algo_lib::collections::iter_ext::collect::IterCollect;
use crate::algo_lib::collections::slice_ext::bounds::Bounds;
use crate::algo_lib::collections::slice_ext::legacy_fill::LegacyFill;
use std::cell::Cell;
#[derive(Clone)]
pub struct DSU {
id: Vec<Cell<u32>>,
size: Vec<u32>,
count: usize,
}
impl DSU {
pub fn new(n: usize) -> Self {
Self {
id: (0..n).map(|i| Cell::new(i as u32)).collect_vec(),
size: vec![1; n],
count: n,
}
}
pub fn size(&self, i: usize) -> usize {
self.size[self.get(i)] 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 (i as u32) == id.get() {
Some(i)
} else {
None
}
})
}
pub fn set_count(&self) -> usize {
self.count
}
pub fn join(&mut self, mut a: usize, mut b: usize) -> bool {
a = self.get(a);
b = self.get(b);
if a == b {
false
} else {
self.size[a] += self.size[b];
self.id[b].replace(a as u32);
self.count -= 1;
true
}
}
pub fn get(&self, i: usize) -> usize {
if self.id[i].get() != i as u32 {
let res = self.get(self.id[i].get() as usize);
self.id[i].replace(res as u32);
}
self.id[i].get() as usize
}
pub fn clear(&mut self) {
self.count = self.id.len();
self.size.legacy_fill(1);
self.id.iter().enumerate().for_each(|(i, id)| {
id.replace(i as u32);
});
}
pub fn parts(&self) -> Vec<Vec<usize>> {
let roots = self.iter().collect_vec();
let mut res = vec![Vec::new(); roots.len()];
for i in 0..self.id.len() {
res[roots.as_slice().bin_search(&self.get(i)).unwrap()].push(i);
}
res
}
}
}
pub mod iter_ext {
pub mod collect {
pub trait IterCollect<T>: Iterator<Item = T> + Sized {
fn collect_vec(self) -> Vec<T> {
self.collect()
}
}
impl<T, I: Iterator<Item = T> + Sized> IterCollect<T> for I {}
}
}
pub mod md_arr {
pub mod arr2d {
use crate::algo_lib::collections::slice_ext::legacy_fill::LegacyFill;
use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::input::Readable;
use crate::algo_lib::io::output::Output;
use crate::algo_lib::io::output::Writable;
use std::ops::Index;
use std::ops::IndexMut;
use std::ops::Range;
use std::slice::Iter;
use std::vec::IntoIter;
#[derive(Clone, Eq, PartialEq, Default)]
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 generate<F>(d1: usize, d2: usize, mut gen: 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(gen(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) -> impl Iterator<Item = &mut T> {
self.data.iter_mut()
}
pub fn row(&self, row: usize) -> impl Iterator<Item = &T> {
assert!(row < self.d1);
self.data.iter().skip(row * self.d2).take(self.d2)
}
pub fn row_mut(&mut self, row: usize) -> impl Iterator<Item = &mut T> {
assert!(row < self.d1);
self.data.iter_mut().skip(row * self.d2).take(self.d2)
}
pub fn column(&self, col: usize) -> impl Iterator<Item = &T> {
assert!(col < self.d2);
self.data.iter().skip(col).step_by(self.d2)
}
pub fn column_mut(&mut self, col: usize) -> impl Iterator<Item = &mut 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!(r1 < self.d1);
assert!(r2 < self.d1);
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
}
}
impl<T: Clone> Arr2d<T> {
pub fn fill(&mut self, elem: T) {
self.data.legacy_fill(elem);
}
pub fn transpose(&self) -> Self {
Self::generate(self.d2, self.d1, |i, j| self[(j, i)].clone())
}
}
impl<T> Index<(usize, usize)> for Arr2d<T> {
type Output = T;
fn index(&self, (row, col): (usize, usize)) -> &Self::Output {
assert!(row < self.d1);
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!(row < self.d1);
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(b' ');
}
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<char>;
}
impl Arr2dRead for Input<'_> {
fn read_table<T: Readable>(&mut self, d1: usize, d2: usize) -> Arr2d<T> {
Arr2d::generate(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<char> {
self.read_table(d1, d2)
}
}
pub trait Arr2dCharWrite {
fn print_table(&mut self, table: &Arr2d<char>);
}
impl Arr2dCharWrite for Output<'_> {
fn print_table(&mut self, table: &Arr2d<char>) {
let mut at = 0usize;
for _ in 0..table.d1 {
for _ in 0..table.d2 {
self.print(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 {
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;
fn less_or_eq(&self, el: &T) -> usize;
}
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 less(&self, el: &T) -> usize {
self.lower_bound(el)
}
fn less_or_eq(&self, el: &T) -> usize {
self.upper_bound(el)
}
}
}
pub mod legacy_fill {
// 1.50
pub trait LegacyFill<T> {
fn legacy_fill(&mut self, val: T);
}
impl<T: Clone> LegacyFill<T> for [T] {
fn legacy_fill(&mut self, val: T) {
for el in self.iter_mut() {
*el = val.clone();
}
}
}
}
}
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 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;
use crate::algo_lib::graph::edges::edge_id::NoId;
use crate::algo_lib::graph::edges::edge_id::WithId;
use crate::algo_lib::graph::edges::edge_trait::BidirectionalEdgeTrait;
use crate::algo_lib::graph::edges::edge_trait::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;
use crate::algo_lib::graph::edges::edge_id::NoId;
use crate::algo_lib::graph::edges::edge_id::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 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;
use crate::algo_lib::graph::edges::edge_trait::EdgeTrait;
use std::ops::Index;
use std::ops::IndexMut;
#[derive(Clone)]
pub struct Graph<E: EdgeTrait> {
pub(super) 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.edges.len());
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.join(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.join(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 from_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 Graph<BiEdge<()>> {
pub fn from_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
}
}
}
pub mod topological_sort {
use crate::algo_lib::graph::edges::edge_trait::EdgeTrait;
use crate::algo_lib::graph::graph::Graph;
use std::collections::VecDeque;
pub trait TopologicalSort {
fn topological_sort(&self) -> Option<Vec<usize>>;
}
impl<E: EdgeTrait> TopologicalSort for Graph<E> {
fn topological_sort(&self) -> Option<Vec<usize>> {
assert!(!E::REVERSABLE);
let n = self.vertex_count();
let mut res = Vec::with_capacity(n);
let mut degree = vec![0u32; n];
for i in 0..n {
for e in self[i].iter() {
degree[e.to()] += 1;
}
}
let mut queue = VecDeque::new();
for (i, deg) in degree.iter().enumerate() {
if *deg == 0 {
queue.push_back(i);
}
}
while !queue.is_empty() {
let cur = queue.pop_front().unwrap();
res.push(cur);
for e in self[cur].iter() {
let to = e.to();
degree[to] -= 1;
if degree[to] == 0 {
queue.push_back(to);
}
}
}
if res.len() == n {
Some(res)
} else {
None
}
}
}
}
}
pub mod io {
pub mod input {
use crate::algo_lib::collections::vec_ext::default::default_vec;
use std::io::Read;
pub struct Input<'s> {
input: &'s mut dyn Read,
buf: Vec<u8>,
at: usize,
buf_read: usize,
}
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<'s> Input<'s> {
const DEFAULT_BUF_SIZE: usize = 4096;
pub fn new(input: &'s mut dyn Read) -> Self {
Self {
input,
buf: default_vec(Self::DEFAULT_BUF_SIZE),
at: 0,
buf_read: 0,
}
}
pub fn new_with_size(input: &'s mut dyn Read, buf_size: usize) -> Self {
Self {
input,
buf: default_vec(buf_size),
at: 0,
buf_read: 0,
}
}
pub fn get(&mut self) -> Option<u8> {
if self.refill_buffer() {
let res = self.buf[self.at];
self.at += 1;
if res == b'\r' {
if self.refill_buffer() && self.buf[self.at] == b'\n' {
self.at += 1;
}
return Some(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 !char::from(b).is_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 char::from(c).is_whitespace() {
break;
}
res.push(c);
}
if res.is_empty() {
None
} else {
Some(res)
}
}
//noinspection RsSelfConvention
pub fn is_exhausted(&mut self) -> bool {
self.peek().is_none()
}
//noinspection RsSelfConvention
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) -> char {
self.skip_whitespace();
self.get().unwrap().into()
}
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 = self.input.read(&mut self.buf).unwrap();
self.buf_read != 0
} else {
true
}
}
}
pub trait Readable {
fn read(input: &mut Input) -> Self;
}
impl Readable for char {
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)
}
}
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 u8 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}
impl Read for Input<'_> {
fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
if self.at == self.buf_read {
self.input.read(buf)
} else {
let mut i = 0;
while i < buf.len() && self.at < self.buf_read {
buf[i] = self.buf[self.at];
i += 1;
self.at += 1;
}
Ok(i)
}
}
}
}
pub mod output {
use crate::algo_lib::collections::vec_ext::default::default_vec;
use std::io::stderr;
use std::io::Stderr;
use std::io::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,
}
}
}
pub struct Output<'s> {
output: &'s mut dyn Write,
buf: Vec<u8>,
at: usize,
auto_flush: bool,
bool_output: BoolOutput,
}
impl<'s> Output<'s> {
const DEFAULT_BUF_SIZE: usize = 4096;
pub fn new(output: &'s mut dyn Write) -> Self {
Self {
output,
buf: default_vec(Self::DEFAULT_BUF_SIZE),
at: 0,
auto_flush: false,
bool_output: BoolOutput::YesNoCaps,
}
}
pub fn new_with_auto_flush(output: &'s mut dyn Write) -> Self {
Self {
output,
buf: default_vec(Self::DEFAULT_BUF_SIZE),
at: 0,
auto_flush: true,
bool_output: BoolOutput::YesNoCaps,
}
}
pub fn flush(&mut self) {
if self.at != 0 {
self.output.write_all(&self.buf[..self.at]).unwrap();
self.output.flush().unwrap();
self.at = 0;
}
}
pub fn print<T: Writable>(&mut self, s: T) {
s.write(self);
self.maybe_flush();
}
pub fn print_line<T: Writable>(&mut self, s: T) {
self.print(s);
self.put(b'\n');
self.maybe_flush();
}
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 maybe_flush(&mut self) {
if self.auto_flush {
self.flush();
}
}
pub fn print_per_line<T: Writable>(&mut self, arg: &[T]) {
for i in arg {
i.write(self);
self.put(b'\n');
}
}
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(b' ');
}
e.write(self);
}
}
pub fn print_iter_ref<'a, T: 'a + Writable, I: Iterator<Item = &'a T>>(
&mut self,
iter: I,
) {
let mut first = true;
for e in iter {
if first {
first = false;
} else {
self.put(b' ');
}
e.write(self);
}
}
pub fn set_bool_output(&mut self, bool_output: BoolOutput) {
self.bool_output = bool_output;
}
}
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;
}
self.maybe_flush();
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<T: Writable> Writable for [T] {
fn write(&self, output: &mut Output) {
output.print_iter_ref(self.iter());
}
}
impl<T: Writable, const N: usize> Writable for [T; N] {
fn write(&self, output: &mut Output) {
output.print_iter_ref(self.iter());
}
}
impl<T: Writable> 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!(u8 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(b' ');
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}
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)
}
}
static mut ERR: Option<Stderr> = None;
pub fn err() -> Output<'static> {
unsafe {
if ERR.is_none() {
ERR = Some(stderr());
}
Output::new_with_auto_flush(ERR.as_mut().unwrap())
}
}
}
}
pub mod misc {
pub mod value {
use std::hash::Hash;
pub trait Value<T>: Copy + Eq + Hash {
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 {
($name: ident: $t: ty = $val: expr) => {
#[derive(Copy, Clone, Eq, PartialEq, Hash, Ord, PartialOrd, Default)]
pub struct $name {}
impl $crate::algo_lib::misc::value::ConstValue<$t> for $name {
const VAL: $t = $val;
}
};
}
pub trait DynamicValue<T>: Value<T> {
//noinspection RsSelfConvention
fn set_val(t: T);
}
#[macro_export]
macro_rules! dynamic_value {
($name: ident: $t: ty) => {
static mut VAL: Option<$t> = None;
#[derive(Copy, Clone, Eq, PartialEq, Hash, Default)]
struct $name {}
impl $crate::algo_lib::misc::value::DynamicValue<$t> for $name {
fn set_val(t: $t) {
unsafe {
VAL = Some(t);
}
}
}
impl $crate::algo_lib::misc::value::Value<$t> for $name {
fn val() -> $t {
unsafe { VAL.unwrap() }
}
}
};
($name: ident: $t: ty = $val: expr) => {
dynamic_value!($name: $t);
$name::set_val($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;
use crate::algo_lib::numbers::num_traits::algebra::IntegerSemiRingWithSub;
use crate::algo_lib::numbers::num_traits::algebra::One;
use crate::algo_lib::numbers::num_traits::algebra::SemiRingWithSub;
use crate::algo_lib::numbers::num_traits::algebra::Zero;
use crate::algo_lib::numbers::num_traits::wideable::Wideable;
use std::mem::swap;
pub fn extended_gcd<T: IntegerSemiRingWithSub + Wideable + Copy>(
a: T,
b: T,
) -> (T, T::W, T::W)
where
T::W: Copy + SemiRingWithSub,
{
if a == T::zero() {
(b, T::W::zero(), T::W::one())
} else {
let (d, y, mut x) = extended_gcd(b % a, a);
x -= T::W::from(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 mod matrix {
use crate::algo_lib::collections::md_arr::arr2d::Arr2d;
use crate::algo_lib::numbers::num_traits::algebra::One;
use crate::algo_lib::numbers::num_traits::algebra::SemiRing;
use crate::algo_lib::numbers::num_traits::algebra::Zero;
use std::ops::Deref;
use std::ops::DerefMut;
#[derive(Clone)]
pub struct Matrix<T>(Arr2d<T>);
impl<T: Zero + One + Clone> Matrix<T> {
pub fn zero(n: usize, m: usize) -> Self {
Self(Arr2d::new(n, m, T::zero()))
}
pub fn ident(n: usize) -> Self {
Self(Arr2d::generate(n, n, |i, j| {
if i == j {
T::one()
} else {
T::zero()
}
}))
}
}
impl<T: Copy> Matrix<T> {
pub fn column(arr: &[T]) -> Self {
Self(Arr2d::generate(arr.len(), 1, |i, _| arr[i]))
}
pub fn row(arr: &[T]) -> Self {
Self(Arr2d::generate(1, arr.len(), |_, i| arr[i]))
}
pub fn new(arr: &[&[T]]) -> Self {
for a in arr {
assert_eq!(a.len(), arr[0].len());
}
Self(Arr2d::generate(arr.len(), arr[0].len(), |i, j| arr[i][j]))
}
}
impl<T: SemiRing + Copy> Matrix<T> {
pub fn mult(&self, a: &Matrix<T>) -> Self {
let mut res = Self::zero(self.d1(), a.d2());
Self::do_mult(&mut res, self, a);
res
}
pub fn do_mult(&mut self, a: &Matrix<T>, b: &Matrix<T>) {
assert_eq!(self.d1(), a.d1());
assert_eq!(a.d2(), b.d1());
assert_eq!(b.d2(), self.d2());
self.fill(T::zero());
for i in 0..self.d1() {
for j in 0..a.d2() {
for k in 0..b.d2() {
self[(i, k)] += a[(i, j)] * b[(j, k)];
}
}
}
}
pub fn add(&mut self, a: &Matrix<T>, b: &Matrix<T>) {
assert_eq!(self.d1(), a.d1());
assert_eq!(self.d2(), a.d2());
assert_eq!(self.d1(), b.d1());
assert_eq!(self.d2(), b.d2());
for i in 0..self.d1() {
for j in 0..self.d2() {
self[(i, j)] = a[(i, j)] + b[(i, j)];
}
}
}
pub fn add_to(&mut self, a: &Matrix<T>) {
assert_eq!(self.d1(), a.d1());
assert_eq!(self.d2(), a.d2());
for i in 0..self.d1() {
for j in 0..self.d2() {
self[(i, j)] += a[(i, j)];
}
}
}
pub fn power(&self, n: usize) -> Matrix<T> {
assert_eq!(self.d1(), self.d2());
let mut res = Self::ident(self.d1());
let mut temp = Self::ident(self.d1());
Self::do_power(self, &mut res, &mut temp, n);
res
}
fn do_power(a: &Matrix<T>, res: &mut Matrix<T>, temp: &mut Matrix<T>, n: usize) {
if n != 0 {
if (n & 1) == 0 {
Self::do_power(a, temp, res, n >> 1);
res.do_mult(temp, temp);
} else {
Self::do_power(a, temp, res, n - 1);
res.do_mult(temp, a);
}
}
}
}
impl<T> Deref for Matrix<T> {
type Target = Arr2d<T>;
fn deref(&self) -> &Self::Target {
&self.0
}
}
impl<T> DerefMut for Matrix<T> {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.0
}
}
impl<T> From<Arr2d<T>> for Matrix<T> {
fn from(a: Arr2d<T>) -> Self {
Self(a)
}
}
}
pub mod mod_int {
use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::input::Readable;
use crate::algo_lib::io::output::Output;
use crate::algo_lib::io::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;
use crate::algo_lib::numbers::num_traits::algebra::IntegerRing;
use crate::algo_lib::numbers::num_traits::algebra::One;
use crate::algo_lib::numbers::num_traits::algebra::Ring;
use crate::algo_lib::numbers::num_traits::algebra::Zero;
use crate::algo_lib::numbers::num_traits::as_index::AsIndex;
use crate::algo_lib::numbers::num_traits::invertible::Invertible;
use crate::algo_lib::numbers::num_traits::wideable::Wideable;
use crate::value;
use crate::when;
use std::collections::HashMap;
use std::fmt::Display;
use std::fmt::Formatter;
use std::hash::Hash;
use std::marker::PhantomData;
use std::ops::Add;
use std::ops::AddAssign;
use std::ops::Div;
use std::ops::DivAssign;
use std::ops::Mul;
use std::ops::MulAssign;
use std::ops::Neg;
use std::ops::Sub;
use std::ops::SubAssign;
pub trait BaseModInt: Field + Copy {
type W: IntegerRing + Copy + From<Self::T>;
type T: IntegerRing + Ord + Copy + Wideable<W = Self::W>;
fn from(v: Self::T) -> Self;
fn module() -> Self::T;
}
#[derive(Copy, Clone, Eq, PartialEq, Hash, Default)]
pub struct ModInt<T, V: Value<T>> {
n: T,
phantom: PhantomData<V>,
}
impl<T: Copy, V: Value<T>> ModInt<T, V> {
pub fn val(&self) -> T {
self.n
}
}
impl<T: Ring + Ord + Copy, V: Value<T>> ModInt<T, V> {
unsafe fn unchecked_new(n: T) -> Self {
debug_assert!(n >= T::zero() && n < V::val());
Self {
n,
phantom: Default::default(),
}
}
unsafe fn maybe_subtract_mod(mut n: T) -> T {
debug_assert!(n < V::val() + V::val() && n >= T::zero());
if n >= V::val() {
n -= V::val();
}
n
}
}
impl<T: IntegerRing + Ord + Copy, V: Value<T>> ModInt<T, V> {
pub fn new(n: T) -> Self {
unsafe {
Self::unchecked_new(Self::maybe_subtract_mod(n % (V::val()) + V::val()))
}
}
}
impl<T: Copy + IntegerRing + Ord + Wideable + Hash, V: Value<T>> ModInt<T, V>
where
T::W: Copy + IntegerRing,
{
pub fn log(&self, alpha: Self) -> T {
let mut base = HashMap::new();
let mut exp = T::zero();
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 += T::one();
pow *= alpha;
inv *= alpha_inv;
}
let step = pow;
let mut i = T::one();
loop {
if let Some(b) = base.get(&pow) {
break exp * i + *b;
}
pow *= step;
i += T::one();
}
}
}
impl<T: Wideable + Ring + Ord + Copy, V: Value<T>> ModInt<T, V>
where
T::W: IntegerRing,
{
pub fn new_from_wide(n: T::W) -> Self {
unsafe {
Self::unchecked_new(Self::maybe_subtract_mod(
T::downcast(n % (V::val()).into()) + V::val(),
))
}
}
}
impl<T: Copy + IntegerRing + Ord + Wideable, V: Value<T>> Invertible for ModInt<T, V>
where
T::W: Copy + IntegerRing,
{
type Output = Self;
fn inv(&self) -> Option<Self> {
let (g, x, _) = extended_gcd(self.n, V::val());
if g != T::one() {
None
} else {
Some(Self::new_from_wide(x))
}
}
}
impl<T: IntegerRing + Ord + Copy + Wideable, V: Value<T>> BaseModInt for ModInt<T, V>
where
T::W: IntegerRing + Copy,
{
type W = T::W;
type T = T;
fn from(v: Self::T) -> Self {
Self::new(v)
}
fn module() -> T {
V::val()
}
}
impl<T: IntegerRing + Ord + Copy, V: Value<T>> From<T> for ModInt<T, V> {
fn from(n: T) -> Self {
Self::new(n)
}
}
impl<T: Ring + Ord + Copy, V: Value<T>> AddAssign for ModInt<T, V> {
fn add_assign(&mut self, rhs: Self) {
self.n = unsafe { Self::maybe_subtract_mod(self.n + rhs.n) };
}
}
impl<T: Ring + Ord + Copy, V: Value<T>> Add for ModInt<T, V> {
type Output = Self;
fn add(mut self, rhs: Self) -> Self::Output {
self += rhs;
self
}
}
impl<T: Ring + Ord + Copy, V: Value<T>> SubAssign for ModInt<T, V> {
fn sub_assign(&mut self, rhs: Self) {
self.n = unsafe { Self::maybe_subtract_mod(self.n + V::val() - rhs.n) };
}
}
impl<T: Ring + Ord + Copy, V: Value<T>> Sub for ModInt<T, V> {
type Output = Self;
fn sub(mut self, rhs: Self) -> Self::Output {
self -= rhs;
self
}
}
impl<T: IntegerRing + Ord + Copy + Wideable, V: Value<T>> MulAssign for ModInt<T, V>
where
T::W: IntegerRing + Copy,
{
fn mul_assign(&mut self, rhs: Self) {
self.n =
T::downcast(T::W::from(self.n) * T::W::from(rhs.n) % T::W::from(V::val()));
}
}
impl<T: IntegerRing + Ord + Copy + Wideable, V: Value<T>> Mul for ModInt<T, V>
where
T::W: IntegerRing + Copy,
{
type Output = Self;
fn mul(mut self, rhs: Self) -> Self::Output {
self *= rhs;
self
}
}
impl<T: IntegerRing + Ord + Copy + Wideable, V: Value<T>> DivAssign for ModInt<T, V>
where
T::W: IntegerRing + Copy,
{
#[allow(clippy::suspicious_op_assign_impl)]
fn div_assign(&mut self, rhs: Self) {
*self *= rhs.inv().unwrap();
}
}
impl<T: IntegerRing + Ord + Copy + Wideable, V: Value<T>> Div for ModInt<T, V>
where
T::W: IntegerRing + Copy,
{
type Output = Self;
fn div(mut self, rhs: Self) -> Self::Output {
self /= rhs;
self
}
}
impl<T: Ring + Ord + Copy, V: Value<T>> Neg for ModInt<T, V> {
type Output = Self;
fn neg(mut self) -> Self::Output {
self.n = unsafe { Self::maybe_subtract_mod(V::val() - self.n) };
self
}
}
impl<T: Display, V: Value<T>> Display for ModInt<T, V> {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
<T as Display>::fmt(&self.n, f)
}
}
impl<T: IntegerRing + Ord + Copy + Readable, V: Value<T>> Readable for ModInt<T, V> {
fn read(input: &mut Input) -> Self {
Self::new(T::read(input))
}
}
impl<T: Writable, V: Value<T>> Writable for ModInt<T, V> {
fn write(&self, output: &mut Output) {
self.n.write(output);
}
}
impl<T: Ring + Ord + Copy, V: Value<T>> Zero for ModInt<T, V> {
fn zero() -> Self {
unsafe { Self::unchecked_new(T::zero()) }
}
}
impl<T: IntegerRing + Ord + Copy, V: Value<T>> One for ModInt<T, V> {
fn one() -> Self {
Self::new(T::one())
}
}
impl<T, V: Value<T>> Wideable for ModInt<T, V> {
type W = Self;
fn downcast(w: Self::W) -> Self {
w
}
}
impl<T: IntegerRing + Ord + Copy + Wideable + Display + AsIndex, V: Value<T>>
std::fmt::Debug for ModInt<T, V>
where
T::W: IntegerRing + Copy,
{
fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
let max = T::from_index(100);
when! {
self.n <= max => write!(f, "{}", self.n),
self.n >= V::val() - max => write!(f, "{}", self.n - V::val()),
else => {
let mut denominator = T::one();
while denominator < max {
let mut num = T::one();
while num < 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);
}
num += T::one();
}
denominator += T::one();
}
write!(f, "(?? {} ??)", self.n)
},
}
}
}
impl<T: IntegerRing + Ord + Copy + AsIndex, V: Value<T>> AsIndex for ModInt<T, V> {
fn from_index(idx: usize) -> Self {
Self::new(T::from_index(idx))
}
fn to_index(self) -> usize {
self.n.to_index()
}
}
value!(Val7: i32 = 1_000_000_007);
pub type ModInt7 = ModInt<i32, Val7>;
value!(Val9: i32 = 1_000_000_009);
pub type ModInt9 = ModInt<i32, Val9>;
value!(ValF: i32 = 998_244_353);
pub type ModIntF = ModInt<i32, ValF>;
}
pub mod num_traits {
pub mod algebra {
use crate::algo_lib::numbers::num_traits::invertible::Invertible;
use std::ops::Add;
use std::ops::AddAssign;
use std::ops::Div;
use std::ops::DivAssign;
use std::ops::Mul;
use std::ops::MulAssign;
use std::ops::Neg;
use std::ops::Rem;
use std::ops::RemAssign;
use std::ops::Sub;
use std::ops::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 bit_ops {
use crate::algo_lib::numbers::num_traits::algebra::One;
use crate::algo_lib::numbers::num_traits::algebra::Zero;
use std::ops::BitAnd;
use std::ops::BitAndAssign;
use std::ops::BitOr;
use std::ops::BitOrAssign;
use std::ops::BitXor;
use std::ops::BitXorAssign;
use std::ops::Not;
use std::ops::RangeInclusive;
use std::ops::Shl;
use std::ops::ShlAssign;
use std::ops::Shr;
use std::ops::ShrAssign;
pub trait BitOps:
Copy
+ BitAnd<Output = Self>
+ BitAndAssign
+ BitOr<Output = Self>
+ BitOrAssign
+ BitXor<Output = Self>
+ BitXorAssign
+ Not<Output = Self>
+ Shl<usize, Output = Self>
+ ShlAssign<usize>
+ Shr<usize, Output = Self>
+ ShrAssign<usize>
+ Zero
+ One
+ PartialEq
{
fn bit(at: usize) -> Self {
Self::one() << at
}
fn is_set(&self, at: usize) -> bool {
(*self >> at & Self::one()) == Self::one()
}
fn set_bit(&mut self, at: usize) {
*self |= Self::bit(at)
}
fn unset_bit(&mut self, at: usize) {
*self &= !Self::bit(at)
}
#[must_use]
fn with_bit(mut self, at: usize) -> Self {
self.set_bit(at);
self
}
#[must_use]
fn without_bit(mut self, at: usize) -> Self {
self.unset_bit(at);
self
}
fn flip_bit(&mut self, at: usize) {
*self ^= Self::bit(at)
}
fn all_bits(n: usize) -> Self {
let mut res = Self::zero();
for i in 0..n {
res.set_bit(i);
}
res
}
fn iter_all(n: usize) -> RangeInclusive<Self> {
Self::zero()..=Self::all_bits(n)
}
}
impl<
T: Copy
+ BitAnd<Output = Self>
+ BitAndAssign
+ BitOr<Output = Self>
+ BitOrAssign
+ BitXor<Output = Self>
+ BitXorAssign
+ Not<Output = Self>
+ Shl<usize, Output = Self>
+ ShlAssign<usize>
+ Shr<usize, Output = Self>
+ ShrAssign<usize>
+ One
+ Zero
+ PartialEq,
> BitOps for T
{
}
pub trait Bits: BitOps {
fn bits() -> u32;
}
macro_rules! bits_integer_impl {
($($t: ident $bits: expr),+) => {$(
impl Bits for $t {
fn bits() -> u32 {
$bits
}
}
)+};
}
bits_integer_impl!(i128 128, i64 64, i32 32, i16 16, i8 8, isize 64, u128 128, u64 64, u32 32, u16 16, u8 8, usize 64);
}
pub mod invertible {
pub trait Invertible {
type Output;
fn inv(&self) -> Option<Self::Output>;
}
}
pub mod wideable {
use std::convert::From;
pub trait Wideable: Sized {
type W: From<Self>;
fn downcast(w: Self::W) -> Self;
}
macro_rules! wideable_impl {
($($t: ident $w: ident),+) => {$(
impl Wideable for $t {
type W = $w;
fn downcast(w: Self::W) -> Self {
w as $t
}
}
)+};
}
wideable_impl!(i64 i128, i32 i64, i16 i32, i8 i16, u64 u128, u32 u64, u16 u32, u8 u16);
}
}
}
}
fn main() {
let mut sin = std::io::stdin();
let input = if false {
algo_lib::io::input::Input::new_with_size(&mut sin, 1)
} else {
algo_lib::io::input::Input::new(&mut sin)
};
let mut stdout = std::io::stdout();
let output = if false {
algo_lib::io::output::Output::new_with_auto_flush(&mut stdout)
} else {
algo_lib::io::output::Output::new(&mut stdout)
};
solution::run(input, output);
}
这程序好像有点Bug，我给组数据试试？
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 2064kb
input:
5 3 x 2 3 v 1 0 1 x 4 5 v 0 2 1 v 1 1 1 4 1 2 3 5 0 1 1 4 0 2 2
output:
998244351 0 2 1 998244351 998244352 0 0 0
result:
ok 9 numbers
Test #2:
score: 0
Accepted
time: 1498ms
memory: 44148kb
input:
199999 100000 x 137025 65661 v 572518668 158967010 74946561 x 129836 192657 x 141948 187810 v 574918069 328924434 141474729 x 143312 111002 x 52772 148497 v 922857701 690080961 651915759 v 656198340 28002884 129579416 v 639893144 265359784 646791226 v 796871409 411409966 598676495 v 882562617 224394...
output:
393120558 773766615 387297348 759959566 981774500 128012497 294611811 980011608 533642029 404379574 745296852 53493560 404565501 828869760 78021156 592494858 647751304 881427733 190018467 515243135 518180555 628180500 509984554 257430135 13737245 352087791 917410487 932051309 366591227 479931477 199...
result:
ok 300000 numbers
Test #3:
score: 0
Accepted
time: 1536ms
memory: 44280kb
input:
199999 100000 x 154525 80092 v 450407262 725458410 590777520 x 24720 135901 v 719242117 114943104 186796011 v 382530926 89156744 943939337 x 183376 26042 x 109984 157873 x 151637 150600 x 4115 27454 x 163135 92648 x 16764 33212 v 849210403 945083972 689295397 v 471196117 68587428 225597765 x 24643 5...
output:
677067461 996514296 449166851 810403092 258196842 853459733 410756156 253348518 912664471 327134890 519245783 922528759 317367558 536888537 506214109 484753530 879045782 772404948 422920052 152084658 517340457 1207902 348787162 320821077 776293878 699474926 711114530 871858473 468497588 822120121 24...
result:
ok 300000 numbers
Test #4:
score: 0
Accepted
time: 1552ms
memory: 44196kb
input:
199999 100000 x 72889 193806 x 35339 33069 v 314802407 406980523 492377265 x 108307 60027 x 144922 140917 v 328481079 117663280 644171354 v 482028404 951751561 166221217 v 936461869 436114879 421819757 x 152919 99965 x 61168 150607 v 56403640 743462679 134896557 v 24809217 462947115 966139991 v 7828...
output:
23709876 380448367 629159667 760678420 539369190 611778104 114926687 653692915 939877414 674199470 304745735 544123803 953800112 186017361 49200537 327282782 871001677 293980713 588783157 502130649 190564297 102680906 993889016 963478755 510012481 105416897 281770975 811082806 367139818 493674194 32...
result:
ok 300000 numbers
Test #5:
score: 0
Accepted
time: 1853ms
memory: 44432kb
input:
199999 100000 x 134204 79203 v 152855933 152545887 271660214 v 393332175 182708769 115884220 v 731792305 965028257 676889584 x 89631 14495 x 142016 85686 v 600051847 172947969 906920949 v 846126215 214556203 657929902 x 125721 133526 x 93179 35713 v 330716449 450417250 611411649 v 114397688 58644961...
output:
139597616 375474977 14619793 889328460 79727434 363703631 397351102 877961602 429046190 588368345 819425899 502148739 520578911 186408072 484373545 997888597 816534316 338411279 334166269 288211584 608252640 509280845 362972392 286415695 363396960 878881251 3658455 711270872 94816531 100279034 48844...
result:
ok 300000 numbers
Test #6:
score: 0
Accepted
time: 2420ms
memory: 44260kb
input:
199999 100000 x 29842 60343 x 22382 27649 v 148997533 411153785 529195552 v 831453378 856711025 439562917 x 183061 152107 v 208562249 845550020 248974502 x 8708 152913 v 901332053 480035531 424365358 v 120556946 620074725 884675784 v 493886564 455460926 851190410 x 63346 64739 x 35246 36255 v 762936...
output:
236797322 190218414 70559261 661765898 266356472 481630021 410967670 613729303 804008156 92638320 37926778 82924205 357869883 232766711 579608532 691702082 124868602 187367212 237610689 608489848 581104410 848616732 907873139 859807891 614624615 454674844 673629667 485784731 743926138 168595096 1826...
result:
ok 300000 numbers
Test #7:
score: 0
Accepted
time: 2412ms
memory: 44340kb
input:
199999 100000 x 179471 175117 x 189060 178495 x 20142 58065 x 22916 150184 v 704047412 186112247 660817663 v 761554808 199099716 794321264 v 362925435 508140595 251556541 v 65674025 717152823 157775106 v 325965317 977108704 50644678 v 566946741 833186394 771714200 v 996708965 76780827 625429369 v 85...
output:
365258325 105829774 612397830 731509055 576900445 663777200 553518677 415454275 7683807 468131249 577225931 513594285 215590236 861146274 812820392 669985796 229486834 564691763 929231866 520228049 774609748 29950289 569366391 721072115 644573107 513714638 554458153 728007201 423847330 100860143 192...
result:
ok 300000 numbers
Test #8:
score: 0
Accepted
time: 2302ms
memory: 44160kb
input:
199999 100000 x 73506 171332 x 135330 187765 v 308206068 679940956 278078069 v 442448744 196158033 738117032 x 194709 115786 v 208526122 936976225 340056181 x 42663 43401 x 55484 199464 v 865443128 131903961 74265613 x 44659 44773 x 32199 18455 v 986118756 284329619 244212114 v 793747964 649179736 4...
output:
429717039 868308596 175018519 966246118 532451840 773132006 457086098 631788280 989689243 550574851 6706768 416615899 285141084 505326489 916518702 457465389 653530244 951605771 614211832 767828057 44273794 698196640 494937773 99337798 718503234 422078037 151379051 20520347 707143833 781787052 24220...
result:
ok 300000 numbers
Test #9:
score: 0
Accepted
time: 2389ms
memory: 44228kb
input:
199999 100000 x 109220 170287 v 563361501 367416904 98790213 x 31431 96958 x 99594 159052 x 95382 129615 v 61965807 547448247 405891792 v 443530416 578856323 588763197 v 761021716 795533831 212530056 v 370964907 391812631 255457982 x 49713 153066 x 141543 111694 v 144135957 614962153 284136518 x 416...
output:
433293962 336914247 747368803 992117520 9180464 159616244 483825959 496735833 964507719 912495370 737285784 595438897 467123496 44306423 562070292 903488238 42971643 61415659 269853145 336741491 565138878 926999098 134871683 277614816 644727031 476324825 69621281 984868613 112590560 688626178 657736...
result:
ok 300000 numbers
Test #10:
score: 0
Accepted
time: 0ms
memory: 2032kb
input:
3 1 x 2 3 v 998244352 998244352 998244352 v 0 0 0 3 1 2 0
output:
2 998244352 998244352
result:
ok 3 number(s): "2 998244352 998244352"
Test #11:
score: 0
Accepted
time: 2128ms
memory: 44028kb
input:
199999 100000 x 199465 1690 x 70268 106693 v 194793703 729830314 457557419 x 64673 6910 v 755452906 141328541 558160677 v 725017524 158685295 201414156 x 161801 27226 x 181414 47025 v 387724146 819109666 514628998 v 252532326 97757436 828777580 v 200868967 692540096 706977766 v 300419109 2053530 824...
output:
627210517 640945891 400484640 305641486 893058825 99893167 735729088 805595533 283037791 377070714 357962902 336785549 835938680 634694731 22388934 493696932 612552793 516945234 963890355 517530875 48223226 215318080 742583745 379791022 135074745 970450812 921824280 86572382 481696244 728925909 6372...
result:
ok 300000 numbers
Test #12:
score: 0
Accepted
time: 3199ms
memory: 44084kb
input:
199999 100000 x 37758 141919 v 148792593 369372129 595139892 x 59335 149367 v 452667329 904801829 628919068 v 160106559 532238331 179544300 v 850489754 705167899 265598880 x 120963 167491 x 92157 46815 v 444945978 987276260 843838004 x 189040 28027 v 889755401 760730228 3237333 x 168907 82672 v 2329...
output:
897185498 177437016 653646802 48860209 883514812 764698776 505088312 585962448 546090395 914246027 540944167 682989725 965835151 803706423 302298107 452996535 714783487 961852197 882717809 425959754 886391042 203667304 454663502 78105722 512196135 727218227 418204527 274934801 270977361 824228740 74...
result:
ok 300000 numbers
Extra Test:
score: 0
Extra Test Passed