QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#309125 | #8133. When Anton Saw This Task He Reacted With 😩 | ucup-team635# | WA | 1223ms | 55404kb | Rust | 31.0kb | 2024-01-20 14:59:55 | 2024-01-20 14:59:55 |
Judging History
answer
use std::ops::*;
// ---------- begin trait ----------
pub trait Zero: Sized + Add<Self, Output = Self> {
fn zero() -> Self;
fn is_zero(&self) -> bool;
}
pub trait One: Sized + Mul<Self, Output = Self> {
fn one() -> Self;
fn is_one(&self) -> bool;
}
pub trait Ring: Zero + One + Sub<Output = Self> {}
pub trait Field: Ring + Div<Output = Self> {}
// ---------- end trait ----------
// ---------- begin modint ----------
pub const fn pow_mod(mut r: u32, mut n: u32, m: u32) -> u32 {
let mut t = 1;
while n > 0 {
if n & 1 == 1 {
t = (t as u64 * r as u64 % m as u64) as u32;
}
r = (r as u64 * r as u64 % m as u64) as u32;
n >>= 1;
}
t
}
pub const fn primitive_root(p: u32) -> u32 {
let mut m = p - 1;
let mut f = [1; 30];
let mut k = 0;
let mut d = 2;
while d * d <= m {
if m % d == 0 {
f[k] = d;
k += 1;
}
while m % d == 0 {
m /= d;
}
d += 1;
}
if m > 1 {
f[k] = m;
k += 1;
}
let mut g = 1;
while g < p {
let mut ok = true;
let mut i = 0;
while i < k {
ok &= pow_mod(g, (p - 1) / f[i], p) > 1;
i += 1;
}
if ok {
break;
}
g += 1;
}
g
}
pub const fn is_prime(n: u32) -> bool {
if n <= 1 {
return false;
}
let mut d = 2;
while d * d <= n {
if n % d == 0 {
return false;
}
d += 1;
}
true
}
#[derive(Clone, Copy, PartialEq, Eq)]
pub struct ModInt<const M: u32>(u32);
impl<const M: u32> ModInt<{ M }> {
const REM: u32 = {
let mut t = 1u32;
let mut s = !M + 1;
let mut n = !0u32 >> 2;
while n > 0 {
if n & 1 == 1 {
t = t.wrapping_mul(s);
}
s = s.wrapping_mul(s);
n >>= 1;
}
t
};
const INI: u64 = ((1u128 << 64) % M as u128) as u64;
const IS_PRIME: () = assert!(is_prime(M));
const PRIMITIVE_ROOT: u32 = primitive_root(M);
const ORDER: usize = 1 << (M - 1).trailing_zeros();
const fn reduce(x: u64) -> u32 {
let _ = Self::IS_PRIME;
let b = (x as u32 * Self::REM) as u64;
let t = x + b * M as u64;
let mut c = (t >> 32) as u32;
if c >= M {
c -= M;
}
c as u32
}
const fn multiply(a: u32, b: u32) -> u32 {
Self::reduce(a as u64 * b as u64)
}
pub const fn new(v: u32) -> Self {
assert!(v < M);
Self(Self::reduce(v as u64 * Self::INI))
}
pub const fn const_mul(&self, rhs: Self) -> Self {
Self(Self::multiply(self.0, rhs.0))
}
pub const fn pow(&self, mut n: u64) -> Self {
let mut t = Self::new(1);
let mut r = *self;
while n > 0 {
if n & 1 == 1 {
t = t.const_mul(r);
}
r = r.const_mul(r);
n >>= 1;
}
t
}
pub const fn inv(&self) -> Self {
assert!(self.0 != 0);
self.pow(M as u64 - 2)
}
pub const fn get(&self) -> u32 {
Self::reduce(self.0 as u64)
}
pub const fn zero() -> Self {
Self::new(0)
}
pub const fn one() -> Self {
Self::new(1)
}
}
impl<const M: u32> Add for ModInt<{ M }> {
type Output = Self;
fn add(self, rhs: Self) -> Self::Output {
let mut v = self.0 + rhs.0;
if v >= M {
v -= M;
}
Self(v)
}
}
impl<const M: u32> Sub for ModInt<{ M }> {
type Output = Self;
fn sub(self, rhs: Self) -> Self::Output {
let mut v = self.0 - rhs.0;
if self.0 < rhs.0 {
v += M;
}
Self(v)
}
}
impl<const M: u32> Mul for ModInt<{ M }> {
type Output = Self;
fn mul(self, rhs: Self) -> Self::Output {
self.const_mul(rhs)
}
}
impl<const M: u32> Div for ModInt<{ M }> {
type Output = Self;
fn div(self, rhs: Self) -> Self::Output {
self * rhs.inv()
}
}
impl<const M: u32> AddAssign for ModInt<{ M }> {
fn add_assign(&mut self, rhs: Self) {
*self = *self + rhs;
}
}
impl<const M: u32> SubAssign for ModInt<{ M }> {
fn sub_assign(&mut self, rhs: Self) {
*self = *self - rhs;
}
}
impl<const M: u32> MulAssign for ModInt<{ M }> {
fn mul_assign(&mut self, rhs: Self) {
*self = *self * rhs;
}
}
impl<const M: u32> DivAssign for ModInt<{ M }> {
fn div_assign(&mut self, rhs: Self) {
*self = *self / rhs;
}
}
impl<const M: u32> Neg for ModInt<{ M }> {
type Output = Self;
fn neg(self) -> Self::Output {
if self.0 == 0 {
self
} else {
Self(M - self.0)
}
}
}
impl<const M: u32> std::fmt::Display for ModInt<{ M }> {
fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
write!(f, "{}", self.get())
}
}
impl<const M: u32> std::fmt::Debug for ModInt<{ M }> {
fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
write!(f, "{}", self.get())
}
}
impl<const M: u32> std::str::FromStr for ModInt<{ M }> {
type Err = std::num::ParseIntError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let val = s.parse::<u32>()?;
Ok(ModInt::new(val))
}
}
impl<const M: u32> From<usize> for ModInt<{ M }> {
fn from(val: usize) -> ModInt<{ M }> {
ModInt::new((val % M as usize) as u32)
}
}
// ---------- end modint ----------
// ---------- begin precalc ----------
pub struct Precalc<const MOD: u32> {
fact: Vec<ModInt<MOD>>,
ifact: Vec<ModInt<MOD>>,
inv: Vec<ModInt<MOD>>,
}
impl<const MOD: u32> Precalc<MOD> {
pub fn new(size: usize) -> Self {
let mut fact = vec![ModInt::one(); size + 1];
let mut ifact = vec![ModInt::one(); size + 1];
let mut inv = vec![ModInt::one(); size + 1];
for i in 2..=size {
fact[i] = fact[i - 1] * ModInt::from(i);
}
ifact[size] = fact[size].inv();
for i in (2..=size).rev() {
inv[i] = ifact[i] * fact[i - 1];
ifact[i - 1] = ifact[i] * ModInt::from(i);
}
Self { fact, ifact, inv }
}
pub fn fact(&self, n: usize) -> ModInt<MOD> {
self.fact[n]
}
pub fn ifact(&self, n: usize) -> ModInt<MOD> {
self.ifact[n]
}
pub fn inv(&self, n: usize) -> ModInt<MOD> {
assert!(0 < n);
self.inv[n]
}
pub fn perm(&self, n: usize, k: usize) -> ModInt<MOD> {
if k > n {
return ModInt::zero();
}
self.fact[n] * self.ifact[n - k]
}
pub fn binom(&self, n: usize, k: usize) -> ModInt<MOD> {
if n < k {
return ModInt::zero();
}
self.fact[n] * self.ifact[k] * self.ifact[n - k]
}
}
// ---------- end precalc ----------
impl<const M: u32> Zero for ModInt<{ M }> {
fn zero() -> Self {
Self::zero()
}
fn is_zero(&self) -> bool {
self.0 == 0
}
}
impl<const M: u32> One for ModInt<{ M }> {
fn one() -> Self {
Self::one()
}
fn is_one(&self) -> bool {
self.get() == 1
}
}
impl<const M: u32> Ring for ModInt<{ M }> {}
impl<const M: u32> Field for ModInt<{ M }> {}
// ---------- begin array op ----------
struct NTTPrecalc<const M: u32> {
sum_e: [ModInt<{ M }>; 30],
sum_ie: [ModInt<{ M }>; 30],
}
impl<const M: u32> NTTPrecalc<{ M }> {
const fn new() -> Self {
let cnt2 = (M - 1).trailing_zeros() as usize;
let root = ModInt::new(ModInt::<{ M }>::PRIMITIVE_ROOT);
let zeta = root.pow((M - 1) as u64 >> cnt2);
let mut es = [ModInt::zero(); 30];
let mut ies = [ModInt::zero(); 30];
let mut sum_e = [ModInt::zero(); 30];
let mut sum_ie = [ModInt::zero(); 30];
let mut e = zeta;
let mut ie = e.inv();
let mut i = cnt2;
while i >= 2 {
es[i - 2] = e;
ies[i - 2] = ie;
e = e.const_mul(e);
ie = ie.const_mul(ie);
i -= 1;
}
let mut now = ModInt::one();
let mut inow = ModInt::one();
let mut i = 0;
while i < cnt2 - 1 {
sum_e[i] = es[i].const_mul(now);
sum_ie[i] = ies[i].const_mul(inow);
now = ies[i].const_mul(now);
inow = es[i].const_mul(inow);
i += 1;
}
Self { sum_e, sum_ie }
}
}
struct NTTPrecalcHelper<const MOD: u32>;
impl<const MOD: u32> NTTPrecalcHelper<MOD> {
const A: NTTPrecalc<MOD> = NTTPrecalc::new();
}
pub trait ArrayAdd {
type Item;
fn add(&self, rhs: &[Self::Item]) -> Vec<Self::Item>;
}
impl<T> ArrayAdd for [T]
where
T: Zero + Copy,
{
type Item = T;
fn add(&self, rhs: &[Self::Item]) -> Vec<Self::Item> {
let mut c = vec![T::zero(); self.len().max(rhs.len())];
c[..self.len()].copy_from_slice(self);
c.add_assign(rhs);
c
}
}
pub trait ArrayAddAssign {
type Item;
fn add_assign(&mut self, rhs: &[Self::Item]);
}
impl<T> ArrayAddAssign for [T]
where
T: Add<Output = T> + Copy,
{
type Item = T;
fn add_assign(&mut self, rhs: &[Self::Item]) {
assert!(self.len() >= rhs.len());
self.iter_mut().zip(rhs).for_each(|(x, a)| *x = *x + *a);
}
}
impl<T> ArrayAddAssign for Vec<T>
where
T: Zero + Add<Output = T> + Copy,
{
type Item = T;
fn add_assign(&mut self, rhs: &[Self::Item]) {
if self.len() < rhs.len() {
self.resize(rhs.len(), T::zero());
}
self.as_mut_slice().add_assign(rhs);
}
}
pub trait ArraySub {
type Item;
fn sub(&self, rhs: &[Self::Item]) -> Vec<Self::Item>;
}
impl<T> ArraySub for [T]
where
T: Zero + Sub<Output = T> + Copy,
{
type Item = T;
fn sub(&self, rhs: &[Self::Item]) -> Vec<Self::Item> {
let mut c = vec![T::zero(); self.len().max(rhs.len())];
c[..self.len()].copy_from_slice(self);
c.sub_assign(rhs);
c
}
}
pub trait ArraySubAssign {
type Item;
fn sub_assign(&mut self, rhs: &[Self::Item]);
}
impl<T> ArraySubAssign for [T]
where
T: Sub<Output = T> + Copy,
{
type Item = T;
fn sub_assign(&mut self, rhs: &[Self::Item]) {
assert!(self.len() >= rhs.len());
self.iter_mut().zip(rhs).for_each(|(x, a)| *x = *x - *a);
}
}
impl<T> ArraySubAssign for Vec<T>
where
T: Zero + Sub<Output = T> + Copy,
{
type Item = T;
fn sub_assign(&mut self, rhs: &[Self::Item]) {
if self.len() < rhs.len() {
self.resize(rhs.len(), T::zero());
}
self.as_mut_slice().sub_assign(rhs);
}
}
pub trait ArrayDot {
type Item;
fn dot(&self, rhs: &[Self::Item]) -> Vec<Self::Item>;
}
impl<T> ArrayDot for [T]
where
T: Mul<Output = T> + Copy,
{
type Item = T;
fn dot(&self, rhs: &[Self::Item]) -> Vec<Self::Item> {
assert!(self.len() == rhs.len());
self.iter().zip(rhs).map(|p| *p.0 * *p.1).collect()
}
}
pub trait ArrayDotAssign {
type Item;
fn dot_assign(&mut self, rhs: &[Self::Item]);
}
impl<T> ArrayDotAssign for [T]
where
T: MulAssign + Copy,
{
type Item = T;
fn dot_assign(&mut self, rhs: &[Self::Item]) {
assert!(self.len() == rhs.len());
self.iter_mut().zip(rhs).for_each(|(x, a)| *x *= *a);
}
}
pub trait ArrayMul {
type Item;
fn mul(&self, rhs: &[Self::Item]) -> Vec<Self::Item>;
}
impl<T> ArrayMul for [T]
where
T: Zero + One + Copy,
{
type Item = T;
fn mul(&self, rhs: &[Self::Item]) -> Vec<Self::Item> {
if self.is_empty() || rhs.is_empty() {
return vec![];
}
let mut res = vec![T::zero(); self.len() + rhs.len() - 1];
for (i, a) in self.iter().enumerate() {
for (res, b) in res[i..].iter_mut().zip(rhs.iter()) {
*res = *res + *a * *b;
}
}
res
}
}
// transform でlen=1を指定すればNTTになる
pub trait ArrayConvolution {
type Item;
fn transform(&mut self, len: usize);
fn inverse_transform(&mut self, len: usize);
fn convolution(&self, rhs: &[Self::Item]) -> Vec<Self::Item>;
}
impl<const M: u32> ArrayConvolution for [ModInt<{ M }>] {
type Item = ModInt<{ M }>;
fn transform(&mut self, len: usize) {
let f = self;
let n = f.len();
let k = (n / len).trailing_zeros() as usize;
assert!(len << k == n);
assert!(k <= ModInt::<{ M }>::ORDER);
let pre = &NTTPrecalcHelper::<{ M }>::A;
for ph in 1..=k {
let p = len << (k - ph);
let mut now = ModInt::one();
for (i, f) in f.chunks_exact_mut(2 * p).enumerate() {
let (x, y) = f.split_at_mut(p);
for (x, y) in x.iter_mut().zip(y.iter_mut()) {
let l = *x;
let r = *y * now;
*x = l + r;
*y = l - r;
}
now *= pre.sum_e[(!i).trailing_zeros() as usize];
}
}
}
fn inverse_transform(&mut self, len: usize) {
let f = self;
let n = f.len();
let k = (n / len).trailing_zeros() as usize;
assert!(len << k == n);
assert!(k <= ModInt::<{ M }>::ORDER);
let pre = &NTTPrecalcHelper::<{ M }>::A;
for ph in (1..=k).rev() {
let p = len << (k - ph);
let mut inow = ModInt::one();
for (i, f) in f.chunks_exact_mut(2 * p).enumerate() {
let (x, y) = f.split_at_mut(p);
for (x, y) in x.iter_mut().zip(y.iter_mut()) {
let l = *x;
let r = *y;
*x = l + r;
*y = (l - r) * inow;
}
inow *= pre.sum_ie[(!i).trailing_zeros() as usize];
}
}
let ik = ModInt::new(2).inv().pow(k as u64);
for f in f.iter_mut() {
*f *= ik;
}
}
fn convolution(&self, rhs: &[Self::Item]) -> Vec<Self::Item> {
if self.len().min(rhs.len()) <= 32 {
return self.mul(rhs);
}
const PARAM: usize = 10;
let size = self.len() + rhs.len() - 1;
let mut k = 0;
while (size + (1 << k) - 1) >> k > PARAM {
k += 1;
}
let len = (size + (1 << k) - 1) >> k;
let mut f = vec![ModInt::zero(); len << k];
let mut g = vec![ModInt::zero(); len << k];
f[..self.len()].copy_from_slice(self);
g[..rhs.len()].copy_from_slice(rhs);
f.transform(len);
g.transform(len);
let mut buf = [ModInt::zero(); 2 * PARAM - 1];
let buf = &mut buf[..(2 * len - 1)];
let pre = &NTTPrecalcHelper::<{ M }>::A;
let mut now = ModInt::one();
for (i, (f, g)) in f
.chunks_exact_mut(2 * len)
.zip(g.chunks_exact(2 * len))
.enumerate()
{
let mut r = now;
for (f, g) in f.chunks_exact_mut(len).zip(g.chunks_exact(len)) {
buf.fill(ModInt::zero());
for (i, f) in f.iter().enumerate() {
for (buf, g) in buf[i..].iter_mut().zip(g.iter()) {
*buf = *buf + *f * *g;
}
}
f.copy_from_slice(&buf[..len]);
for (f, buf) in f.iter_mut().zip(buf[len..].iter()) {
*f = *f + r * *buf;
}
r = -r;
}
now *= pre.sum_e[(!i).trailing_zeros() as usize];
}
f.inverse_transform(len);
f.truncate(self.len() + rhs.len() - 1);
f
}
}
// ---------- end array op ----------
// ---------- begin Heavy-Light decomposition ----------
pub struct HLD {
size: usize,
edge: Vec<(usize, usize)>,
child: Vec<Vec<usize>>,
path_root: Vec<usize>,
parent: Vec<usize>,
left: Vec<usize>,
right: Vec<usize>,
inverse: Vec<usize>,
}
impl HLD {
pub fn new(size: usize) -> Self {
assert!(size <= 10usize.pow(8));
HLD {
size: size,
edge: Vec::with_capacity(size - 1),
child: Vec::new(),
path_root: Vec::new(),
parent: Vec::new(),
left: Vec::new(),
right: Vec::new(),
inverse: Vec::new(),
}
}
pub fn add_edge(&mut self, a: usize, b: usize) {
assert!(a != b && a < self.size && b < self.size);
self.edge.push((a, b));
}
pub fn build(&mut self, root: usize) {
assert!(self.edge.len() + 1 == self.size);
let size = self.size;
let mut cnt = vec![0; size];
for &(a, b) in self.edge.iter() {
cnt[a] += 1;
cnt[b] += 1;
}
let mut child = cnt
.into_iter()
.map(|c| Vec::with_capacity(c))
.collect::<Vec<_>>();
for &(a, b) in self.edge.iter() {
child[a].push(b);
child[b].push(a);
}
let mut parent = vec![size; size];
let mut q = Vec::with_capacity(size);
q.push(root);
parent[root] = root;
for i in 0..size {
let v = q[i];
for u in child[v].clone() {
assert!(parent[u] == size);
parent[u] = v;
child[u].retain(|e| *e != v);
q.push(u);
}
}
let mut sum = vec![1; size];
for &v in q.iter().rev() {
let child = &mut child[v];
if !child.is_empty() {
let (pos, _) = child.iter().enumerate().max_by_key(|p| sum[*p.1]).unwrap();
child.swap(0, pos);
sum[v] = 1 + child.iter().fold(0, |s, a| s + sum[*a]);
}
}
let mut path_root = (0..size).collect::<Vec<_>>();
let mut left = vec![0; size];
let mut right = vec![0; size];
let mut dfs = vec![(root, false)];
let mut id = 0;
while let Some((v, end)) = dfs.pop() {
if end {
right[v] = id;
continue;
}
left[v] = id;
id += 1;
dfs.push((v, true));
let child = &child[v];
if !child.is_empty() {
for &u in child[1..].iter() {
path_root[u] = u;
dfs.push((u, false));
}
let u = child[0];
path_root[u] = path_root[v];
dfs.push((u, false));
}
}
let mut inverse = vec![size; size];
for (i, l) in left.iter().enumerate() {
inverse[*l] = i;
}
self.child = child;
self.parent = parent;
self.left = left;
self.right = right;
self.path_root = path_root;
self.inverse = inverse;
}
pub fn lca(&self, mut a: usize, mut b: usize) -> usize {
assert!(a < self.size && b < self.size);
let path = &self.path_root;
let parent = &self.parent;
let index = &self.left;
while path[a] != path[b] {
if index[a] > index[b] {
std::mem::swap(&mut a, &mut b);
}
b = parent[path[b]];
}
std::cmp::min((index[a], a), (index[b], b)).1
}
pub fn path(
&self,
src: usize,
dst: usize,
up: &mut Vec<(usize, usize)>,
down: &mut Vec<(usize, usize)>,
) {
assert!(src < self.size && dst < self.size);
up.clear();
down.clear();
let path = &self.path_root;
let parent = &self.parent;
let index = &self.left;
let mut x = src;
let mut y = dst;
while path[x] != path[y] {
if index[x] > index[y] {
let p = path[x];
assert!(p == path[p]);
up.push((index[p], index[x] + 1));
x = parent[p];
} else {
let p = path[y];
assert!(p == path[p]);
down.push((index[p], index[y] + 1));
y = parent[p];
}
}
if index[x] <= index[y] {
down.push((index[x], index[y] + 1));
} else {
up.push((index[y], index[x] + 1));
}
down.reverse();
}
pub fn sub_tree(&self, v: usize) -> (usize, usize) {
assert!(v < self.size);
(self.left[v], self.right[v])
}
pub fn parent(&self, v: usize) -> Option<usize> {
assert!(v < self.size);
let p = self.parent[v];
if p == v {
None
} else {
Some(p)
}
}
// s -> t へのパスの2番目の頂点を返す
pub fn next(&self, s: usize, t: usize) -> usize {
assert!(s < self.size && t < self.size && s != t);
let (a, b) = self.sub_tree(s);
let (c, d) = self.sub_tree(t);
if !(a <= c && d <= b) {
return self.parent[s];
}
let mut pos = t;
let mut pre = t;
while self.path_root[s] != self.path_root[pos] {
pre = self.path_root[pos];
pos = self.parent[pre];
}
if s == pos {
pre
} else {
self.child[s][0]
}
}
pub fn vertex(&self, x: usize) -> usize {
assert!(x < self.size);
self.inverse[x]
}
pub fn jump(
&self,
s: usize,
t: usize,
mut k: usize,
up: &mut Vec<(usize, usize)>,
down: &mut Vec<(usize, usize)>,
) -> Option<usize> {
assert!(s.max(t) < self.size);
self.path(s, t, up, down);
for (l, r) in up.drain(..) {
if k < r - l {
return Some(self.vertex(r - 1 - k));
}
k -= r - l;
}
for (l, r) in down.drain(..) {
if k < r - l {
return Some(self.vertex(l + k));
}
k -= r - l;
}
None
}
}
// ---------- end Heavy-Light decomposition ----------
// ---------- begin segment tree Point Update Range Query ----------
pub struct SegmentTreePURQ<T, F> {
n: usize,
size: usize,
data: Vec<T>,
e: T,
op: F,
}
impl<T, F> SegmentTreePURQ<T, F>
where
T: Clone,
F: Fn(&T, &T) -> T,
{
pub fn new(n: usize, e: T, op: F) -> Self {
assert!(n > 0);
let size = n.next_power_of_two();
let data = vec![e.clone(); 2 * size];
SegmentTreePURQ {
n,
size,
data,
e,
op,
}
}
pub fn update_tmp(&mut self, x: usize, v: T) {
assert!(x < self.n);
self.data[x + self.size] = v;
}
pub fn update_all(&mut self) {
for i in (1..self.size).rev() {
self.data[i] = (self.op)(&self.data[2 * i], &self.data[2 * i + 1]);
}
}
pub fn update(&mut self, x: usize, v: T) {
assert!(x < self.n);
let mut x = x + self.size;
self.data[x] = v;
x >>= 1;
while x > 0 {
self.data[x] = (self.op)(&self.data[2 * x], &self.data[2 * x + 1]);
x >>= 1;
}
}
pub fn find(&self, l: usize, r: usize) -> T {
assert!(l <= r && r <= self.n);
if l == r {
return self.e.clone();
}
let mut l = self.size + l;
let mut r = self.size + r;
let mut x = self.e.clone();
let mut y = self.e.clone();
while l < r {
if l & 1 == 1 {
x = (self.op)(&x, &self.data[l]);
l += 1;
}
if r & 1 == 1 {
r -= 1;
y = (self.op)(&self.data[r], &y);
}
l >>= 1;
r >>= 1;
}
(self.op)(&x, &y)
}
pub fn max_right<P>(&self, l: usize, f: P) -> usize
where
P: Fn(&T) -> bool,
{
assert!(l <= self.n);
assert!(f(&self.e));
if l == self.n {
return self.n;
}
let mut l = l + self.size;
let mut sum = self.e.clone();
while {
l >>= l.trailing_zeros();
let v = (self.op)(&sum, &self.data[l]);
if !f(&v) {
while l < self.size {
l <<= 1;
let v = (self.op)(&sum, &self.data[l]);
if f(&v) {
sum = v;
l += 1;
}
}
return l - self.size;
}
sum = v;
l += 1;
l.count_ones() > 1
} {}
self.n
}
pub fn min_left<P>(&self, r: usize, f: P) -> usize
where
P: Fn(&T) -> bool,
{
assert!(r <= self.n);
assert!(f(&self.e));
if r == 0 {
return 0;
}
let mut r = r + self.size;
let mut sum = self.e.clone();
while {
r -= 1;
while r > 1 && r & 1 == 1 {
r >>= 1;
}
let v = (self.op)(&self.data[r], &sum);
if !f(&v) {
while r < self.size {
r = 2 * r + 1;
let v = (self.op)(&self.data[r], &sum);
if f(&v) {
sum = v;
r -= 1;
}
}
return r + 1 - self.size;
}
sum = v;
(r & (!r + 1)) != r
} {}
0
}
}
// ---------- end segment tree Point Update Range Query ----------
// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
use std::str::FromStr;
pub struct Scanner<'a> {
it: std::str::SplitWhitespace<'a>,
}
impl<'a> Scanner<'a> {
pub fn new(s: &'a String) -> Scanner<'a> {
Scanner {
it: s.split_whitespace(),
}
}
pub fn next<T: FromStr>(&mut self) -> T {
self.it.next().unwrap().parse::<T>().ok().unwrap()
}
pub fn next_bytes(&mut self) -> Vec<u8> {
self.it.next().unwrap().bytes().collect()
}
pub fn next_chars(&mut self) -> Vec<char> {
self.it.next().unwrap().chars().collect()
}
pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
(0..len).map(|_| self.next()).collect()
}
}
}
// ---------- end scannner ----------
use std::collections::*;
use std::io::Write;
type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;
fn main() {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
let mut sc = scanner::Scanner::new(&s);
let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
run(&mut sc, &mut out);
}
type M = ModInt<998244353>;
fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
let n: usize = sc.next();
let q: usize = sc.next();
let mut leaf = vec![true; n];
let mut left = vec![true; n];
let mut val = vec![[M::zero(); 3]; n];
let mut hld = HLD::new(n);
for i in 0..n {
let c = sc.next::<String>();
if c == "x" {
let l = sc.next::<usize>() - 1;
let r = sc.next::<usize>() - 1;
hld.add_edge(i, l);
hld.add_edge(i, r);
left[r] = false;
leaf[i] = false;
} else {
let x = M::new(sc.next::<u32>());
let y = M::new(sc.next::<u32>());
let z = M::new(sc.next::<u32>());
val[i] = [x, y, z];
}
}
hld.build(0);
let hld = hld;
let mut under = vec![n; n];
for i in 0..n {
if leaf[i] {
under[hld.path_root[i]] = i;
}
}
let under = under;
type Mat = [[M; 3]; 3];
let mul = |a: &Mat, b: &Mat| -> Mat {
let mut c = [[M::zero(); 3]; 3];
for (c, a) in c.iter_mut().zip(a.iter()) {
for (a, b) in a.iter().zip(b.iter()) {
for (c, b) in c.iter_mut().zip(b.iter()) {
*c += *a * *b;
}
}
}
c
};
let gen_leaf = |p: [M; 3]| -> Mat {
let mut mat = [[M::zero(); 3]; 3];
for (mat, v) in mat.iter_mut().zip(p.iter()) {
mat[0] = *v;
}
mat
};
let gen = |p: Mat, left: bool| -> Mat {
let v = [p[0][0], p[1][0], p[2][0]];
let mut res = [[M::zero(); 3]; 3];
res[0][1] = -v[2];
res[1][0] = v[2];
res[2][0] = -v[1];
res[0][2] = v[1];
res[2][1] = v[0];
res[1][2] = -v[0];
if !left {
for res in res.iter_mut().flatten() {
*res = -*res;
}
}
res
};
let mut e = [[M::zero(); 3]; 3];
for i in 0..3 {
e[i][i] = M::one();
}
let mut seg = SegmentTreePURQ::new(n, e, mul);
for i in (0..n).rev() {
let v = hld.vertex(i);
if leaf[v] {
let val = val[v];
seg.update(i, gen_leaf(val));
}
if i > 0 && v == hld.path_root[v] {
let r = hld.sub_tree(under[v]).1;
let m = seg.find(i, r);
let mat = gen(m, left[v]);
let p = hld.parent[v];
let pos = hld.sub_tree(p).0;
seg.update(pos, mat);
}
}
for _ in 0..q {
let v = sc.next::<usize>() - 1;
let x = M::new(sc.next::<u32>());
let y = M::new(sc.next::<u32>());
let z = M::new(sc.next::<u32>());
val[v] = [x, y, z];
seg.update(hld.sub_tree(v).0, gen_leaf(val[v]));
let mut pos = hld.path_root[v];
while pos > 0 {
let l = hld.sub_tree(pos).0;
let r = hld.sub_tree(under[pos]).1;
let m = seg.find(l, r);
let mat = gen(m, left[v]);
let p = hld.parent[pos];
assert!(pos != p);
let x = hld.sub_tree(p).0;
seg.update(x, mat);
let next = hld.path_root[p];
assert!(next != pos);
pos = next;
}
let r = hld.sub_tree(under[0]).1;
let ans = seg.find(0, r);
writeln!(out, "{} {} {}", ans[0][0], ans[1][0], ans[2][0]).ok();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 2032kb
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: -100
Wrong Answer
time: 1223ms
memory: 55404kb
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:
605123795 224477738 610947005 238284787 16469853 870231856 294611811 980011608 533642029 404379574 745296852 53493560 593678852 169374593 920223197 405749495 350493049 116816620 190018467 515243135 518180555 370063853 488259799 740814218 13737245 352087791 917410487 932051309 366591227 479931477 199...
result:
wrong answer 1st numbers differ by non-multiple of MOD, - expected: '393120558', found: '605123795'