CF1408G Clusterization Counting

发表于 | 阅读数

给定 $n$ 个点的无向带权完全图，边权为 $1\sim\frac{n(n-1)}{2}$。对于满足 $1\leq k\leq n$ 的每个 $k$ 求出将原图划分成 $k$ 个组的方案数，满足组间边的权大于组内边的权值，答案对 $998244353$ 取模。

$n\leq 1500$

组间边$>$组内边，就是最小的 Kruskal重构树。

即构成重构树之后，一组方案就是重构树上的一个子树。

  • 但需要注意，建完Kruskal重构树，并不能保证组间边$>$组内边，每次建的时候需要特判，是否把所有之间的边加进去，如果没有显然，显然这个子树会出现一个大于组间边的组外边。

那么 checkcheck 每个子树能否成为一个联通块，然后做一个树上背包即可。

树上背包重载一下$dp[x]$的乘法即。然后好像可以证明复杂度不超过$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
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 3e3 + 10;
const int mod = 998244353;

const int SEN = 4e5 + 10;

struct Edge
{
    int u, v, w;

    bool operator<(const Edge &b) const
    {
        return w < b.w;
    }
};
using poly = vector<int>;
poly operator*(poly a, poly b)
{
    poly c(a.size() + b.size() - 1);
    for (size_t i = 0; i < a.size(); ++i)
        for (size_t j = 0; j < b.size(); ++j)
            c[i + j] = (c[i + j] + 1ll * a[i] * b[j] % mod) % mod;
    return c;
}

int k;
namespace KruskalTree
{
    int fa[N];
    poly dp[N];
    int dep[N], a[N], dfn[N], ed[N], tot;
    int siz[N], flag[N], en[N];
    vector<int> g[N];
    int find(int x)
    {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    void addedge(int u, int v)
    {

        g[u].push_back(v);
        g[v].push_back(u);
    }

    void inc(int x)
    {
        en[x]++;
        if (en[x] == (siz[x] - 1) * siz[x] / 2)
            flag[x] = 1;
    }

    void dfs2(int x, int fa)
    {
        vector<int> tmp;
        if (g[x].size() <= 1)
        {
            dp[x] = {0, 1};
            return;
        }
        for (int to : g[x])
        {
            if (to == fa)
                continue;
            dfs2(to, x);
            tmp.push_back(to);
        }
        if (tmp.size() >= 2)
        {
            for (int i = 0; i + 1 < tmp.size(); i++)
                dp[tmp[i]] = dp[tmp[i]] * dp[tmp[i + 1]];

            dp[x] = dp[tmp[tmp.size() - 2]];
        }
        if (flag[x])

            dp[x][1] = 1;
    }
    void init(int n, vector<Edge> e)
    {
        for (int i = 0; i <= n << 1; i++)
            fa[i] = i;
        for (int i = 1; i <= n; i++)
            flag[i] = 1, siz[i] = 1;
        int cnt = n;
        sort(e.begin(), e.end());
        for (Edge now : e)
        {
            int u = now.u, v = now.v, w = now.w;

            int x = find(u), y = find(v);
            //cout << u << " " << v << " " << w << endl;
            if (x == y)
            {
                inc(x);
                continue;
            }
            cnt++;
            fa[x] = fa[y] = cnt;
            siz[cnt] = siz[x] + siz[y];
            en[cnt] = en[x] + en[y];
            addedge(x, cnt);
            addedge(y, cnt);
            inc(cnt);
        }

        dfs2(cnt, 0);
        }

} // namespace KruskalTree
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}

using namespace KruskalTree;

int w[N][N];
int main()
{
    int n = read();
    k = n;
    vector<Edge> e;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            w[i][j] = read();
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            e.push_back({i, j, w[i][j]});

    init(n, e);
}