QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190548#6161. 作业题Qingyu100 ✓223ms3328kbRust11.3kb2023-09-29 03:56:562023-09-29 03:56:57

Judging History

你现在查看的是最新测评结果

  • [2023-09-29 03:56:57]
  • 评测
  • 测评结果:100
  • 用时:223ms
  • 内存:3328kb
  • [2023-09-29 03:56:56]
  • 提交

answer

// N 頂点M辺のグラフが与えられる
// 辺には重みw_iが割り振られている
// 全域木の重みを (重みの和) * (重みのgcd) と定義する
// 全ての全域木についての重みの和を求めて
// mod 998244353
//
// 2 <= N <= 30
// 1 <= w_i <= 152501
// 多重辺、自己ループ無し

fn main() {
    let (n, e) = read();
    let m = e.iter().map(|e| e.2).max().unwrap();
    let mut phi = (0..=m).collect::<Vec<_>>();
    for i in 2..=m {
        if i == phi[i] {
            for j in (1..=(m / i)).rev() {
                phi[j * i] -= phi[j];
            }
        }
    }
    let mut ans = M::zero();
    for (i, phi) in phi.iter().enumerate().skip(1) {
        let mut cnt = 0;
        let mut mat = vec![vec![Dual::new(M::zero(), M::zero()); n]; n];
        for &(a, b, w) in e.iter() {
            if w % i == 0 {
                cnt += 1;
                let v = Dual::new(M::one(), M::from(w));
                mat[a][a] = mat[a][a] + v;
                mat[b][b] = mat[b][b] + v;
                mat[a][b] = mat[a][b] - v;
                mat[b][a] = mat[b][a] - v;
            }
        }
        if cnt < n - 1 {
            continue;
        }
        for m in mat.iter_mut() {
            m.pop();
        }
        mat.pop();
        let det = determinant(mat).1;
        ans += M::from(*phi) * det;
    }
    println!("{}", ans);
}

// ---------- begin Dual ----------
#[derive(Clone, Copy, Default)]
pub struct Dual<T>(T, T);

impl<T> Dual<T> {
    pub fn new(a: T, b: T) -> Self {
        Self(a, b)
    }
}

impl<T> Zero for Dual<T>
where
    T: Zero,
{
    fn zero() -> Self {
        Self::new(T::zero(), T::zero())
    }
    fn is_zero(&self) -> bool {
        self.0.is_zero()
    }
}

impl<T> One for Dual<T>
where
    T: One + Zero + Clone,
{
    fn one() -> Self {
        Self::new(T::one(), T::zero())
    }
}

impl<T> Ring for Dual<T> where T: One + Zero + Clone + Sub<Output = T> {}
impl<T> Field for Dual<T> where T: One + Zero + Clone + Sub<Output = T> + Div<Output = T> {}

impl<T> Add for Dual<T>
where
    T: Add<Output = T>,
{
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        Self::new(self.0 + rhs.0, self.1 + rhs.1)
    }
}

impl<T> Sub for Dual<T>
where
    T: Sub<Output = T>,
{
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        Self::new(self.0 - rhs.0, self.1 - rhs.1)
    }
}

impl<T> Mul for Dual<T>
where
    T: Clone + Add<Output = T> + Mul<Output = T>,
{
    type Output = Self;
    fn mul(self, rhs: Self) -> Self {
        Self::new(
            self.0.clone() * rhs.0.clone(),
            self.0 * rhs.1 + self.1 * rhs.0,
        )
    }
}

impl<T> Div for Dual<T>
where
    T: Clone + One + Zero + Sub<Output = T> + Div<Output = T>,
{
    type Output = Self;
    fn div(self, rhs: Self) -> Self {
        assert!(!rhs.0.is_zero());
        let x = T::one() / rhs.0;
        let y = T::zero() - x.clone() * x.clone() * rhs.1;
        self * Self::new(x, y)
    }
}
// ---------- end Dual ----------

fn read() -> (usize, Vec<(usize, usize, usize)>) {
    let mut s = String::new();
    use std::io::*;
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace().flat_map(|s| s.parse::<usize>());
    let mut next = || it.next().unwrap();
    let n = next();
    let m = next();
    let e = (0..m)
        .map(|_| {
            let a = next() - 1;
            let b = next() - 1;
            let c = next();
            (a, b, c)
        })
        .collect();
    (n, e)
}

pub fn determinant<T>(mut mat: Vec<Vec<T>>) -> T
where
    T: Field + Copy,
{
    let n = mat.len();
    assert!(mat.iter().all(|mat| mat.len() == n));
    let mut det = T::one();
    for i in (0..n).rev() {
        if let Some(x) = mat.iter().position(|mat| !mat[i].is_zero()) {
            if i != x {
                mat.swap(i, x);
                det = det * (T::zero() - T::one());
            }
            let mut a = mat.pop().unwrap();
            det = det * a[i];
            let inv = T::one() / a[i];
            a[..i].iter_mut().for_each(|a| *a = *a * inv);
            for mat in mat.iter_mut() {
                let mul = mat[i];
                for (mat, a) in mat.iter_mut().zip(a.iter()).take(i) {
                    *mat = *mat - mul * *a;
                }
            }
        } else {
            return T::zero();
        }
    }
    det
}

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;
}

pub trait Ring: Zero + One + Sub<Self, Output = Self> {}
pub trait Field: Ring + Div<Self, Output = Self> {}

impl<T: Modulo> Zero for ModInt<T> {
    fn zero() -> Self {
        Self::zero()
    }
    fn is_zero(&self) -> bool {
        self.is_zero()
    }
}

impl<T: Modulo> One for ModInt<T> {
    fn one() -> Self {
        Self::one()
    }
}

impl<T: Modulo> Ring for ModInt<T> {}
impl<T: Modulo> Field for ModInt<T> {}

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
}

use std::marker::*;
use std::ops::*;

pub trait Modulo {
    fn modulo() -> u32;
    fn build(v: u32) -> u32;
    fn reduce(v: u64) -> u32;
}

pub struct ConstantModulo<const M: u32>;

impl<const M: u32> ConstantModulo<{ M }> {
    const ORDER: usize = (M - 1).trailing_zeros() as usize;
    const PRIMITIVE_ROOT: u32 = primitive_root(M);
    const ZETA: u32 = pow_mod(Self::PRIMITIVE_ROOT, (M - 1) >> Self::ORDER, 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));
}

impl<const M: u32> Modulo for ConstantModulo<{ M }> {
    fn modulo() -> u32 {
        M
    }
    fn build(v: u32) -> u32 {
        Self::reduce(v as u64 * Self::INI)
    }
    fn reduce(x: u64) -> u32 {
        debug_assert!(x < (Self::modulo() as u64) << 32);
        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
    }
}

pub trait NTTFriendly {
    fn order() -> usize;
    fn zeta() -> u32;
}

impl<const M: u32> NTTFriendly for ConstantModulo<{ M }> {
    fn order() -> usize {
        Self::ORDER
    }
    fn zeta() -> u32 {
        Self::ZETA
    }
}

pub struct ModInt<T>(u32, PhantomData<fn() -> T>);

impl<T> Clone for ModInt<T> {
    fn clone(&self) -> Self {
        Self::build(self.0)
    }
}

impl<T> Copy for ModInt<T> {}

impl<T: Modulo> Add for ModInt<T> {
    type Output = Self;
    fn add(self, rhs: Self) -> Self::Output {
        let mut v = self.0 + rhs.0;
        if v >= T::modulo() {
            v -= T::modulo();
        }
        Self::build(v)
    }
}

impl<T: Modulo> Sub for ModInt<T> {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self::Output {
        let mut v = self.0 - rhs.0;
        if self.0 < rhs.0 {
            v += T::modulo();
        }
        Self::build(v)
    }
}

impl<T: Modulo> Mul for ModInt<T> {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self::Output {
        Self::build(T::reduce(self.0 as u64 * rhs.0 as u64))
    }
}

impl<T: Modulo> Div for ModInt<T> {
    type Output = Self;
    fn div(self, rhs: Self) -> Self::Output {
        self * rhs.inv()
    }
}

impl<T: Modulo> AddAssign for ModInt<T> {
    fn add_assign(&mut self, rhs: Self) {
        *self = *self + rhs;
    }
}

impl<T: Modulo> SubAssign for ModInt<T> {
    fn sub_assign(&mut self, rhs: Self) {
        *self = *self - rhs;
    }
}

impl<T: Modulo> MulAssign for ModInt<T> {
    fn mul_assign(&mut self, rhs: Self) {
        *self = *self * rhs;
    }
}

impl<T: Modulo> Neg for ModInt<T> {
    type Output = Self;
    fn neg(self) -> Self::Output {
        if self.is_zero() {
            Self::zero()
        } else {
            Self::build(T::modulo() - self.0)
        }
    }
}

impl<T: Modulo> std::fmt::Display for ModInt<T> {
    fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
        write!(f, "{}", self.get())
    }
}

impl<T: Modulo> std::fmt::Debug for ModInt<T> {
    fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
        write!(f, "{}", self.get())
    }
}

impl<T: Modulo> std::str::FromStr for ModInt<T> {
    type Err = std::num::ParseIntError;
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let val = s.parse::<u32>()?;
        Ok(ModInt::new(val))
    }
}

impl<T: Modulo> From<usize> for ModInt<T> {
    fn from(v: usize) -> Self {
        Self::new_unchecked((v % T::modulo() as usize) as u32)
    }
}

impl<T> ModInt<T> {
    fn build(v: u32) -> Self {
        ModInt(v, PhantomData)
    }
    pub fn is_zero(&self) -> bool {
        self.0 == 0
    }
}

impl<T: Modulo> ModInt<T> {
    pub fn new_unchecked(v: u32) -> Self {
        Self::build(T::build(v))
    }
    pub fn new(v: u32) -> Self {
        Self::new_unchecked(v % T::modulo())
    }
    pub fn zero() -> Self {
        Self::new_unchecked(0)
    }
    pub fn one() -> Self {
        Self::new_unchecked(1)
    }
    pub fn get(&self) -> u32 {
        T::reduce(self.0 as u64)
    }
    pub fn pow(&self, mut n: u64) -> Self {
        let mut t = Self::one();
        let mut r = *self;
        while n > 0 {
            if n & 1 == 1 {
                t *= r;
            }
            r *= r;
            n >>= 1;
        }
        t
    }
    pub fn inv(&self) -> Self {
        assert!(!self.is_zero());
        self.pow((T::modulo() - 2) as u64)
    }
    pub fn fact(n: usize) -> Self {
        (1..=n).fold(Self::one(), |s, a| s * Self::from(a))
    }
}

const PRIME: u32 = 998_244_353;

type S = ConstantModulo<PRIME>;
type M = ModInt<S>;

詳細信息

Test #1:

score: 10
Accepted
time: 12ms
memory: 2904kb

input:

5 10
1 2 113400
1 3 131040
1 4 131040
1 5 126000
2 3 131040
2 4 90720
2 5 138600
3 4 110880
3 5 110880
4 5 95760

output:

549298858

result:

ok 1 number(s): "549298858"

Test #2:

score: 10
Accepted
time: 13ms
memory: 2952kb

input:

6 15
1 2 110880
1 3 141120
1 4 141120
1 5 131040
1 6 151200
2 3 137280
2 4 105840
2 5 138600
2 6 150480
3 4 138600
3 5 131040
3 6 137280
4 5 85680
4 6 151200
5 6 131040

output:

627752274

result:

ok 1 number(s): "627752274"

Test #3:

score: 10
Accepted
time: 92ms
memory: 3324kb

input:

25 24
1 2 147840
1 3 98280
2 4 120960
3 5 128520
5 6 128520
6 7 143640
1 8 138600
7 9 131040
3 10 147840
10 11 120120
5 12 120120
4 13 131040
8 14 151200
13 15 151200
5 16 110880
11 17 120960
6 18 151200
6 19 147840
5 20 147840
1 21 120960
14 22 110880
13 23 120120
18 24 98280
1 25 131040

output:

623404094

result:

ok 1 number(s): "623404094"

Test #4:

score: 10
Accepted
time: 111ms
memory: 3328kb

input:

28 28
1 2 128520
2 3 98280
1 4 138600
4 5 98280
2 6 98280
1 7 131040
3 8 138600
2 9 147840
6 10 120120
1 11 120960
7 12 138600
6 13 147840
3 14 120960
6 15 120960
9 16 120120
4 17 143640
3 18 128520
15 19 147840
9 20 120120
6 21 120960
20 22 147840
10 23 131040
5 24 138600
7 25 143640
5 26 120960
4 ...

output:

640377458

result:

ok 1 number(s): "640377458"

Test #5:

score: 10
Accepted
time: 115ms
memory: 3220kb

input:

30 30
1 2 110880
1 3 120960
3 4 131040
3 5 120120
3 6 138600
5 7 98280
3 8 120960
5 9 128520
1 10 128520
2 11 138600
5 12 98280
10 13 98280
11 14 143640
3 15 120960
10 16 98280
16 17 138600
5 18 138600
13 19 147840
18 20 120960
13 21 131040
15 22 151200
22 23 131040
2 24 128520
6 25 120960
20 26 138...

output:

309797364

result:

ok 1 number(s): "309797364"

Test #6:

score: 10
Accepted
time: 95ms
memory: 3248kb

input:

25 25
1 2 131040
2 3 120120
2 4 98280
3 5 110880
5 6 120120
4 7 120960
1 8 128520
4 9 110880
3 10 147840
7 11 120960
4 12 120960
2 13 138600
8 14 120960
1 15 128520
8 16 131040
10 17 110880
14 18 98280
9 19 131040
7 20 147840
8 21 138600
14 22 138600
5 23 151200
7 24 131040
13 25 143640
12 1 143640

output:

302382070

result:

ok 1 number(s): "302382070"

Test #7:

score: 10
Accepted
time: 200ms
memory: 3304kb

input:

28 376
1 2 152501
1 3 152501
1 4 152501
1 5 152501
1 6 152501
1 7 152501
1 8 152501
1 9 152501
1 10 152501
1 11 152501
1 12 152501
1 13 152501
1 14 152501
1 15 152501
1 16 152501
1 17 152501
1 18 152501
1 19 152501
1 20 152501
1 21 152501
1 22 152501
1 23 152501
1 24 152501
1 25 152501
1 26 152501
1...

output:

493255263

result:

ok 1 number(s): "493255263"

Test #8:

score: 10
Accepted
time: 219ms
memory: 3272kb

input:

30 431
1 2 152501
1 3 152501
1 4 152501
1 5 152501
1 6 152501
1 7 152501
1 8 152501
1 9 152501
1 10 152501
1 11 152501
1 12 152501
1 13 152501
1 14 152501
1 15 152501
1 16 152501
1 17 152501
1 18 152501
1 19 152501
1 20 152501
1 21 152501
1 22 152501
1 23 152501
1 24 152501
1 25 152501
1 26 152501
1...

output:

441996120

result:

ok 1 number(s): "441996120"

Test #9:

score: 10
Accepted
time: 205ms
memory: 3180kb

input:

28 372
1 2 152501
1 3 152501
1 4 152501
1 5 152501
1 6 152501
1 7 152501
1 8 152501
1 9 152501
1 10 152501
1 11 152501
1 12 152501
1 13 152501
1 14 152501
1 15 152501
1 16 152501
1 17 152501
1 18 152501
1 19 152501
1 20 152501
1 21 152501
1 22 152501
1 23 152501
1 24 152501
1 25 152501
1 26 152501
1...

output:

179882346

result:

ok 1 number(s): "179882346"

Test #10:

score: 10
Accepted
time: 223ms
memory: 3228kb

input:

30 432
1 2 152501
1 3 152501
1 4 152501
1 5 152501
1 6 152501
1 7 152501
1 8 152501
1 9 152501
1 10 152501
1 11 152501
1 12 152501
1 13 152501
1 14 152501
1 15 152501
1 16 152501
1 17 152501
1 18 152501
1 19 152501
1 20 152501
1 21 152501
1 22 152501
1 23 152501
1 24 152501
1 25 152501
1 26 152501
1...

output:

45748263

result:

ok 1 number(s): "45748263"

Extra Test:

score: 0
Extra Test Passed