题目
点这里看题目。
分析
不难想到，题目的要求，就是要组内边总是比相邻的组间边小。
也就是要组内边的最大值小于组间边的最小值。
于是可以从小到大加边。如果一个连通块在加边的时候，变成了一个团，这就意味着现在这个连通块可以单分为一组（剩余的边只有可能成为组间边，组间边都比组内边大）。之后我们就用 (G(Gsubset V)) 表示一个组。
我们可以证明，能分的组的数量是 (O(n)) 的，且任意两组要么包含，要么不交。
关于数量的证明：
考虑用组内边的权最大的一条来代替这个组，我们称这种边为 " 标准边 " 。
对于标准边 (e) ，我们可以不断地扩展边权小于 (e) 的边，最终找到这条标准边对应的组的点集。
如果仅由标准边形成的子图有环，那么考虑一个环上的最大边 (e) 和次大边 (e') 。此时 (e') 对应的组包含这个环，但是环上点集对应的团包含了 (e) ，(e) 的权大于 (e') ，出现了矛盾。
所以可以知道，标准边最终会形成森林的样子，因此数量是 (O(n)) 的。
关于组的关系的证明：
直接考虑两个相交但却不包含的组 (G_1,G_2)。我们提出它们的两个标准边，记为 (e_1,e_2) 。
由于边权彼此不等，因此不妨认为 (e_1) 的权大于 (e_2) 。那么显然 (G_2subset G_1) ，矛盾。
综合以上我们可以知道，最终可以单独划分的组数量是 (O(n)) 的，且可以按照包含关系划分成树的形状。
我们可以直接从小到大加边，建立 Kruskal 重构树。此时树上的每一个点都对应了一个连通块。我们可以直接在建树的时候判断一个连通块是否可以被单独划分。
接着就可以直接在树上对可行的块进行背包 DP 了。时间复杂度是 (O(n^2)) 的。
代码
#include <cstdio>
#include <utility>
using namespace std;
typedef long long LL;
typedef pair<int, int> Edge;
const int mod = 998244353;
const int MAXN = 3e3 + 5;
template<typename _T>
void read( _T &x )
{
x = 0; char s = getchar(); int f = 1;
while( s < '0' || '9' < s ) { f = 1; if( s == '-' ) f = -1; s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ); s = getchar(); }
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) write( x / 10 );
putchar( x % 10 + '0' );
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
int f[MAXN][MAXN];
int lch[MAXN], rch[MAXN], tot[MAXN];
bool able[MAXN];
int fa[MAXN], siz[MAXN], Etot[MAXN];
Edge E[MAXN * MAXN];
int Graph[MAXN][MAXN];
int N, ID;
int Edg( const int n ) { return n * ( n - 1 ) >> 1; }
int Sub( int x, int v ) { return x < v ? x + mod - v : x - v; }
int Mul( LL x, int v ) { x *= v; if( x >= mod ) x %= mod; return x; }
int Add( int x, int v ) { return x + v >= mod ? x + v - mod : x + v; }
int FindSet( const int u ) { return fa[u] = ( fa[u] == u ? u : FindSet( fa[u] ) ); }
void DFS( const int u )
{
if( u <= N ) { tot[u] = f[u][1] = 1; return; }
int l = lch[u], r = rch[u]; DFS( l ), DFS( r );
for( int j = 1 ; j <= tot[r] ; j ++ )
for( int k = 1 ; k <= tot[l] ; k ++ )
f[u][j + k] = Add( f[u][j + k], Mul( f[l][k], f[r][j] ) );
tot[u] = tot[l] + tot[r];
if( able[u] ) f[u][1] = Add( f[u][1], 1 );
}
int main()
{
read( N );
for( int i = 1 ; i <= N ; i ++ )
for( int j = 1 ; j <= N ; j ++ )
{
read( Graph[i][j] );
if( i < j ) E[Graph[i][j]] = Edge( i, j );
}
for( int i = 1 ; i <= N << 1 ; i ++ )
fa[i] = i, siz[i] = i <= N;
int cnt = N, rt = N;
for( int i = 1 ; i <= N ; i ++ ) f[i][1] = 1;
for( int i = 1, u, v ; i <= Edg( N ) ; i ++ )
{
u = FindSet( E[i].first ),
v = FindSet( E[i].second );
if( u != v )
{
fa[u] = fa[v] = ++ cnt;
lch[cnt] = u, rch[cnt] = v, rt = cnt;
Etot[cnt] = Etot[u] + Etot[v] + 1, siz[cnt] = siz[u] + siz[v];
if( Etot[cnt] == Edg( siz[cnt] ) ) able[cnt] = true;
}
else
{
if( ( ++ Etot[u] ) == Edg( siz[u] ) )
able[u] = true;
}
}
DFS( rt );
for( int k = 1 ; k <= N ; k ++ ) write( f[rt][k] ), putchar( k == N ? '
' : ' ' );
return 0;
}