DDOSvoid's Blog

Luogu P6624 [省选联考 2020 A 卷] 作业题

发表于 分类于
本文字数： 3.3k 阅读时长 ≈ 3 分钟

题目描述

https://www.luogu.com.cn/problem/P6624

简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，定义一个生成树 $T$ 的价值为 $\sum_{i=1}^{n-1}w_{e_i}\times(w_{e_1},w_{e_2},\cdots,w_{e_{n-1}})$ ，求所有生成树的价值之和

$n\le 30,m\le \frac{n(n-1)}{2}w_i\le 152501$

Solution

首先考虑将 $gcd$ 拆掉，然后对式子进行化简

矩阵树定理将 $\prod$ 转换成 $\sum$ 是经典 $trick$，但现在的问题是如果枚举 $d$，那么时间复杂度 $O(n^3w_i)$，无法通过此题

这个时候我们考虑只有枚举 $d$ 之后边数大于等于 $n-1$ 才跑矩阵树定理，那么这样的时间复杂度为 $O(\frac{\sum_{i}\tau(i)}{n-1}n^3)$，但是注意到边只有 $n^2$ 个，所以实际上的复杂度应该为 $O(\frac{n^2\times 144}{n-1}n^3)$，$144$ 是一条边的约数最大值，而且实际上也跑不满

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#define maxn 32
#define maxm 160000
#define ll long long
using namespace std;

const int p = 998244353;
ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
}

inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }
inline int mul(int x, int y) { return 1ll * x * y % p; }

struct node {
    int x, y;

    node (int x = 0, int y = 0) : x(x), y(y) {}

    friend node operator + (const node &u, const node &v) {
        return node(add(u.x, v.x), add(u.y, v.y));
    }
    friend node operator - (const node &u, const node &v) {
        return node(add(u.x, p - v.x), add(u.y, p - v.y));
    }
    friend node operator * (const node &u, const node &v) {
        return node(add(mul(u.x, v.y), mul(u.y, v.x)), mul(u.y, v.y));
    }
    friend node operator / (const node &u, const node &v) {
        ll inv = pow_mod(v.y, p - 2);
        return node(add(mul(u.x, v.y), p - mul(u.y, v.x)) * inv % p * inv % p,
                    mul(u.y, inv));
    }
};

node g[maxn][maxn];
int Gauss(int n) {
    node res(0, 1);
    for (int i = 1; i <= n; ++i) {
        int pos = -1;
        for (int j = i; j <= n; ++j) if (g[j][i].y) pos = j;
        if (pos == -1) return 0; swap(g[i], g[pos]);
        if (pos != i) res = res * node(0, p - 1);
        res = res * g[i][i]; node inv = node(0, 1) / g[i][i];
        for (int j = i + 1; j <= n; ++j) {
            node div = g[j][i] * inv;
            for (int k = n; k >= i; --k) g[j][k] = g[j][k] - div * g[i][k];
        }
    } return res.x;
}

int pri[maxm], cnt, phi[maxm]; bool isp[maxm];
void init_isp(int n) {
    phi[1] = 1; 
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, phi[i] = i - 1; 
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                phi[i * pri[j]] = pri[j] * phi[i];
                break;
            } phi[i * pri[j]] = (pri[j] - 1) * phi[i];
        }
    }
}

int n, m; 
vector<pair<int, int>> A[maxm];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; int N = 0; 
    for (int i = 1; i <= m; ++i) {
        int x, y, z; cin >> x >> y >> z; 
        A[z].emplace_back(x, y); N = max(N, z);  
    } ll ans = 0; init_isp(N);
    for (int d = 1; d <= N; ++d) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) g[i][j] = node(0, 0);
        int cnt = 0; 
        for (int t = d; t <= N; t += d) {
            cnt += A[t].size();
            for (auto [x, y] : A[t]) {
                g[x][x] = g[x][x] + node(t, 1);
                g[y][y] = g[y][y] + node(t, 1);
                g[x][y] = g[x][y] - node(t, 1);
                g[y][x] = g[y][x] - node(t, 1);
            }
        }
        if (cnt >= n - 1) ans = (ans + 1ll * phi[d] * Gauss(n - 1)) % p; 
    } cout << ans << "\n";
    return 0;
}