矩阵树定理，好像和 2020 联合省选 作业题 套路类似。
题意：给定 $n$ 个点的树，问在所有 $n$ 个点的完全图的生成树中，与原树有 $k$ 条边相同的方案数。输出 $\forall k\in[0, n - 1]$ 的答案。$n\leq 100$。
看作多项式，如果我们把原树中的边记作 $x$，非原树中的边记作 1，那么最后所有生成树的和可以记为一个多项式，这样最后每一项的系数就对应着答案。
但是多项式卷积需要 $O(n\log n)$ 的时间，而应用矩阵树定理，计算行列式时有 $O(n ^ 3)$，总复杂度 $O(n ^ 4\log n)$，无法通过。
考虑常见套路：多次多项式乘法的时候，可以考虑维护点值而不是多项式本身。这样就可以避免不必要的多项式点值与系数之间的转换。
那么任取 $n$ 个点值，带入计算行列式，这样我们就得到了答案多项式的点值表达，最后高斯消元一下即可。时间复杂度 $O(n ^ 4)$。
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
| int det(int n)
{
int x = 0, res = 1;
for (int i = 1; i <= n; ++ i)
{
int t = -1;
for (int j = i; j <= n; ++ j)
if (a[j][i]) {
t = i;
break;
}
if (!~t) return 0;
if (t ^ i) std::swap(a[t], a[i]), x ^= 1;
int Inv = qpow(a[i][i]);
res = (LL) res * a[i][i] % Mod;
for (int j = i; j <= n + 1; ++ j) a[i][j] = (LL) a[i][j] * Inv % Mod;
for (int j = 1; j <= n; ++ j)
if (j ^ i && a[j][i])
for (int k = n + 1; k >= i; -- k)
adj(a[j][k] -= (LL) a[i][k] * a[j][i] % Mod);
}
return x ? adj(res = -res) : res;
}
int main()
{
std::cin >> n;
for (int i = 1, u, v; i < n; ++ i)
{
std::cin >> u >> v;
edg[u][v] ++, edg[v][u] ++, d[u] ++, d[v] ++;
}
for (int mul = 1; mul <= n; ++ mul)
{
for (int i = 1; i < n; ++ i)
for (int j = 1; j < n; ++ j)
adj(adj(a[i][j] = -edg[i][j] * mul) -= ((i != j) - edg[i][j]));
for (int i = 1; i < n; ++ i)
a[i][i] = (a[i][i] + (LL) d[i] * mul + (n - 1 - d[i])) % Mod;
f[mul] = det(n - 1);
}
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j) a[i][j] = qpow(i, j - 1);
for (int i = 1; i <= n; ++ i) a[i][n + 1] = f[i];
det(n);
for (int i = 1; i <= n; ++ i) printf("%d ", a[i][n + 1]);
return 0;
}
|