写在前面的，一道非常好的题，思路很顺滑（是这样用的吧），考察的数据结构也很巧妙。

分析

首先从小到大把边加进来，那么，一个连通块是满足条件的当且仅当在加完某条边之后这个连通块是一个团。所以我们就有了个，指数级别的 。那么如何去掉连通块的问题。其实我们如果按照边的长度排序。构建一棵重构树。那么我们发现，一个连通块一定是一个节点的子树。那么我们可以定义状态 为以 为根节点，分成 组的总方案。那么转移为 。根据树形背包的时间复杂度分析可以知道，总转移是 的，(好像可以用 优化转移，不是时间瓶颈不分析) 。那么最后答案为 。总的复杂度为 。

• 在重构时，记录边的数量，看看是否已经构成了团。

代码

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
const int N = 3010,inf = 0x3f3f3f3f,mod = 998244353;
int f[N][N],si[N],tot[N],ed[N],n,fa[N],lc[N],rc[N],able[N];
pii e[N * N];
int C2(int a) {return 1ll * a * (a - 1) / 2;}
int findset(int x) {return fa[x] == x ? x : fa[x] = findset(fa[x]);}
void dfs(int x) {
    if(x <= n) {tot[x] = f[x][1] = 1;return;}
    dfs(lc[x]);dfs(rc[x]);
    for(int i = 1;i <= tot[lc[x]];i++) {
        for(int j = 1;j <= tot[rc[x]];j++) {
            f[x][i + j] = (f[x][i + j] + 1ll * f[lc[x]][i] * f[rc[x]][j] % mod) % mod;
        }
    }tot[x] = tot[lc[x]] + tot[rc[x]];
    if(able[x]) f[x][1] = (f[x][1] + 1) % mod;
} 
int main() {
    n = read();
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            int w = read();if(i < j) e[w] = pii(i,j);
        }
    }for(int i = 1;i <= n;i++) fa[i] = i,si[i] = 1;
    int cnt = n,rt = n;
    for(int i = 1;i <= C2(n);i++) {
        int a = findset(e[i].first),b = findset(e[i].second);
        if(a == b) {ed[a]++;if(ed[a] == C2(si[a])) able[a] = 1;}
        else {
            cnt++;rt = cnt;lc[cnt] = a;rc[cnt] = b;
            fa[a] = fa[b] = fa[cnt] = cnt;
            ed[cnt] = ed[a] + ed[b] + 1;
            si[cnt] = si[a] + si[b];
            if(ed[cnt] == C2(si[cnt])) able[cnt] = 1;
        }
    }
    dfs(rt);
    for(int i = 1;i <= n;i++) printf("%d ",f[rt][i]);printf("\n");
    return 0;
}