結果
| 問題 | No.235 めぐるはめぐる (5) |
| ユーザー |
 ngtkana
|
| 提出日時 | 2024-06-24 13:24:30 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 3,503 ms / 10,000 ms |
| コード長 | 56,023 bytes |
| コンパイル時間 | 14,400 ms |
| コンパイル使用メモリ | 387,600 KB |
| 実行使用メモリ | 60,020 KB |
| 最終ジャッジ日時 | 2024-06-24 13:24:59 |
| 合計ジャッジ時間 | 28,392 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 3,503 ms
59,128 KB |
| testcase_01 | AC | 2,274 ms
60,020 KB |
| testcase_02 | AC | 3,292 ms
59,368 KB |
コンパイルメッセージ
warning: unused import: `factorial::Factorial`
--> src/main.rs:870:13
|
870 | pub use factorial::Factorial;
| ^^^^^^^^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused import: `fourier::any_mod_fps_mul`
--> src/main.rs:871:13
|
871 | pub use fourier::any_mod_fps_mul;
| ^^^^^^^^^^^^^^^^^^^^^^^^
warning: unused import: `fourier::fft`
--> src/main.rs:872:13
|
872 | pub use fourier::fft;
| ^^^^^^^^^^^^
warning: unused import: `fourier::fps_mul`
--> src/main.rs:873:13
|
873 | pub use fourier::fps_mul;
| ^^^^^^^^^^^^^^^^
warning: unused import: `fourier::ifft`
--> src/main.rs:874:13
|
874 | pub use fourier::ifft;
| ^^^^^^^^^^^^^
ソースコード
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::<O>::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<usize>,
pub index: Vec<usize>,
pub head: Vec<usize>,
}
impl Hld {
pub fn from_short_parents(mut parent: Vec<usize>) -> (Self, Vec<Vec<usize>>) {
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<Vec<usize>>) {
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<usize>], parent: Vec<usize>) -> 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<usize>],
head: &mut [usize],
index: &mut [usize],
current: &mut std::ops::RangeFrom<usize>,
) {
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>]) -> 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<usize>]) -> Vec<usize> {
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<O: OpBase> {
nodes: Vec<Node<O>>,
}
impl<O: OpBase> LinkCutTreeBase<O> {
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<Item = O::Value>) -> 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<usize> {
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<usize> {
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<O::Value> {
if !self.undirected_is_connected(i, j) {
return None;
}
self.evert(i);
Some(self.fold(j))
}
pub fn parent(&mut self, x: usize) -> Option<usize> {
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<O: OpBase> {
id: usize,
parent: *mut Self,
left: *mut Self,
right: *mut Self,
rev: bool,
value: O::InternalValue,
acc: O::InternalValue,
}
unsafe fn is_splay_root<O: OpBase>(x: *mut Node<O>) -> 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<O: OpBase>(x: *mut Node<O>) {
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<O: OpBase>(x: *mut Node<O>) {
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<O: OpBase>(x: *mut Node<O>) {
let x = &mut *x;
std::mem::swap(&mut x.left, &mut x.right);
O::rev(&mut x.acc);
x.rev ^= true;
}
unsafe fn expose<O: OpBase>(x: *mut Node<O>) -> *mut Node<O> {
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<O: OpBase>(x: *mut Node<O>) {
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<O: OpBase>(l: *mut Node<O>) {
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<O: OpBase>(r: *mut Node<O>) {
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<T> = LinkCutTreeBase<Commut<T>>;
#[doc(hidden)]
pub struct Commut<T: Op>(T);
impl<T: Op> OpBase for Commut<T> {
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: Op>(T);
pub type NonCommutLinkCutTree<T> = LinkCutTreeBase<NonCommut<T>>;
impl<T: Op> OpBase for NonCommut<T> {
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<const P: u64>(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<const P: u64> {
fact: Vec<Fp<P>>,
inv_fact: Vec<Fp<P>>,
}
impl<const P: u64> Factorial<P> {
pub fn new(length: usize) -> Self {
let mut fact = vec![Fp::<P>::new(1); length + 1];
let mut inv_fact = vec![Fp::<P>::new(1); length + 1];
for i in 1..=length {
fact[i] = fact[i - 1] * Fp::<P>::new(i as u64);
}
inv_fact[length] = fact[length].inv();
for i in (1..=length).rev() {
inv_fact[i - 1] = inv_fact[i] * Fp::<P>::new(i as u64);
}
Self { fact, inv_fact }
}
pub fn fact(&self, n: usize) -> Fp<P> {
self.fact[n]
}
pub fn inv_fact(&self, n: usize) -> Fp<P> {
self.inv_fact[n]
}
pub fn perm(&self, n: usize, k: usize) -> Fp<P> {
self.fact[n] * self.inv_fact[n - k]
}
pub fn comb(&self, n: usize, k: usize) -> Fp<P> {
self.fact[n] * self.inv_fact[n - k] * self.inv_fact[k]
}
pub fn binom(&self, n: usize, k: usize) -> Fp<P> {
self.comb(n, k)
}
pub fn comb_or_zero(&self, n: usize, k: isize) -> Fp<P> {
if k < 0 || k as usize > n {
Fp::<P>::new(0)
} else {
self.comb(n, k as usize)
}
}
pub fn comb_with_reputation(&self, n: usize, k: usize) -> Fp<P> {
assert!(n > 0 || k > 0);
self.comb(n + k - 1, k)
}
}
impl<const P: u64> Index<usize> for Factorial<P> {
type Output = Fp<P>;
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<P1>;
type F2 = Fp<P2>;
type F3 = Fp<P3>;
pub fn fps_mul<const P: u64>(a: impl AsRef<[Fp<P>]>, b: impl AsRef<[Fp<P>]>) -> Vec<Fp<P>>
where
(): PrimitiveRoot<P>,
{
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<const P: u64>(a: &[Fp<P>], b: &[Fp<P>]) -> Vec<Fp<P>> {
let v1 = fps_mul(
a.iter().map(|&x| F1::new(x.value())).collect::<Vec<_>>(),
b.iter().map(|&x| F1::new(x.value())).collect::<Vec<_>>(),
);
let v2 = fps_mul(
a.iter().map(|&x| F2::new(x.value())).collect::<Vec<_>>(),
b.iter().map(|&x| F2::new(x.value())).collect::<Vec<_>>(),
);
let v3 = fps_mul(
a.iter().map(|&x| F3::new(x.value())).collect::<Vec<_>>(),
b.iter().map(|&x| F3::new(x.value())).collect::<Vec<_>>(),
);
v1.into_iter()
.zip(v2)
.zip(v3)
.map(|((e1, e2), e3)| garner(e1, e2, e3))
.collect::<Vec<_>>()
}
pub fn fft<const P: u64>(f: &mut [Fp<P>])
where
(): PrimitiveRoot<P>,
{
let n = f.len();
assert!(n.is_power_of_two());
assert!((P - 1) % n as u64 == 0);
let mut root = <() as PrimitiveRoot<P>>::VALUE.pow((P - 1) / f.len() as u64);
let fourth = <() as PrimitiveRoot<P>>::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<const P: u64>(f: &mut [Fp<P>])
where
(): PrimitiveRoot<P>,
{
let n = f.len();
assert!(n.is_power_of_two());
let root = <() as PrimitiveRoot<P>>::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::<Vec<_>>();
roots.reverse();
let fourth = <() as PrimitiveRoot<P>>::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<const P: u64>(x1: Fp<P1>, x2: Fp<P2>, x3: Fp<P3>) -> Fp<P> {
let (x1, x2, x3) = (x1.value(), x2.value(), x3.value());
let x2 = ((x2 + (P2 - x1)) * mod_inv::<P2>(P1)) % P2;
let x3 =
(((x3 + (P3 - x1)) * mod_inv::<P3>(P1) % P3 + (P3 - x2)) * mod_inv::<P3>(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 P: u64> {
const VALUE: Fp<P>;
}
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<const P: u64> {
value: u64,
}
impl<const P: u64> Fp<P> {
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::<P>(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<const P: u64> std::fmt::Debug for Fp<P> {
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<const P: u64> std::fmt::Display for Fp<P> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{}", self.value())
}
}
macro_rules! impl_from_signed {
($($t:ty),*) => {
$(
impl<const P: u64> From<$t> for Fp<P> {
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<const P: u64> From<$t> for Fp<P> {
fn from(x: $t) -> Self { Self::new(x as u64) }
}
)*
};
}
impl_from_unsigned!(u8, u16, u32, u64, u128, usize);
impl<const P: u64> AddAssign<Fp<P>> for Fp<P> {
fn add_assign(&mut self, rhs: Fp<P>) {
self.value += rhs.value;
if self.value >= P {
self.value -= P;
}
}
}
impl<const P: u64> SubAssign<Fp<P>> for Fp<P> {
fn sub_assign(&mut self, rhs: Fp<P>) {
if self.value < rhs.value {
self.value += P;
}
self.value -= rhs.value;
}
}
impl<const P: u64> MulAssign<Fp<P>> for Fp<P> {
fn mul_assign(&mut self, rhs: Fp<P>) {
self.value = self.value * rhs.value % P;
}
}
#[allow(clippy::suspicious_op_assign_impl)]
impl<const P: u64> DivAssign<Fp<P>> for Fp<P> {
fn div_assign(&mut self, rhs: Fp<P>) {
*self *= rhs.inv()
}
}
macro_rules! fp_forward_ops {
($(
$trait:ident,
$trait_assign:ident,
$fn:ident,
$fn_assign:ident,
)*) => {$(
impl<const P: u64> $trait_assign<&Fp<P>> for Fp<P> {
fn $fn_assign(&mut self, rhs: &Fp<P>) {
self.$fn_assign(*rhs);
}
}
impl<const P: u64, T: Into<Fp<P>>> $trait<T> for Fp<P> {
type Output = Fp<P>;
fn $fn(mut self, rhs: T) -> Self::Output {
self.$fn_assign(rhs.into());
self
}
}
impl<const P: u64> $trait<&Fp<P>> for Fp<P> {
type Output = Fp<P>;
fn $fn(self, rhs: &Fp<P>) -> Self::Output {
self.$fn(*rhs)
}
}
impl<const P: u64, T: Into<Fp<P>>> $trait<T> for &Fp<P> {
type Output = Fp<P>;
fn $fn(self, rhs: T) -> Self::Output {
(*self).$fn(rhs.into())
}
}
impl<const P: u64> $trait<&Fp<P>> for &Fp<P> {
type Output = Fp<P>;
fn $fn(self, rhs: &Fp<P>) -> 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<const P: u64> Neg for Fp<P> {
type Output = Fp<P>;
fn neg(mut self) -> Self::Output {
if self.value > 0 {
self.value = P - self.value;
}
self
}
}
impl<const P: u64> Sum for Fp<P> {
fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.fold(Self::new(0), |acc, x| acc + x)
}
}
impl<'a, const P: u64> Sum<&'a Self> for Fp<P> {
fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
iter.copied().sum()
}
}
impl<const P: u64> Product for Fp<P> {
fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.fold(Self::new(1), |acc, x| acc * x)
}
}
impl<'a, const P: u64> Product<&'a Self> for Fp<P> {
fn product<I: Iterator<Item = &'a Self>>(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<O: LazyOps>(root: *mut Node<O>) {
if !root.is_null() {
unsafe {
deep_free((*root).left);
deep_free((*root).right);
Box::from_raw(root);
}
}
}
pub fn access_index<O: LazyOps>(mut root: &mut Node<O>, mut i: usize) -> &mut Node<O> {
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<O: LazyOps>(left: *mut Node<O>, right: *mut Node<O>) -> *mut Node<O> {
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<O: LazyOps>(root: *mut Node<O>, at: usize) -> [*mut Node<O>; 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<O: LazyOps> {
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<O::Lazy>,
}
impl<O: LazyOps> Node<O> {
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<T: Sized + Debug + Clone> Value for T {}
pub struct Nop<T: Value>(PhantomData<fn(T) -> T>);
impl<T: Value> LazyOps for Nop<T> {
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<O>(PhantomData<fn(O) -> O>);
impl<O: Ops> LazyOps for NoLazy<O> {
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<Self::Lazy>) {
match lower {
None => *lower = Some(upper.clone()),
Some(lower) => Self::compose(upper, lower),
}
}
}
pub struct SplayTree<O: LazyOps>(Cell<*mut Node<O>>);
impl<O: LazyOps> SplayTree<O> {
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<usize>) {
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<usize>) -> Option<O::Acc> {
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<usize>, 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<Entry<'_, O>> {
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<usize>) -> 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<O: LazyOps> FromIterator<O::Value> for SplayTree<O> {
fn from_iter<T: IntoIterator<Item = O::Value>>(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<O> {
type IntoIter = Iter<'a, O>;
type Item = &'a O::Value;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<O: LazyOps> Debug for SplayTree<O> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_list().entries(self.iter()).finish()
}
}
impl<O: LazyOps> Clone for SplayTree<O> {
fn clone(&self) -> Self {
self.iter().cloned().collect()
}
}
impl<O: LazyOps> Default for SplayTree<O> {
fn default() -> Self {
Self(Cell::new(null_mut()))
}
}
impl<O: LazyOps> PartialEq for SplayTree<O>
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<O: LazyOps> Eq for SplayTree<O> where O::Value: Eq {}
impl<O: LazyOps> PartialOrd for SplayTree<O>
where
O::Value: PartialOrd,
{
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
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<O: LazyOps> Ord for SplayTree<O>
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<O: LazyOps> Hash for SplayTree<O>
where
O::Value: Hash,
{
fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
self.iter().for_each(|x| x.hash(state))
}
}
impl<O: LazyOps> Index<usize> for SplayTree<O> {
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<O>,
start: usize,
end: usize,
}
impl<'a, O: LazyOps> Iterator for Iter<'a, O> {
type Item = &'a O::Value;
fn next(&mut self) -> Option<Self::Item> {
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<Self::Item> {
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<O>);
impl<O: LazyOps> Deref for Entry<'_, O> {
type Target = O::Value;
fn deref(&self) -> &Self::Target {
&unsafe { &*self.0 .0.get() }.value
}
}
impl<O: LazyOps> DerefMut for Entry<'_, O> {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut unsafe { &mut *self.0 .0.get() }.value
}
}
impl<O: LazyOps> Drop for SplayTree<O> {
fn drop(&mut self) {
deep_free(self.0.get());
}
}
fn into_range(len: usize, range: impl RangeBounds<usize>) -> Range<usize> {
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);
}
}
// }}}