Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

CF917D Stranger Trees

Posted on Edited on

行列式+高斯消元。

Solution

可以发现，我们记$f(x)$这个生成函数，其$x$的指数代表选了几条边，根据矩阵树定理，构造出矩阵，用拆系数$fft$维护即可做到$O(n^4\log n)$，基本无法通过，思考我们到底干了啥，本质上我们就是通过单次$n\log n$的时间复杂度来计算了一个行列式，最后得到了一个多项式，那么我们可以先用$n+1$个点确定这个多项式，然后高斯消元。

这样就可以做到$O(n^4)$。

Code

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 <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0;
    bool flag = 0;
    char c = getchar();
    while (c < '0' || '9' < c) { if (c == '-') flag = 1; c = getchar(); }
    while ('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if (flag) res = -res;
}
template <class T, class... ARC>
inline void read(T &res, ARC &...com) { read(res), read(com...); }
template <class T>
void write(T res)
{
    if (res < 0) putchar('-'), res = -res;
    if (res > 9) write(res / 10);
    putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while (*s) putchar(*s++); }
template <class T, class... ARC>
inline void write(T res, ARC... com) { write(res), write(com...); }
const int N = 105, mod = 1e9 + 7;
int n;
int a[N][N], e[N][N], du[N];
int f[N];
inline int qpow(int x, int k)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = 1ll * res * x % mod;
        k >>= 1;
        x = 1ll * x * x % mod;
    }
    return res;
}
inline int calc(int x)
{
    int flag = 0, res = 1;
    for(int i = 1, t;i <= x;i ++)
    {
        t = -1;
        for(int j = i;j <= x;j ++)
            if(a[j][i])
            {
                t = i;
                break;
            }
        if(t == -1) return 0;
        if(t ^ i) swap(a[t], a[i]), flag ^= 1;
        int inv = qpow(a[i][i], mod - 2);
        res = 1ll * res * a[i][i] % mod;
        for(int j = i;j <= x + 1;j ++) a[i][j] = 1ll * a[i][j] * inv % mod;
        for(int j = 1;j <= x;j ++)
            if(j ^ i && a[j][i])
                for(int k = x + 1;k >= i;k --)
                    a[j][k] = (a[j][k] - 1ll * a[i][k] * a[j][i] % mod + mod) % mod;
    }
    return flag ? (-res + mod) % mod : res;
}
int main()
{
    read(n);
    for(int i = 1, o, u;i < n;i ++)
    {
        read(o, u);
        e[o][u] ++, e[u][o] ++, du[o] ++, du[u] ++;
    } 
    for(int mul = 1;mul <= n;mul ++)
    {
        for(int i = 1;i < n;i ++)
            for(int j = 1;j < n;j ++)
                a[i][j] = (mod - 1ll * e[i][j] * mul % mod),
                a[i][j] = (a[i][j] - ((i != j) - e[i][j]) + mod) % mod;
        for(int i = 1;i < n;i ++)
            a[i][i] = (a[i][i] + 1ll * du[i] * mul + (n - 1 - du[i]) % mod) % mod;
        f[mul] = calc(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];
    calc(n);
    for(int i = 1;i <= n;i ++) write(a[i][n + 1], ' ');
    return 0;
}