DDOSvoid's Blog

CF 917D Stranger Trees

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

题目描述

https://codeforces.com/problemset/problem/917/D

简要题意：给定一个 $n$ 个点无向树，求对于 $k\in[1,n - 1]$，有多少棵这 $n$ 个点的完全无向图的生成树与这棵树有恰好 $k$ 条边重复

$n\le 100$

Solution

我们考虑令树边的权值为 $x$，非树边的权值为 $1$，那么对这张图用矩阵树定理求求出的 $n-1$ 次多项式的系数就是我们要的答案，但我们显然不能直接暴力拿多项式来做矩阵树定理，我们考虑带 $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
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
#include <iostream>
#include <vector>
#define maxn 110
using namespace std;

const int p = 1000000007;
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; 
}

int n, m;

struct Edge {
    int u, v;
} e[maxn]; 

int w[maxn][maxn];

int g[maxn][maxn];
int Gauss(int n) {
    int res = 1; 
    for (int i = 1; i <= n; ++i) {
        int pos = -1;
        for (int j = i; j <= n; ++j) if (g[j][i]) pos = j;
        if (pos == -1) return 0; swap(g[i], g[pos]); if (pos != i) res = p - res;
        res = mul(res, g[i][i]); int inv = pow_mod(g[i][i], p - 2);
        for (int j = i + 1; j <= n; ++j) 
            for (int k = n; k >= i; --k)
                g[j][k] = add(g[j][k], p - mul({ g[j][i], inv, g[i][k] }));
    } return res;
}

#define Poly vector<int> 
Poly Lagrange(const Poly &x, const Poly &y, int n) { // i in [1, n], n >= 2
    Poly a(n + 1), b(n + 1); a[0] = 1; 
    for (int i = 1; i <= n; ++i) { 
        for (int j = i; j; --j) a[j] = add(a[j - 1], p - mul(x[i], a[j]));
        a[0] = p - mul(x[i], a[0]);
    } Poly res(n); 
    for (int i = 1; i <= n; ++i) {
        for (int j = n - 1; ~j; --j) b[j] = add(a[j + 1], mul(x[i], b[j + 1]));
        int t = 1;
        for (int j = 1; j <= n; ++j)
            if (i != j) t = mul(t, add(x[i], p - x[j]));
        t = mul(pow_mod(t, p - 2), y[i]);
        for (int j = 0; j < n; ++j) res[j] = add(res[j], mul(b[j], t)); 
    } return res;
}

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

    cin >> n;
    for (int i = 1; i < n; ++i) cin >> e[i].u >> e[i].v;
    vector<int> x(n + 1), y(n + 1); 
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) g[i][i] = n - 1; 
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) if (i != j) g[i][j] = p - 1;
        for (int i = 1; i < n; ++i) {
            int u = e[i].u, v = e[i].v;
            g[u][u] = add(g[u][u], k - 1), g[v][v] = add(g[v][v], k - 1);
            g[u][v] = p - k, g[v][u] = p - k; 
        } x[k] = k, y[k] = Gauss(n - 1);
    } Poly res = Lagrange(x, y, n);
    for (int i = 0; i < n; ++i) cout << res[i] << " \n"[i == n - 1]; 
    return 0;
}

第一种做法是比较直观无脑的，我们考虑将问题稍做转换，如果我们只选择 $k$ 条边，那么相当于现在还有 $n-k$ 个连通块，我们知道一个结论是，使用 $k-1$ 条边将 $k$ 个连通块连通的方案数为 $n^{k-2}\prod_{i=1}^ks_i$，其中 $s_i$ 表示第 $i$ 个连通块的大小

根据这个结论，我们考虑用树形 $dp$ 求出选择 $k$ 条边的 $\prod_{i=1}^k s_i$ 的和，连通块的大小的乘积这个东西有一个经典的做法就是我们记录每个连通块选恰好一个点的方案数，我们令 $f_{u,i,0/1}$ 表示连通块有 $i$ 个，$u$ 所在的连通块是否有选点，我们求出这东西之后将其乘上 $n^{k-2}$ 得到的东西并不是答案，这个可能会算重，我们再容斥一下即可

时间复杂度 $O(n^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
#include <iostream>
#include <vector>
#define maxn 110
using namespace std;
 
const int p = 1000000007;
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; 
}
 
int n, m;
 
struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}
 
int f[maxn][maxn][2], g[maxn][2], sz[maxn];
void dfs(int u, int fa) {
    sz[u] = 1; 
    f[u][1][0] = f[u][1][1] = 1; 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue; dfs(v, u);
        for (int s = 1; s <= sz[u] + sz[v]; ++s)
            for (int o = 0; o < 2; ++o) g[s][o] = 0;
        for (int s = 1; s <= sz[u]; ++s)
            for (int o = 0; o < 2; ++o) { 
                if (!f[u][s][o]) continue;
                for (int t = 1; t <= sz[v] && s + t <= n; ++t)
                    for (int p = 0; p < 2; ++p) {
                        int val = mul(f[u][s][o], f[v][t][p]);
                        if (o + p < 2) g[s + t - 1][o | p] = add(g[s + t - 1][o | p], val);
                        if (p) g[s + t][o] = add(g[s + t][o], val); 
                    }
            }
        sz[u] += sz[v];
        for (int s = 1; s <= sz[u]; ++s)
            for (int o = 0; o < 2; ++o) f[u][s][o] = g[s][o];
    } 
}
 
int C[maxn][maxn];
void init_C(int n) {
    for (int i = 0; i <= n; ++i) C[i][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j) C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
}
 
int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
 
    cin >> n; init_C(n);
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x); 
    } dfs(1, 0);
    vector<int> f(n + 1), g(n + 1);
    for (int i = 0; i < n; ++i) {
        if (i == n - 1) f[i] = 1;
        else f[i] = mul(pow_mod(n, n - i - 2), ::f[1][n - i][1]); 
    }
    for (int i = 0; i < n; ++i)
        for (int j = i, opt = 1; j < n; ++j, opt = p - opt)
            g[i] = add(g[i], mul({opt, C[j][i], f[j]}));
    for (int i = 0; i < n; ++i) cout << g[i] << " \n"[i == n - 1];
    return 0;
}