結果
| 問題 |
No.3346 Tree to DAG
|
| コンテスト | |
| ユーザー |
 akakimidori
|
| 提出日時 | 2025-11-15 11:36:23 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 117 ms / 2,000 ms |
| コード長 | 27,527 bytes |
| コンパイル時間 | 12,831 ms |
| コンパイル使用メモリ | 404,964 KB |
| 実行使用メモリ | 15,960 KB |
| 最終ジャッジ日時 | 2025-11-15 11:36:42 |
| 合計ジャッジ時間 | 16,948 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 39 |
コンパイルメッセージ
warning: unused import: `std::io::Write`
--> src/main.rs:39:5
|
39 | use std::io::Write;
| ^^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused variable: `v`
--> src/main.rs:91:24
|
91 | fn init(&mut self, v: usize) -> Self::Value {
| ^ help: if this is intentional, prefix it with an underscore: `_v`
|
= note: `#[warn(unused_variables)]` on by default
warning: unused variable: `e`
--> src/main.rs:96:59
|
96 | fn merge(&mut self, p: &Self::Value, c: &Self::Value, e: &Self::Edge) -> Self::Value {
| ^ help: if this is intentional, prefix it with an underscore: `_e`
warning: type alias `Map` is never used
--> src/main.rs:41:6
|
41 | type Map<K, V> = BTreeMap<K, V>;
| ^^^
|
= note: `#[warn(dead_code)]` on by default
warning: type alias `Set` is never used
--> src/main.rs:42:6
|
42 | type Set<T> = BTreeSet<T>;
| ^^^
warning: type alias `Deque` is never used
--> src/main.rs:43:6
|
43 | type Deque<T> = VecDeque<T>;
| ^^^^^
ソースコード
// DAGの個数の最大値
// サイクルについて包除で個数を考えてみる
// 確率を考える
// p=1/2 とする
//
// 1. 1つのパス上にある時
// A, B という距離でとってきた時
// 1
// - p^(A+2-1) - p^(B+2-1) - p^(A+B+2-1)
// + 3 * p^(A+B+3-1)
// - 0
//
// 2. 三叉路
// A, B, C
// 1
// - p^(A+B+2-1) - p^(B+C+2-1) - p^(C+A+2-1)
// + 3 p^(A+B+C+3-1)
// - 0
//
// どっちも距離が大きい方がいい
// 各頂点から遠い頂点のtop3 を計算する
// 三叉路取れる時はそっちで、そうでない次数2については上の値を出す
// 最大値を取る
// と言いたいが桁数が大きすぎる
// +と-が混在しているのが厄介で、どうするか
//
// sum_{0<=i}x_i * p^i
// |x_i| <= 1
// という形にする
// 非ゼロ項が少ないことを活かす
// -2 < sum_i x_i p^i < 2
// となるので差分を管理して前から足し引き, 2倍という手順を踏んでいく
// 差が4以上になると確定するのでそれをやればいい
//
// いや|x| の最大値をVとして
// (-2V, 2V) となるので4Vで判定とかの方がいいか？
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() {
input! {
n: usize,
e: [(usize1, usize1); n - 1],
}
let mut solver = Rerooting::new(n, R);
for (a, b) in e {
solver.add_edge(a, b, ());
}
let dp = solver.solve();
let mut ans = Data::new(vec![]);
for dp in dp {
if dp[1] <= 0 {
continue;
}
let mut x = vec![(0, 1)];
if dp[2] > 0 {
for i in 0..3 {
x.push((dp[i] + dp[(i + 1) % 3] + 2 - 1, -1));
x.push((dp[0] + dp[1] + dp[2] + 3 - 1, 1));
}
} else {
let (a, b) = (dp[0], dp[1]);
x.push((a + 2 - 1, -1));
x.push((b + 2 - 1, -1));
x.push((a + b + 2 - 1, -1));
x.push((a + b + 3 - 1, 3));
}
let x = Data::new(x);
ans = ans.max(x);
}
let mut base = M::zero();
for &(x, v) in ans.data.iter() {
let p = M::new(2).inv().pow(x as u64);
base += M::from(v as i64) * p;
}
base *= M::new(2).pow(n as u64 + 2);
println!("{}", base);
}
type M = ModInt<998244353>;
struct R;
impl RerootingOperator for R {
type Value = TopK<i32, 3>;
type Edge = ();
fn init(&mut self, v: usize) -> Self::Value {
let mut res = Self::Value::new([std::i32::MIN / 2; 3]);
res.update(0);
res
}
fn merge(&mut self, p: &Self::Value, c: &Self::Value, e: &Self::Edge) -> Self::Value {
let mut p = p.clone();
p.update(c[0] + 1);
p
}
}
// 場所、値
#[derive(Clone)]
pub struct Data {
data: Vec<(i32, i32)>,
max: i32,
}
impl Data {
pub fn new(mut x: Vec<(i32, i32)>) -> Self {
x.sort();
x.dedup_by(|a, b| a.0 == b.0 && {
b.1 += a.1;
true
});
x.retain(|p| p.1 != 0);
let m = x.iter().map(|p| p.1.abs()).max().unwrap_or(0);
Self {
data: x,
max: m,
}
}
}
impl Ord for Data {
fn cmp(&self, rhs: &Self) -> std::cmp::Ordering {
let mut val = 0i32;
let mut x = std::i32::MIN;
let mut y = 0;
let mut z = 0;
let d = self.max + rhs.max;
while y < self.data.len() || z < rhs.data.len() {
let p = self.data.get(y).cloned();
let q = rhs.data.get(z).cloned();
let nx = if let (Some(p), Some(q)) = (p, q) {
p.0.min(q.0)
} else {
p.or(q).unwrap().0
};
val *= 1 << 2.min(nx.saturating_sub(x));
if val.abs() >= 4 * d {
break;
}
if let Some(p) = p {
if p.0 == nx {
val += p.1;
y += 1;
}
}
if let Some(p) = q {
if p.0 == nx {
val -= p.1;
z += 1;
}
}
x = nx + 1;
val *= 2;
}
val.cmp(&0)
}
}
impl PartialOrd for Data {
fn partial_cmp(&self, rhs: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(rhs))
}
}
impl PartialEq for Data {
fn eq(&self, rhs: &Self) -> bool {
self.cmp(rhs) == std::cmp::Ordering::Equal
}
}
impl Eq for Data {}
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
#[macro_export]
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
#[macro_export]
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, bytes) => {
read_value!($iter, String).bytes().collect::<Vec<u8>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
// ---------- end input macro ----------
// ---------- 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)
}
}
impl<const M: u32> From<i64> for ModInt<{ M }> {
fn from(val: i64) -> ModInt<{ M }> {
ModInt::new(val.rem_euclid(M as i64) 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
}
}
// ---------- 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 trait ----------
use std::ops::*;
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 Group: Zero + Sub<Output = Self> + Neg<Output = Self> {}
pub trait SemiRing: Zero + One {}
pub trait Ring: SemiRing + Group {}
pub trait Field: Ring + Div<Output = Self> {}
impl<T> Group for T where T: Zero + Sub<Output = Self> + Neg<Output = Self> {}
impl<T> SemiRing for T where T: Zero + One {}
impl<T> Ring for T where T: SemiRing + Group {}
impl<T> Field for T where T: Ring + Div<Output = Self> {}
pub fn zero<T: Zero>() -> T {
T::zero()
}
pub fn one<T: One>() -> T {
T::one()
}
pub fn pow<T: One + Clone>(mut r: T, mut n: usize) -> T {
let mut t = one();
while n > 0 {
if n & 1 == 1 {
t = t * r.clone();
}
r = r.clone() * r;
n >>= 1;
}
t
}
pub fn pow_sum<T: SemiRing + Clone>(mut r: T, mut n: usize) -> T {
let mut ans = T::zero();
let mut sum = T::one();
while n > 0 {
if n & 1 == 1 {
ans = ans * r.clone() + sum.clone();
}
sum = sum * (T::one() + r.clone());
r = r.clone() * r;
n >>= 1;
}
ans
}
// ---------- end trait ----------
// ---------- begin Rerooting ----------
pub trait RerootingOperator {
type Value: Clone;
type Edge: Clone;
fn init(&mut self, v: usize) -> Self::Value;
fn merge(&mut self, p: &Self::Value, c: &Self::Value, e: &Self::Edge) -> Self::Value;
}
pub struct Rerooting<R: RerootingOperator> {
manager: R,
size: usize,
edge: Vec<(usize, usize, R::Edge, R::Edge)>,
}
impl<R: RerootingOperator> Rerooting<R> {
pub fn new(size: usize, manager: R) -> Self {
assert!(size > 0 && size < 10usize.pow(8));
Rerooting {
manager: manager,
size: size,
edge: vec![],
}
}
pub fn add_edge(&mut self, a: usize, b: usize, cost: R::Edge) {
assert!(a < self.size && b < self.size && a != b);
self.add_edge_bi(a, b, cost.clone(), cost);
}
pub fn add_edge_bi(&mut self, a: usize, b: usize, ab: R::Edge, ba: R::Edge) {
assert!(a < self.size && b < self.size && a != b);
self.edge.push((a, b, ab, ba));
}
pub fn solve(&mut self) -> Vec<R::Value> {
let size = self.size;
let mut graph = vec![vec![]; size];
for e in self.edge.iter() {
graph[e.0].push((e.1, e.2.clone()));
graph[e.1].push((e.0, e.3.clone()));
}
let root = 0;
let mut topo = vec![root];
let mut parent = vec![root; size];
let mut parent_edge: Vec<Option<R::Edge>> = (0..size).map(|_| None).collect();
for i in 0..size {
let v = topo[i];
let child = std::mem::take(&mut graph[v]);
for e in child.iter() {
let k = graph[e.0].iter().position(|e| e.0 == v).unwrap();
let c = graph[e.0].remove(k).1;
parent_edge[e.0] = Some(c);
parent[e.0] = v;
topo.push(e.0);
}
graph[v] = child;
}
let manager = &mut self.manager;
let mut down: Vec<_> = (0..size).map(|v| manager.init(v)).collect();
for &v in topo.iter().rev() {
for e in graph[v].iter() {
down[v] = manager.merge(&down[v], &down[e.0], &e.1);
}
}
let mut up: Vec<_> = (0..size).map(|v| manager.init(v)).collect();
let mut stack = vec![];
for &v in topo.iter() {
if let Some(e) = parent_edge[v].take() {
let ini = manager.init(v);
up[v] = manager.merge(&ini, &up[v], &e);
}
if !graph[v].is_empty() {
stack.push((graph[v].as_slice(), up[v].clone()));
while let Some((g, val)) = stack.pop() {
if g.len() == 1 {
up[g[0].0] = val;
} else {
let m = g.len() / 2;
let (a, b) = g.split_at(m);
for a in [(a, b), (b, a)].iter() {
let mut p = val.clone();
for a in a.0.iter() {
p = manager.merge(&p, &down[a.0], &a.1);
}
stack.push((a.1, p));
}
}
}
}
for e in graph[v].iter() {
up[v] = manager.merge(&up[v], &down[e.0], &e.1);
}
}
up
}
}
// ---------- end Rerooting ----------
// 大きいやつN個を管理する
// ---------- begin top-k ----------
#[derive(Clone, Debug)]
pub struct TopK<T, const N: usize>([T; N]);
impl<T, const N: usize> TopK<T, N>
where
T: Ord + Copy,
{
pub fn new(a: [T; N]) -> Self {
assert!(a.windows(2).all(|a| a[0] >= a[1]));
Self(a)
}
pub fn update(&mut self, v: T) {
for i in 0..N {
if v >= self.0[i] {
self.0[i..].rotate_right(1);
self.0[i] = v;
return;
}
}
}
pub fn merge(&self, rhs: &Self) -> Self {
let mut res = self.0;
let mut i = 0;
let mut j = 0;
for res in res.iter_mut() {
if self.0[i] >= rhs.0[j] {
*res = self.0[i];
i += 1;
} else {
*res = rhs.0[j];
j += 1;
}
}
Self::new(res)
}
}
impl<T, const N: usize> std::ops::Index<usize> for TopK<T, N> {
type Output = T;
fn index(&self, x: usize) -> &Self::Output {
&self.0[x]
}
}
// ---------- end top-k ----------