use proconio::input; use proconio::marker::Usize1; use splay_tree::SplayTree; type Fp = fp::Fp<1_000_000_007>; fn main() { input! { n: usize, sum: [usize; n], coeff: [usize; n], edges: [(Usize1, Usize1); n - 1], q: usize, } let (hld, _g) = Hld::from_edges(0, &edges); let mut values = vec![ Value { coeff: fp!(0), sum: fp!(0) }; n ]; for (x, &i) in hld.index.iter().enumerate() { values[i] = Value { coeff: fp!(coeff[x]), sum: fp!(sum[x]), }; } let mut lazy_segtree = SplayTree::::from_iter(values); for _ in 0..q { input! { com: String, } match com.as_str() { "0" => { input! { i: Usize1, j: Usize1, op: usize, } hld.visit_path_segments_including_lca_by_index(i, j, |i, j| { lazy_segtree.act(i..=j, fp!(op)); }); } "1" => { input! { i: Usize1, j: Usize1, } let mut ans = fp!(0); hld.visit_path_segments_including_lca_by_index(i, j, |i, j| { ans += lazy_segtree.fold(i..=j).unwrap().sum; }); println!("{ans}"); } _ => unreachable!(), } } } #[derive(Clone, Copy, Debug, PartialEq)] struct Value { coeff: Fp, sum: Fp, } enum O {} impl splay_tree::LazyOps for O { type Acc = Value; type Lazy = Fp; type Value = Value; fn proj(value: &Self::Value) -> Self::Acc { *value } fn op(lhs: &Self::Acc, rhs: &Self::Acc) -> Self::Acc { Value { coeff: lhs.coeff + rhs.coeff, sum: lhs.sum + rhs.sum, } } fn act_value(lazy: &Self::Lazy, value: &mut Self::Value) { value.sum += lazy * value.coeff; } fn act_acc(lazy: &Self::Lazy, acc: &mut Self::Acc) { acc.sum += lazy * acc.coeff; } fn compose(upper: &Self::Lazy, lower: &mut Self::Lazy) { *lower += upper; } } pub struct Hld { pub parent: Vec, pub index: Vec, pub head: Vec, } impl Hld { pub fn from_short_parents(mut parent: Vec) -> (Self, Vec>) { parent.insert(0, 0); let mut g = vec![Vec::new(); parent.len()]; for (i, &p) in parent.iter().enumerate().skip(1) { g[p].push(i); } (__build_hld(0, &mut g, parent), g) } pub fn from_edges(root: usize, edges: &[(usize, usize)]) -> (Self, Vec>) { let mut g = vec![Vec::new(); edges.len() + 1]; for &(i, j) in edges { g[i].push(j); g[j].push(i); } let parent = __remove_parent(root, &mut g); (__build_hld(root, &mut g, parent), g) } pub fn visit_path_segments_including_lca( &self, mut i: usize, // id mut j: usize, // id mut f: impl FnMut(usize, usize), // id ) { while self.head[i] != self.head[j] { if self.index[i] < self.index[j] { f(self.head[j], j); j = self.parent[self.head[j]]; } else { f(self.head[i], i); i = self.parent[self.head[i]]; } } if self.index[i] < self.index[j] { f(i, j) } else { f(j, i) } } pub fn visit_path_segments_including_lca_by_index( &self, i: usize, // id j: usize, // id mut f: impl FnMut(usize, usize), // index ) { self.visit_path_segments_including_lca(i, j, |i, j| f(self.index[i], self.index[j])); } pub fn lca(&self, mut i: usize, mut j: usize) -> usize { while self.head[i] != self.head[j] { if self.index[i] < self.index[j] { j = self.parent[self.head[j]]; } else { i = self.parent[self.head[i]]; } } std::cmp::min_by_key(i, j, |&i| self.index[i]) } } fn __build_hld(root: usize, g: &mut [Vec], parent: Vec) -> Hld { let n = g.len(); __heavy_first(0, g); let mut index = vec![usize::MAX; n]; let mut head = vec![usize::MAX; n]; head[root] = root; __head_and_index(0, &*g, &mut head, &mut index, &mut (0..)); Hld { parent, index, head, } } fn __head_and_index( i: usize, g: &[Vec], head: &mut [usize], index: &mut [usize], current: &mut std::ops::RangeFrom, ) { index[i] = current.next().unwrap(); for &j in &g[i] { head[j] = if j == g[i][0] { head[i] } else { j }; __head_and_index(j, g, head, index, current); } } fn __heavy_first(i: usize, g: &mut [Vec]) -> usize { let mut max = 0; let mut size = 1; for e in 0..g[i].len() { let csize = __heavy_first(g[i][e], g); if max < csize { max = csize; g[i].swap(0, e); } size += csize; } size } fn __remove_parent(root: usize, g: &mut [Vec]) -> Vec { let mut stack = vec![root]; let mut parent = vec![usize::MAX; g.len()]; parent[root] = root; while let Some(i) = stack.pop() { g[i].retain(|&j| parent[i] != j); for &j in &g[i] { parent[j] = i; stack.push(j); } } parent } // link_cut_tree {{{ // https://ngtkana.github.io/ac-adapter-rs/link_cut_tree/index.html #[allow(dead_code)] mod link_cut_tree { mod base { #[doc(hidden)] pub trait OpBase { type Value: Clone; type InternalValue: Clone; fn identity() -> Self::InternalValue; fn mul(lhs: &Self::InternalValue, rhs: &Self::InternalValue) -> Self::InternalValue; fn into_front(value: Self::InternalValue) -> Self::Value; fn from_front(value: Self::Value) -> Self::InternalValue; fn rev(value: &mut Self::InternalValue); } pub struct LinkCutTreeBase { nodes: Vec>, } impl LinkCutTreeBase { pub fn new(n: usize) -> Self { Self { nodes: (0..n) .map(|id| Node { id, parent: std::ptr::null_mut(), left: std::ptr::null_mut(), right: std::ptr::null_mut(), rev: false, value: O::identity(), acc: O::identity(), }) .collect(), } } pub fn from_values(values: impl IntoIterator) -> Self { Self { nodes: values .into_iter() .map(O::from_front) .enumerate() .map(|(id, value)| Node { id, parent: std::ptr::null_mut(), left: std::ptr::null_mut(), right: std::ptr::null_mut(), rev: false, value: value.clone(), acc: value, }) .collect(), } } pub fn link(&mut self, p: usize, c: usize) { unsafe { let c = std::ptr::addr_of_mut!(self.nodes[c]); let p = std::ptr::addr_of_mut!(self.nodes[p]); expose(c); assert!((*c).left.is_null(), "c = {} is not a root", (*c).id); expose(p); assert!( (*c).parent.is_null(), "c = {} and p = {} are already connected", (*c).id, (*p).id ); (*c).parent = p; (*p).right = c; update(p); } } pub fn undirected_link(&mut self, i: usize, j: usize) -> bool { if self.undirected_is_connected(i, j) { return false; } self.evert(j); self.link(i, j); true } pub fn cut(&mut self, x: usize) -> Option { unsafe { let x = std::ptr::addr_of_mut!(self.nodes[x]); expose(x); let p = (*x).left; (*x).left = std::ptr::null_mut(); let ans = p.as_ref().map(|p| p.id); if !p.is_null() { (*p).parent = std::ptr::null_mut(); } update(x); ans } } pub fn undirected_cut(&mut self, i: usize, j: usize) -> bool { if !self.undirected_has_edge(i, j) { return false; } self.evert(i); self.cut(j); true } pub fn evert(&mut self, x: usize) { unsafe { let x = std::ptr::addr_of_mut!(self.nodes[x]); expose(x); rev(x); push(x); } } pub fn undirected_has_edge(&mut self, x: usize, y: usize) -> bool { self.parent(x) == Some(y) || self.parent(y) == Some(x) } pub fn undirected_is_connected(&mut self, x: usize, y: usize) -> bool { if x == y { return true; } unsafe { let x = std::ptr::addr_of_mut!(self.nodes[x]); let y = std::ptr::addr_of_mut!(self.nodes[y]); expose(x); expose(y); !(*x).parent.is_null() } } pub fn lca(&mut self, x: usize, y: usize) -> Option { if x == y { return Some(x); } unsafe { let x = std::ptr::addr_of_mut!(self.nodes[x]); let y = std::ptr::addr_of_mut!(self.nodes[y]); expose(x); let lca = expose(y); if (*x).parent.is_null() { None } else { Some((*lca).id) } } } pub fn set(&mut self, x: usize, mut f: impl FnMut(O::Value) -> O::Value) { unsafe { let x = std::ptr::addr_of_mut!(self.nodes[x]); expose(x); (*x).value = O::from_front(f(O::into_front((*x).value.clone()))); update(x); } } pub fn fold(&mut self, x: usize) -> O::Value { unsafe { let x = std::ptr::addr_of_mut!(self.nodes[x]); expose(x); O::into_front((*x).acc.clone()) } } pub fn undirected_fold(&mut self, i: usize, j: usize) -> Option { if !self.undirected_is_connected(i, j) { return None; } self.evert(i); Some(self.fold(j)) } pub fn parent(&mut self, x: usize) -> Option { unsafe { let x = std::ptr::addr_of_mut!(self.nodes[x]); expose(x); let mut p = (*x).left.as_mut()?; while let Some(next) = p.right.as_mut() { p = next; } splay(p); Some(p.id) } } } #[derive(Clone, Copy)] struct Node { id: usize, parent: *mut Self, left: *mut Self, right: *mut Self, rev: bool, value: O::InternalValue, acc: O::InternalValue, } unsafe fn is_splay_root(x: *mut Node) -> bool { let x = &*x; let p = match x.parent.as_ref() { Some(p) => p, None => return true, }; !std::ptr::eq(x, p.left) && !std::ptr::eq(x, p.right) } unsafe fn push(x: *mut Node) { let x = &mut *x; if x.rev { if let Some(l) = x.left.as_mut() { rev(l); } if let Some(r) = x.right.as_mut() { rev(r); } x.rev = false; } } unsafe fn update(x: *mut Node) { let x = &mut *x; x.acc = x.value.clone(); if !x.left.is_null() { x.acc = O::mul(&(*x.left).acc, &x.acc); } if !x.right.is_null() { x.acc = O::mul(&x.acc, &(*x.right).acc); } } unsafe fn rev(x: *mut Node) { let x = &mut *x; std::mem::swap(&mut x.left, &mut x.right); O::rev(&mut x.acc); x.rev ^= true; } unsafe fn expose(x: *mut Node) -> *mut Node { let mut last = std::ptr::null_mut(); let mut current = x; while !current.is_null() { splay(current); (*current).right = last; update(current); last = current; current = (*current).parent; } splay(x); last } unsafe fn splay(x: *mut Node) { let x = &mut *x; push(x); while !is_splay_root(x) { let p = &mut *x.parent; if is_splay_root(p) { push(p); push(x); if std::ptr::eq(p.left, x) { rotate_right(p); } else { rotate_left(p); } } else { let g = &mut *p.parent; push(g); push(p); push(x); #[allow(clippy::collapsible_else_if)] if std::ptr::eq(p.left, x) { if std::ptr::eq(g.left, p) { rotate_right(g); rotate_right(p); } else { rotate_right(p); rotate_left(g); } } else { if std::ptr::eq(g.left, p) { rotate_left(p); rotate_right(g); } else { rotate_left(g); rotate_left(p); } } } } } unsafe fn rotate_left(l: *mut Node) { let l = &mut *l; let r = &mut *l.right; let p = l.parent; let c = r.left; l.right = c; if !c.is_null() { (*c).parent = l; } r.left = l; l.parent = r; r.parent = p; update(l); update(r); if !p.is_null() { if std::ptr::eq((*p).left, l) { (*p).left = r; } else if std::ptr::eq((*p).right, l) { (*p).right = r; } update(&mut *p); } } unsafe fn rotate_right(r: *mut Node) { let r = &mut *r; let l = &mut *r.left; let p = r.parent; let c = l.right; r.left = c; if !c.is_null() { (*c).parent = r; } l.right = r; r.parent = l; l.parent = p; update(r); update(l); if !p.is_null() { if std::ptr::eq((*p).left, r) { (*p).left = l; } else if std::ptr::eq((*p).right, r) { (*p).right = l; } update(&mut *p); } } } pub use base::LinkCutTreeBase; use base::OpBase; pub trait Op { type Value: Clone; fn identity() -> Self::Value; fn mul(lhs: &Self::Value, rhs: &Self::Value) -> Self::Value; } impl OpBase for () { type InternalValue = (); type Value = (); fn identity() -> Self::InternalValue {} fn mul(_lhs: &Self::InternalValue, _rhs: &Self::InternalValue) -> Self::InternalValue {} fn rev(_value: &mut Self::InternalValue) {} fn into_front(_value: Self::InternalValue) {} fn from_front(_value: Self::Value) -> Self::InternalValue {} } pub type LinkCutTree = LinkCutTreeBase<()>; pub type CommutLinkCutTree = LinkCutTreeBase>; #[doc(hidden)] pub struct Commut(T); impl OpBase for Commut { type InternalValue = T::Value; type Value = T::Value; fn identity() -> Self::InternalValue { T::identity() } fn mul(lhs: &Self::InternalValue, rhs: &Self::InternalValue) -> Self::InternalValue { T::mul(lhs, rhs) } fn rev(_value: &mut Self::InternalValue) {} fn into_front(value: Self::InternalValue) -> Self::Value { value } fn from_front(value: Self::Value) -> Self::InternalValue { value } } #[doc(hidden)] pub struct NonCommut(T); pub type NonCommutLinkCutTree = LinkCutTreeBase>; impl OpBase for NonCommut { type InternalValue = (T::Value, T::Value); type Value = T::Value; fn identity() -> Self::InternalValue { (T::identity(), T::identity()) } fn mul(lhs: &Self::InternalValue, rhs: &Self::InternalValue) -> Self::InternalValue { (T::mul(&lhs.0, &rhs.0), T::mul(&rhs.1, &lhs.1)) } fn rev(value: &mut Self::InternalValue) { std::mem::swap(&mut value.0, &mut value.1); } fn into_front(value: Self::InternalValue) -> Self::Value { value.0 } fn from_front(value: Self::Value) -> Self::InternalValue { (value.clone(), value) } } } // }}} // fp {{{ // https://ngtkana.github.io/ac-adapter-rs/fp/index.html #[allow(dead_code)] mod fp { mod ext_gcd { pub(crate) fn mod_inv(x: u64) -> u64 { debug_assert!(P % 2 == 1); debug_assert!(P < 1 << 31); debug_assert!(x < P); mod_inv_signed(x as i64, P as i64) as u64 } fn mod_inv_signed(a: i64, m: i64) -> i64 { debug_assert!(a > 0); debug_assert!(m > 0); if a == 1 { return 1; } m + (1 - m * mod_inv_signed(m % a, a)) / a } } mod factorial { use super::Fp; use std::ops::Index; pub struct Factorial { fact: Vec>, inv_fact: Vec>, } impl Factorial

{ pub fn new(length: usize) -> Self { let mut fact = vec![Fp::

::new(1); length + 1]; let mut inv_fact = vec![Fp::

::new(1); length + 1]; for i in 1..=length { fact[i] = fact[i - 1] * Fp::

::new(i as u64); } inv_fact[length] = fact[length].inv(); for i in (1..=length).rev() { inv_fact[i - 1] = inv_fact[i] * Fp::

::new(i as u64); } Self { fact, inv_fact } } pub fn fact(&self, n: usize) -> Fp

{ self.fact[n] } pub fn inv_fact(&self, n: usize) -> Fp

{ self.inv_fact[n] } pub fn perm(&self, n: usize, k: usize) -> Fp

{ self.fact[n] * self.inv_fact[n - k] } pub fn comb(&self, n: usize, k: usize) -> Fp

{ self.fact[n] * self.inv_fact[n - k] * self.inv_fact[k] } pub fn binom(&self, n: usize, k: usize) -> Fp

{ self.comb(n, k) } pub fn comb_or_zero(&self, n: usize, k: isize) -> Fp

{ if k < 0 || k as usize > n { Fp::

::new(0) } else { self.comb(n, k as usize) } } pub fn comb_with_reputation(&self, n: usize, k: usize) -> Fp

{ assert!(n > 0 || k > 0); self.comb(n + k - 1, k) } } impl Index for Factorial

{ type Output = Fp

; fn index(&self, index: usize) -> &Self::Output { &self.fact[index] } } } mod fourier { use super::mod_inv; use super::Fp; use super::PrimitiveRoot; const P1: u64 = 924844033; const P2: u64 = 998244353; const P3: u64 = 1012924417; type F1 = Fp; type F2 = Fp; type F3 = Fp; pub fn fps_mul(a: impl AsRef<[Fp

]>, b: impl AsRef<[Fp

]>) -> Vec> where (): PrimitiveRoot

, { let a = a.as_ref(); let b = b.as_ref(); if a.is_empty() || b.is_empty() { return vec![]; } let mut a = a.to_vec(); let mut b = b.to_vec(); let n = a.len() + b.len() - 1; let len = n.next_power_of_two(); a.resize(len, Fp::new(0)); b.resize(len, Fp::new(0)); fft(&mut a); fft(&mut b); for (a, b) in a.iter_mut().zip(b.iter()) { *a *= *b; } ifft(&mut a); a.truncate(n); a } pub fn any_mod_fps_mul(a: &[Fp

], b: &[Fp

]) -> Vec> { let v1 = fps_mul( a.iter().map(|&x| F1::new(x.value())).collect::>(), b.iter().map(|&x| F1::new(x.value())).collect::>(), ); let v2 = fps_mul( a.iter().map(|&x| F2::new(x.value())).collect::>(), b.iter().map(|&x| F2::new(x.value())).collect::>(), ); let v3 = fps_mul( a.iter().map(|&x| F3::new(x.value())).collect::>(), b.iter().map(|&x| F3::new(x.value())).collect::>(), ); v1.into_iter() .zip(v2) .zip(v3) .map(|((e1, e2), e3)| garner(e1, e2, e3)) .collect::>() } pub fn fft(f: &mut [Fp

]) where (): PrimitiveRoot

, { let n = f.len(); assert!(n.is_power_of_two()); assert!((P - 1) % n as u64 == 0); let mut root = <() as PrimitiveRoot

>::VALUE.pow((P - 1) / f.len() as u64); let fourth = <() as PrimitiveRoot

>::VALUE.pow((P - 1) / 4); let mut fft_len = n; while 4 <= fft_len { let quarter = fft_len / 4; for f in f.chunks_mut(fft_len) { let mut c = Fp::new(1); for (((i, j), k), l) in (0..) .zip(quarter..) .zip(quarter * 2..) .zip(quarter * 3..) .take(quarter) { let c2 = c * c; let x = f[i] + f[k]; let y = f[j] + f[l]; let z = f[i] - f[k]; let w = fourth * (f[j] - f[l]); f[i] = x + y; f[j] = c2 * (x - y); f[k] = c * (z + w); f[l] = c2 * c * (z - w); c *= root; } } root *= root; root *= root; fft_len = quarter; } if fft_len == 2 { for f in f.chunks_mut(2) { let x = f[0]; let y = f[1]; f[0] = x + y; f[1] = x - y; } } } pub fn ifft(f: &mut [Fp

]) where (): PrimitiveRoot

, { let n = f.len(); assert!(n.is_power_of_two()); let root = <() as PrimitiveRoot

>::VALUE.pow((P - 1) / f.len() as u64); let mut roots = std::iter::successors(Some(root.inv()), |x| Some(x * x)) .take(n.trailing_zeros() as usize + 1) .collect::>(); roots.reverse(); let fourth = <() as PrimitiveRoot

>::VALUE.pow((P - 1) / 4).inv(); let mut quarter = 1_usize; if n.trailing_zeros() % 2 == 1 { for f in f.chunks_mut(2) { let x = f[0]; let y = f[1]; f[0] = x + y; f[1] = x - y; } quarter = 2; } while quarter != n { let fft_len = quarter * 4; let root = roots[fft_len.trailing_zeros() as usize]; for f in f.chunks_mut(fft_len) { let mut c = Fp::new(1); for (((i, j), k), l) in (0..) .zip(quarter..) .zip(quarter * 2..) .zip(quarter * 3..) .take(quarter) { let c2 = c * c; let x = f[i] + c2 * f[j]; let y = f[i] - c2 * f[j]; let z = c * (f[k] + c2 * f[l]); let w = fourth * c * (f[k] - c2 * f[l]); f[i] = x + z; f[j] = y + w; f[k] = x - z; f[l] = y - w; c *= root; } } quarter = fft_len; } let d = Fp::from(f.len()).inv(); f.iter_mut().for_each(|x| *x *= d); } fn garner(x1: Fp, x2: Fp, x3: Fp) -> Fp

{ let (x1, x2, x3) = (x1.value(), x2.value(), x3.value()); let x2 = ((x2 + (P2 - x1)) * mod_inv::(P1)) % P2; let x3 = (((x3 + (P3 - x1)) * mod_inv::(P1) % P3 + (P3 - x2)) * mod_inv::(P2)) % P3; Fp::new(x1 + P1 * (x2 + P2 * x3 % P)) } } use ext_gcd::mod_inv; pub use factorial::Factorial; pub use fourier::any_mod_fps_mul; pub use fourier::fft; pub use fourier::fps_mul; pub use fourier::ifft; use std::iter::Product; use std::iter::Sum; use std::mem::swap; 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; #[macro_export] macro_rules! fp { ($value:expr) => { $crate::fp::Fp::from($value) }; ($value:expr; mod $p:expr) => { $crate::fp::Fp::<$p>::from($value) }; } pub trait PrimitiveRoot { const VALUE: Fp

; } impl PrimitiveRoot<998244353> for () { const VALUE: Fp<998244353> = Fp::new(3); } impl PrimitiveRoot<1012924417> for () { const VALUE: Fp<1012924417> = Fp::new(5); } impl PrimitiveRoot<924844033> for () { const VALUE: Fp<924844033> = Fp::new(5); } #[derive(Clone, Copy, PartialEq, Eq, Hash)] pub struct Fp { value: u64, } impl Fp

{ pub const fn new(value: u64) -> Self { Self { value: value % P } } pub const fn value(self) -> u64 { self.value } pub fn inv(self) -> Self { Self { value: mod_inv::

(self.value), } } pub fn pow(self, mut exp: u64) -> Self { let mut result = Self::new(1); let mut base = self; while exp > 0 { if exp & 1 == 1 { result *= base; } base *= base; exp >>= 1; } result } pub fn sign(pow: usize) -> Self { Self::new(if pow % 2 == 0 { 1 } else { P - 1 }) } } impl std::fmt::Debug for Fp

{ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { pub fn berlekamp_massey_fp(a: i64, p: i64) -> [i64; 2] { let mut u0 = 0_i64; let mut v0 = 1_i64; let mut w0 = a * u0 + p * v0; let mut u1 = 1_i64; let mut v1 = 0_i64; let mut w1 = a * u1 + p * v1; while p <= w0 * w0 { let q = w0 / w1; u0 -= q * u1; v0 -= q * v1; w0 -= q * w1; swap(&mut u0, &mut u1); swap(&mut v0, &mut v1); swap(&mut w0, &mut w1); } [w0, u0] } if self.value == 0 { return write!(f, "0"); } let [mut num, mut den] = berlekamp_massey_fp(self.value as i64, P as i64); if den < 0 { num = -num; den = -den; } if den == 1 { write!(f, "{}", num) } else { write!(f, "{}/{}", num, den) } } } impl std::fmt::Display for Fp

{ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.value()) } } macro_rules! impl_from_signed { ($($t:ty),*) => { $( impl From<$t> for Fp

{ fn from(x: $t) -> Self { if x < 0 { -Self::new((P as i64 - x as i64) as u64) } else { Self::new(x as u64) } } } )* }; } impl_from_signed!(i8, i16, i32, i64, i128, isize); macro_rules! impl_from_unsigned { ($($t:ty),*) => { $( impl From<$t> for Fp

{ fn from(x: $t) -> Self { Self::new(x as u64) } } )* }; } impl_from_unsigned!(u8, u16, u32, u64, u128, usize); impl AddAssign> for Fp

{ fn add_assign(&mut self, rhs: Fp

) { self.value += rhs.value; if self.value >= P { self.value -= P; } } } impl SubAssign> for Fp

{ fn sub_assign(&mut self, rhs: Fp

) { if self.value < rhs.value { self.value += P; } self.value -= rhs.value; } } impl MulAssign> for Fp

{ fn mul_assign(&mut self, rhs: Fp

) { self.value = self.value * rhs.value % P; } } #[allow(clippy::suspicious_op_assign_impl)] impl DivAssign> for Fp

{ fn div_assign(&mut self, rhs: Fp

) { *self *= rhs.inv() } } macro_rules! fp_forward_ops { ($( $trait:ident, $trait_assign:ident, $fn:ident, $fn_assign:ident, )*) => {$( impl $trait_assign<&Fp

> for Fp

{ fn $fn_assign(&mut self, rhs: &Fp

) { self.$fn_assign(*rhs); } } impl>> $trait for Fp

{ type Output = Fp

; fn $fn(mut self, rhs: T) -> Self::Output { self.$fn_assign(rhs.into()); self } } impl $trait<&Fp

> for Fp

{ type Output = Fp

; fn $fn(self, rhs: &Fp

) -> Self::Output { self.$fn(*rhs) } } impl>> $trait for &Fp

{ type Output = Fp

; fn $fn(self, rhs: T) -> Self::Output { (*self).$fn(rhs.into()) } } impl $trait<&Fp

> for &Fp

{ type Output = Fp

; fn $fn(self, rhs: &Fp

) -> Self::Output { (*self).$fn(*rhs) } } )*}; } fp_forward_ops! { Add, AddAssign, add, add_assign, Sub, SubAssign, sub, sub_assign, Mul, MulAssign, mul, mul_assign, Div, DivAssign, div, div_assign, } impl Neg for Fp

{ type Output = Fp

; fn neg(mut self) -> Self::Output { if self.value > 0 { self.value = P - self.value; } self } } impl Sum for Fp

{ fn sum>(iter: I) -> Self { iter.fold(Self::new(0), |acc, x| acc + x) } } impl<'a, const P: u64> Sum<&'a Self> for Fp

{ fn sum>(iter: I) -> Self { iter.copied().sum() } } impl Product for Fp

{ fn product>(iter: I) -> Self { iter.fold(Self::new(1), |acc, x| acc * x) } } impl<'a, const P: u64> Product<&'a Self> for Fp

{ fn product>(iter: I) -> Self { iter.copied().product() } } } // }}} // splay_tree {{{ // https://ngtkana.github.io/ac-adapter-rs/splay_tree/index.html #[allow(dead_code)] mod splay_tree { mod node { use super::LazyOps; use std::cmp::Ordering; use std::fmt::Debug; use std::mem::replace; use std::mem::swap; use std::ptr::null_mut; use std::ptr::{self}; #[allow(unused_must_use)] pub fn deep_free(root: *mut Node) { if !root.is_null() { unsafe { deep_free((*root).left); deep_free((*root).right); Box::from_raw(root); } } } pub fn access_index(mut root: &mut Node, mut i: usize) -> &mut Node { loop { root.push(); if let Some(left) = unsafe { root.left.as_mut() } { left.push(); } if let Some(right) = unsafe { root.right.as_mut() } { right.push(); } let lsize = unsafe { root.left.as_ref() }.map_or(0, |left| left.len); root = match i.cmp(&lsize) { Ordering::Less => unsafe { root.left.as_mut() }.unwrap(), Ordering::Equal => { root.splay(); return root; } Ordering::Greater => { i -= lsize + 1; unsafe { root.right.as_mut() }.unwrap() } }; } } pub fn merge(left: *mut Node, right: *mut Node) -> *mut Node { let ans = if let Some(mut left) = unsafe { left.as_mut() } { if let Some(right) = unsafe { right.as_mut() } { left = access_index(left, left.len - 1); left.push(); left.right = right; right.parent = left; left.update(); } left } else { right }; ans } pub fn split_at(root: *mut Node, at: usize) -> [*mut Node; 2] { if let Some(mut root) = unsafe { root.as_mut() } { if at == root.len { [root, null_mut()] } else if at == 0 { [null_mut(), root] } else { root = access_index(root, at); root.push(); let left = replace(&mut root.left, null_mut()); if let Some(left) = unsafe { left.as_mut() } { left.parent = null_mut(); root.update(); } [left, root] } } else { [null_mut(), null_mut()] } } pub struct Node { pub left: *mut Self, pub right: *mut Self, pub parent: *mut Self, pub len: usize, pub rev: bool, pub value: O::Value, pub acc: O::Acc, pub lazy: Option, } impl Node { pub fn new(value: O::Value) -> Self { Node { left: null_mut(), right: null_mut(), parent: null_mut(), len: 1, rev: false, acc: O::proj(&value), value, lazy: None, } } pub fn dump(&self) where O::Value: Debug, O::Acc: Debug, O::Lazy: Debug, { if let Some(left) = unsafe { self.left.as_ref() } { left.dump(); } println!( "{:?}: parent = {:?}, left = {:?}, right = {:?}, len = {}, rev = {}, value = \ {:?}, acc = {:?}, lazy = {:?}", self as *const _, self.parent, self.left, self.right, self.len, self.rev, self.value, self.acc, self.lazy ); if let Some(right) = unsafe { self.right.as_ref() } { right.dump(); } } pub fn update(&mut self) { self.len = 1; self.acc = O::proj(&self.value); if let Some(left) = unsafe { self.left.as_mut() } { left.push(); self.len += left.len; self.acc = O::op(&left.acc, &self.acc); } if let Some(right) = unsafe { self.right.as_mut() } { right.push(); self.len += right.len; self.acc = O::op(&self.acc, &right.acc); } } pub fn push(&mut self) { if let Some(lazy) = self.lazy.take() { O::act_value(&lazy, &mut self.value); O::act_acc(&lazy, &mut self.acc); if let Some(left) = unsafe { self.left.as_mut() } { O::compose_to_option(&lazy, &mut left.lazy); } if let Some(right) = unsafe { self.right.as_mut() } { O::compose_to_option(&lazy, &mut right.lazy); } } if replace(&mut self.rev, false) { swap(&mut self.left, &mut self.right); if let Some(left) = unsafe { self.left.as_mut() } { left.rev ^= true; } if let Some(right) = unsafe { self.right.as_mut() } { right.rev ^= true; } } } pub fn rotate(&mut self) { let p = unsafe { &mut *self.parent }; let g = p.parent; self.push(); if ptr::eq(self, p.left) { p.left = self.right; if let Some(c) = unsafe { p.left.as_mut() } { c.parent = p; } self.right = p; } else { p.right = self.left; if let Some(c) = unsafe { p.right.as_mut() } { c.parent = p; } self.left = p; } p.parent = self; self.parent = g; if let Some(g) = unsafe { g.as_mut() } { if ptr::eq(p, g.left) { g.left = self; } else { g.right = self; } } p.update(); self.update(); } pub fn splay(&mut self) { while let Some(p) = unsafe { self.parent.as_mut() } { if let Some(g) = unsafe { p.parent.as_mut() } { if ptr::eq(self, p.left) == ptr::eq(p, g.left) { p.rotate(); } else { self.rotate(); } } self.rotate(); } } } } use self::node::access_index; use self::node::deep_free; use self::node::merge; use self::node::split_at; use self::node::Node; use std::cell::Cell; use std::cmp::Ordering; use std::fmt::Debug; use std::hash::Hash; use std::iter::FromIterator; use std::marker::PhantomData; use std::ops::Bound; use std::ops::Deref; use std::ops::DerefMut; use std::ops::Index; use std::ops::Range; use std::ops::RangeBounds; use std::ptr::null_mut; pub trait Value: Sized + Debug + Clone {} impl Value for T {} pub struct Nop(PhantomData T>); impl LazyOps for Nop { type Acc = (); type Lazy = (); type Value = T; fn proj(_value: &Self::Value) -> Self::Acc {} fn op(&(): &Self::Acc, &(): &Self::Acc) -> Self::Acc {} fn act_value(&(): &Self::Lazy, _value: &mut Self::Value) {} fn act_acc(&(): &Self::Lazy, &mut (): &mut Self::Acc) {} fn compose(&(): &Self::Lazy, &mut (): &mut Self::Lazy) {} } pub trait Ops { type Value: Value; type Acc: Value; fn proj(value: &Self::Value) -> Self::Acc; fn op(lhs: &Self::Acc, rhs: &Self::Acc) -> Self::Acc; } pub struct NoLazy(PhantomData O>); impl LazyOps for NoLazy { type Acc = O::Acc; type Lazy = (); type Value = O::Value; fn proj(value: &Self::Value) -> Self::Acc { O::proj(value) } fn op(lhs: &Self::Acc, rhs: &Self::Acc) -> Self::Acc { O::op(lhs, rhs) } fn act_value(&(): &Self::Lazy, _value: &mut Self::Value) {} fn act_acc(&(): &Self::Lazy, _acc: &mut Self::Acc) {} fn compose(&(): &Self::Lazy, &mut (): &mut Self::Lazy) {} } pub trait LazyOps { type Value: Value; type Acc: Value; type Lazy: Value; fn proj(value: &Self::Value) -> Self::Acc; fn op(lhs: &Self::Acc, rhs: &Self::Acc) -> Self::Acc; fn act_value(lazy: &Self::Lazy, value: &mut Self::Value); fn act_acc(lazy: &Self::Lazy, acc: &mut Self::Acc); fn compose(upper: &Self::Lazy, lower: &mut Self::Lazy); fn compose_to_option(upper: &Self::Lazy, lower: &mut Option) { match lower { None => *lower = Some(upper.clone()), Some(lower) => Self::compose(upper, lower), } } } pub struct SplayTree(Cell<*mut Node>); impl SplayTree { pub fn new() -> Self { Self(Cell::new(null_mut())) } pub fn is_empty(&self) -> bool { self.0.get().is_null() } pub fn len(&self) -> usize { unsafe { self.0.get().as_ref() }.map_or(0, |root| root.len) } pub fn insert(&mut self, at: usize, value: O::Value) { if self.len() < at { splay_tree_index_out_of_range_fail(at, self.len()); } let [left, right] = split_at(self.0.get(), at); let node = Box::leak(Box::new(Node::new(value))); self.0.set(merge(merge(left, node), right)); } pub fn delete(&mut self, at: usize) -> O::Value { if self.len() <= at { splay_tree_index_out_of_range_fail(at, self.len()); } let [lc, r] = split_at(self.0.get(), at + 1); let [l, c] = split_at(lc, at); let ans = unsafe { Box::from_raw(c) }.value; self.0.set(merge(l, r)); ans } pub fn reverse(&mut self, range: impl RangeBounds) { let Range { start, end } = into_range(self.len(), range); let [lc, r] = split_at(self.0.get(), end); let [l, c] = split_at(lc, start); if let Some(c) = unsafe { c.as_mut() } { c.rev ^= true; c.push(); } self.0.set(merge(merge(l, c), r)); } pub fn fold(&self, range: impl RangeBounds) -> Option { let Range { start, end } = into_range(self.len(), range); let [lc, r] = split_at(self.0.get(), end); let [l, c] = split_at(lc, start); let ans = unsafe { c.as_mut() }.map(|c| { c.update(); c.acc.clone() }); self.0.set(merge(merge(l, c), r)); ans } pub fn act(&mut self, range: impl RangeBounds, lazy: O::Lazy) { let Range { start, end } = into_range(self.len(), range); let [lc, r] = split_at(self.0.get(), end); let [l, c] = split_at(lc, start); if let Some(c) = unsafe { c.as_mut() } { c.lazy = Some(lazy); c.push(); } self.0.set(merge(merge(l, c), r)); } pub fn get(&self, i: usize) -> Option<&O::Value> { if self.len() <= i { return None; } let mut root = unsafe { self.0.get().as_mut() }.unwrap(); root = access_index(root, i); self.0.set(root); let ans = &root.value; Some(ans) } pub fn entry(&mut self, i: usize) -> Option> { if self.len() <= i { return None; } let mut root = unsafe { self.0.get().as_mut() }.unwrap(); root = access_index(root, i); self.0.set(root); Some(Entry(self)) } pub fn split_off(&mut self, at: usize) -> Self { if self.len() < at { splay_tree_index_out_of_range_fail(at, self.len()); } let [left, right] = split_at(self.0.get(), at); self.0.set(left); Self(Cell::new(right)) } pub fn append(&mut self, right: &Self) { let root = merge(self.0.get(), right.0.get()); self.0.set(root); right.0.set(null_mut()); } pub fn iter(&self) -> Iter<'_, O> { Iter { splay: self, start: 0, end: self.len(), } } pub fn range(&self, range: impl RangeBounds) -> Iter<'_, O> { let Range { start, end } = into_range(self.len(), range); Iter { splay: self, start, end, } } pub fn dump(&self) { println!(" === start dump === "); match unsafe { self.0.get().as_ref() } { None => println!("empty"), Some(root) => root.dump(), } println!(" === end dump === "); } } impl FromIterator for SplayTree { fn from_iter>(iter: T) -> Self { let mut iter = iter.into_iter(); let mut root = match iter.next() { None => return Self::new(), Some(value) => Box::leak(Box::new(Node::new(value))), }; for value in iter { let node = Box::leak(Box::new(Node::new(value))); root.parent = node; node.left = root; node.update(); root = node; } Self(Cell::new(root)) } } impl<'a, O: LazyOps> IntoIterator for &'a SplayTree { type IntoIter = Iter<'a, O>; type Item = &'a O::Value; fn into_iter(self) -> Self::IntoIter { self.iter() } } impl Debug for SplayTree { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { f.debug_list().entries(self.iter()).finish() } } impl Clone for SplayTree { fn clone(&self) -> Self { self.iter().cloned().collect() } } impl Default for SplayTree { fn default() -> Self { Self(Cell::new(null_mut())) } } impl PartialEq for SplayTree where O::Value: PartialEq, { fn eq(&self, other: &Self) -> bool { self.len() == other.len() && self.iter().zip(other.iter()).all(|(x, y)| x == y) } } impl Eq for SplayTree where O::Value: Eq {} impl PartialOrd for SplayTree where O::Value: PartialOrd, { fn partial_cmp(&self, other: &Self) -> Option { for (x, y) in self.iter().zip(other.iter()) { match x.partial_cmp(y) { Some(Ordering::Equal) => (), non_eq => return non_eq, } } self.len().partial_cmp(&other.len()) } } impl Ord for SplayTree where O::Value: Ord, { fn cmp(&self, other: &Self) -> Ordering { for (x, y) in self.iter().zip(other.iter()) { match x.cmp(y) { Ordering::Equal => (), non_eq => return non_eq, } } self.len().cmp(&other.len()) } } impl Hash for SplayTree where O::Value: Hash, { fn hash(&self, state: &mut H) { self.iter().for_each(|x| x.hash(state)) } } impl Index for SplayTree { type Output = O::Value; fn index(&self, index: usize) -> &Self::Output { if self.len() <= index { splay_tree_index_out_of_range_fail(index, self.len()); } self.get(index).unwrap() } } pub struct Iter<'a, O: LazyOps> { splay: &'a SplayTree, start: usize, end: usize, } impl<'a, O: LazyOps> Iterator for Iter<'a, O> { type Item = &'a O::Value; fn next(&mut self) -> Option { if self.start == self.end { None } else { let ans = self.splay.get(self.start).unwrap(); self.start += 1; Some(ans) } } } impl<'a, O: LazyOps> DoubleEndedIterator for Iter<'a, O> { fn next_back(&mut self) -> Option { if self.start == self.end { None } else { self.end -= 1; let ans = self.splay.get(self.end).unwrap(); Some(ans) } } } pub struct Entry<'a, O: LazyOps>(&'a mut SplayTree); impl Deref for Entry<'_, O> { type Target = O::Value; fn deref(&self) -> &Self::Target { &unsafe { &*self.0 .0.get() }.value } } impl DerefMut for Entry<'_, O> { fn deref_mut(&mut self) -> &mut Self::Target { &mut unsafe { &mut *self.0 .0.get() }.value } } impl Drop for SplayTree { fn drop(&mut self) { deep_free(self.0.get()); } } fn into_range(len: usize, range: impl RangeBounds) -> Range { let start = match range.start_bound() { Bound::Included(&start) => start, Bound::Excluded(&start) => start - 1, Bound::Unbounded => 0, }; let end = match range.end_bound() { Bound::Included(&end) => end + 1, Bound::Excluded(&end) => end, Bound::Unbounded => len, }; if len < start { splay_tree_start_index_len_fail(start, len); } if len < end { splay_tree_end_index_len_fail(end, len); } if start > end { splay_tree_index_order_fail(start, end) } start..end } fn splay_tree_index_out_of_range_fail(index: usize, len: usize) -> ! { panic!( "range index {} out of range for splay tree of length {}", index, len ); } fn splay_tree_start_index_len_fail(index: usize, len: usize) -> ! { panic!( "range start index {} out of range for splay tree of length {}", index, len ); } fn splay_tree_end_index_len_fail(index: usize, len: usize) -> ! { panic!( "range end index {} out of range for splay tree of length {}", index, len ); } fn splay_tree_index_order_fail(index: usize, end: usize) -> ! { panic!("splay tree index starts at {} but ends at {}", index, end); } } // }}}