题解 CF1408G 【Clusterization Counting】
s_r_f
·
·
题解
一些怨念：赛时差 2min 没冲完这个题……
建出 Kruskal 重构树. 不难发现我们取的联通块必然是 Kruskal 重构树上的一个子树。
那么 check 每个子树能否成为一个联通块，然后做一个树上背包即可。
code :
```cpp
#include <bits/stdc++.h>
#define LL long long
using namespace std;
template <typename T> void read(T &x){
static char ch; x = 0,ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }
const int N = 3005,P = 998244353;
inline void upd(int &x,int v){ x = (x+v>=P)?(x+v-P):(x+v); }
int n,G[N][N],cntv;
struct Union_Find_Set{
int fa[N<<1];
inline void init(){ for (int i = 1; i <= n<<1; ++i) fa[i] = i; }
inline int Find(int x){ return x == fa[x] ? x : (fa[x] = Find(fa[x])); }
inline void Merge(int x,int y){ fa[Find(x)] = Find(y); }
}S;
struct Edge{
int x,y;
bool operator < (const Edge w) const{ return G[x][y] < G[w.x][w.y]; }
}e[N*N/2]; int le;
int Rt,fa[N<<1],ch[N<<1][2];
int F[N<<1][N],siz[N],tl[N],tr[N],Time,pos[N];
int mx[N<<1],pre[N][N],suf[N][N];
inline void dfs0(int x){
if (x <= n){ tl[x] = tr[x] = ++Time; pos[Time] = x; siz[x] = 1; return; }
dfs0(ch[x][0]); dfs0(ch[x][1]); tl[x] = tl[ch[x][0]],tr[x] = tr[ch[x][1]]; siz[x] = siz[ch[x][0]] + siz[ch[x][1]];
}
inline void dfs(int x){
if (x <= n){ F[x][1] = 1; return; }
dfs(ch[x][0]); dfs(ch[x][1]);
for (int i = 1; i <= siz[ch[x][0]]; ++i)
for (int j = 1; j <= siz[ch[x][1]]; ++j){
upd(F[x][i+j],(LL)F[ch[x][0]][i] * F[ch[x][1]][j] % P);
}
mx[x] = max(mx[ch[x][0]],mx[ch[x][1]]);
for (int i = tl[ch[x][0]]; i <= tr[ch[x][0]]; ++i)
for (int j = tl[ch[x][1]]; j <= tr[ch[x][1]]; ++j) mx[x] = max(mx[x],G[pos[i]][pos[j]]);
for (int i = tl[x]; i <= tr[x]; ++i){
int val = 1000000000;
if (tl[x] > 1) val = min(val,pre[pos[i]][tl[x]-1]);
if (tr[x] < n) val = min(val,suf[pos[i]][tr[x]+1]);
if (val < mx[x]){ F[x][1] = (F[x][1] + P-1) % P; break; }
}
F[x][1] = (F[x][1] + 1) % P;
}
int main(){
int i,j,u,v;
read(n); cntv = n; S.init();
for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) read(G[i][j]);
for (i = 1; i <= n; ++i) for (j = i+1; j <= n; ++j) ++le,e[le].x = i,e[le].y = j;
for (i = 1; i <= n; ++i) G[i][i] = 100000000;
sort(e+1,e+le+1);
for (i = 1; i <= le; ++i){
u = S.Find(e[i].x),v = S.Find(e[i].y);
if (u == v) continue;
++cntv; S.Merge(u,cntv); S.Merge(v,cntv);
ch[cntv][0] = u,ch[cntv][1] = v; fa[u] = fa[v] = cntv; Rt = cntv;
}
dfs0(Rt);
for (i = 1; i <= n; ++i){
for (j = 1; j <= n; ++j) pre[i][j] = suf[i][j] = G[i][pos[j]];
for (j = 2; j <= n; ++j) pre[i][j] = min(pre[i][j],pre[i][j-1]);
for (j = n-1; j ; --j) suf[i][j] = min(suf[i][j],suf[i][j+1]);
}
dfs(Rt);
for (i = 1; i <= n; ++i) write(F[Rt][i]),putchar(i<n?' ':'\n');
return 0;
}
```