Statement

给你一张 nn 个点的完全图，边 (i,j)(i,j) 的边权是 w(i,j)w(i,j)。保证所有边权形成一个 1∼n(n−1)21\sim\frac{n(n-1)}2 的排列。

请你对每个 k∈[1..n]k\in[1..n]，求出把 nn 个点划分成 kk 个点集的方案数，满足：

  • 对于任意四个点 a,b,c,da,b,c,d 满足 a,b,ca,b,c 同组但 dd 不同组，有 w(a,b)<w(c,d)w(a,b)<w(c,d)。

数据范围：n≤1500n\le1500。

Solution

条件就是组内边小于组间边，也就是组内边的最大值小于组间边的最小值。

所以按边权从小到大加边，可以发现一个结论：一个连通块可以单分为一组，当且仅当这个连通块在加边的时候，变成了一个团。

因此按照 Kruskal 的过程，维护当前连通块是否是团。到这里应该可以得到指数级的 DP。

比较显然的是，合法连通块一定是 Kruskal 重构树上的一棵子树。然后就可以树形 DP 了。

这是经典的树形背包，时间复杂度 O(n2)O(n^2)。因此总时间复杂度也为 O(n2)O(n^2)。

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
#include <bits/stdc++.h>
typedef long long LL;
const int N = 3007, mod = 998244353;
namespace us {
int dad[N], val[N], siz[N];
void init(int n) { for (int i = 1; i <= n; i++) dad[i] = val[i] = i, siz[i] = 1; }
int find(int x) { return dad[x] == x ? x : dad[x] = find(dad[x]); }
}  // namespace us
int n, a[N][N], pnodes, son[N][2], cnt[N], siz[N], f[N][N];
std::pair<int, int> b[N * N];
void dfs(int u) {
    if (u <= n) return siz[u] = 1, f[u][1] = 1, void();
    static int g[N];
    f[u][0] = 1;
    for (int i = 0, v; i <= 1; siz[u] += siz[v], i++) {
        v = son[u][i], dfs(v), memset(g, 0, sizeof(int) * (siz[u] + siz[v] + 2));
        for (int x = 0; x <= siz[u]; x++)
            for (int y = 1; y <= siz[v]; y++) g[x + y] = (g[x + y] + (LL)f[u][x] * f[v][y]) % mod;
        memcpy(f[u], g, sizeof(int) * (siz[u] + siz[v] + 2));
    }
    f[u][1] = cnt[u] == siz[u] * (siz[u] - 1) / 2;
}
int main() {
    scanf("%d", &n), us::init(n), pnodes = n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) scanf("%d", a[i] + j), b[a[i][j]] = {i, j};
    for (int i = 1; i <= n * (n - 1) / 2; i++) {
        int u = us::find(b[i].first), v = us::find(b[i].second);
        if (u != v) {
            int fa = ++pnodes;
            son[fa][0] = us::val[u], son[fa][1] = us::val[v];
            cnt[fa] = cnt[son[fa][0]] + cnt[son[fa][1]] + 1;
            if (us::siz[u] < us::siz[v]) std::swap(u, v);
            us::dad[v] = u, us::siz[u] += us::siz[v], us::val[u] = fa;
        } else
            cnt[us::val[u]]++;
    }
    dfs(pnodes);
    for (int i = 1; i <= n; i++) printf("%d%c", f[pnodes][i], " \n"[i == n]);
    return 0;
}