DDOSvoid's Blog

Luogu P5296 [北京省选集训2019]生成树计数

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

题目描述

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

简要题意：给定一个 $n$ 个点的带权完全无向图，给定 $k$，求所有生成树的权值的 $k$ 次方之和

$n,k\le 30$

Solution

我们知道 $(\sum_{i=1}^{n-1}w_i)^k=\sum_{i\in[1,n-1],a_i\ge0,\sum_{a_i}=k}\binom{k}{a_1,\cdots,a_k}\prod_{i=1}^{n-1}w_i^{a_i}$，这是一个多项式卷积的形式，我们考虑将其看做生成函数，相当于 $ans=k![x^k]\prod_{i=1}^{n-1}e^{w_ix}$

我们把每条边看做一个 $k$ 次的多项式，然后做矩阵树定理即可，因为 $k$ 很小，所以求逆和乘法直接 $O(k^2)$ 暴力即可

时间复杂度 $O(n^3k^2)$

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
#include <iostream>
#include <vector>
#define maxn 31
using namespace std;

const int p = 998244353;
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; }
inline int add(initializer_list<int> lst) { int s = 0; for (auto t : lst) s = add(s, t); return s; }
inline int mul(initializer_list<int> lst) { int s = 1; for (auto t : lst) s = mul(s, t); return s; }
int pow_mod(int x, int n) {
    int s = 1;
    for (; n; n >>= 1, x = mul(x, x))
        if (n & 1) s = mul(s, x);
    return s; 
}

#define Poly vector<int>
#define len(a) (a.size())
namespace Pol {
    Poly operator + (const Poly &u, const Poly &v) { // len(u) == len(v)
        int n = len(u); Poly res(n);
        for (int i = 0; i < n; ++i) res[i] = add(u[i], v[i]);
        return res;
    }
    Poly operator - (const Poly &u, const Poly &v) { // len(u) == len(v)
        int n = len(u); Poly res(n);
        for (int i = 0; i < n; ++i) res[i] = add(u[i], p - v[i]);
        return res;
    }
    /*Poly operator * (const Poly &u, const Poly &v) {
        int n1 = len(u), n2 = len(v); Poly res(n1 + n2 - 1); 
        for (int i = 0; i < n1; ++i)
            for (int j = 0; j < n2; ++j) res[i + j] = add(res[i + j], mul(u[i], v[j]));
        return res;
        }*/
    Poly operator * (const Poly &u, const Poly &v) { // len(u) == len(v)
        int n = len(u); Poly res(n);
        for (int i = 0; i < n; ++i)
            for (int j = 0; i + j < n; ++j) res[i + j] = add(res[i + j], mul(u[i], v[j]));
        return res;
    }
    Poly Inv(const Poly &a) {
        int n = len(a); Poly res(n); res[0] = pow_mod(a[0], p - 2); Poly ta(n);
        for (int i = 1; i < n; ++i) ta[i] = mul(a[i], res[0]);
        for (int i = 1; i < n; ++i)
            for (int j = 1; j <= i; ++j) res[i] = add(res[i], mul(p - ta[j], res[i - j]));
        return res;
    }
}

int n, k;
int w[maxn][maxn];

Poly g[maxn][maxn];
Poly Gauss(int n) {
    Poly res(k + 1); res[0] = 1;
    for (int i = 1; i <= n; ++i) {
        int pos = -1; for (int j = i; j <= n; ++j) if (g[j][i][0] > 0) pos = j;
        swap(g[i], g[pos]); if (pos != i) for (int j = 0; j <= k; ++j) res[j] = p - res[j];
        res = Pol::operator*(res, g[i][i]); Poly inv = Pol::Inv(g[i][i]);
        for (int j = i + 1; j <= n; ++j) 
            for (int k = n; k >= i; --k)
                g[j][k] = Pol::operator-(g[j][k], Pol::operator*(Pol::operator*(g[j][i], inv), g[i][k]));
    } return res;
}

int fac[maxn], inv[maxn];
void init_C(int n) {
    fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
    inv[n] = pow_mod(fac[n], p - 2); for (int i = n - 1; ~i; --i) inv[i] = mul(inv[i + 1], i + 1); 
}

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

    cin >> n >> k; init_C(k);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) cin >> w[i][j];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) g[i][j].resize(k + 1); 
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j < i; ++j) 
            for (int k = 0, t = 1; k <= ::k; ++k, t = mul(t, w[i][j])) {
                g[i][j][k] = p - mul(t, inv[k]);
                g[j][i][k] = p - mul(t, inv[k]);
                g[i][i][k] = add(g[i][i][k], mul(t, inv[k]));
                g[j][j][k] = add(g[j][j][k], mul(t, inv[k])); 
            }
    Poly res = Gauss(n - 1); cout << mul(fac[k], res[k]) << "\n";
    return 0;
}