(mathcal{Description})
Link.
给定一个 (n) 阶完全图，边权为 (1simfrac{n(n-1)}2) 的排列。称一种将点集划分为 (k) 组的方案合法，当且仅当对于每个组，与其他组相连的边均大于组内的边。对于 (kin[1,n])，求合法的划分方案数，对 (998244353) 取模。
(nle1500)。
(mathcal{Solution})
按边权从小到大加入边，发现原图中某个团可以成为一组，当且仅当存在加边过程中的某个时刻，该团 ((a)) 已存在（(m) 个点间已有 (frac{m(m-1)}2) 条边），((b)) 不与其他任何结点邻接。考虑加边过程中维护一个并查集和链表，对于边 ((u,v))，令其并查集的根为 (x,y)，若 (x=y) 则跳过；否则把 (y) 的链表接在 (x) 的一端，最后 (yleftarrow x)。不难发现一个团满足 ((b)) 等价于它的结点是链表上连续的一段区间。
接下来判断条件 ((a))，重新加一次边，并查集维护连通块内边数和链表上最左右端的位置，一次合并发现成团就连一条边 ((l,r))，表示区间 ([l,r]) 内的结点独立成组合法。注意到合法团的点集要不不交，要不包含，所以至多有 (2n-1) 个合法团（此时合法团的包含关系构成完全二叉树）。
最后就 DP 了，(f(i,j)) 表示前 (i) 个位置分成 (j) 段的方案数，利用判断 ((a)) 时连出的边转移即可。总复杂度 (mathcal O(n^2))。
(mathcal{Code})
#include <cstdio>
#include <vector>
#include <assert.h>
inline int rint () {
int x = 0; char s = getchar ();
for ( ; s < '0' || '9' < s; s = getchar () );
for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );
return x;
}
inline void wint ( const int x ) {
if ( 9 < x ) wint ( x / 10 );
putchar ( x % 10 ^ '0' );
}
const int MAXN = 1500, MAXE = MAXN * ( MAXN - 1 ) >> 1, MOD = 998244353;
int n, e, fa[MAXN + 5], fir[MAXN + 5], las[MAXN + 5], nxt[MAXN + 5];
int siz[MAXN + 5], ecnt[MAXN + 5], id[MAXN + 5], f[MAXN + 5][MAXN + 5];
bool nbeg[MAXN + 5];
std::vector<int> trans[MAXN + 5];
std::pair<int, int> ref[MAXE + 5];
inline void addeq ( int& a, const int b ) {
( a += b ) < MOD ? 0 : a -= MOD;
}
inline int find ( const int x ) {
return x ^ fa[x] ? fa[x] = find ( fa[x] ) : x;
}
inline void kLink ( int x, int y ) {
if ( ( x = find ( x ) ) ^ ( y = find ( y ) ) ) {
fa[y] = x, fir[x] = fir[y], siz[x] += siz[y], ecnt[x] += ecnt[y];
}
if ( ++ ecnt[x] == siz[x] * ( siz[x] - 1 ) >> 1 ) {
trans[las[x]].push_back ( fir[x] );
}
}
int main () {
n = rint (), e = n * ( n - 1 ) >> 1;
for ( int i = 1; i <= n; ++ i ) {
fa[i] = fir[i] = las[i] = i;
for ( int j = 1; j <= n; ++ j ) {
int id = rint ();
if ( i < j ) ref[id] = { i, j };
}
}
for ( int i = 1; i <= e; ++ i ) {
int u = find ( ref[i].first ), v = find ( ref[i].second );
if ( u == v ) continue;
nxt[las[u]] = fir[v], las[u] = las[v];
las[v] = fir[v] = -1, fa[v] = u;
}
int cnt = 0;
for ( int i = 1; i <= n; ++ i ) nbeg[nxt[i]] = true;
for ( int i = 1; i <= n; ++ i ) if ( !nbeg[i] ) id[cnt = 1] = i;
assert ( cnt );
for ( int p = id[1]; cnt ++ < n; ) id[cnt] = p = nxt[p];
for ( int i = 1; i <= n; ++ i ) {
fa[i] = fir[id[i]] = las[id[i]] = i;
ecnt[i] = 0, siz[i] = 1;
trans[i].push_back ( i );
}
for ( int i = 1; i <= e; ++ i ) kLink ( ref[i].first, ref[i].second );
f[0][0] = 1;
for ( int i = 0; i < n; ++ i ) {
for ( int j = 0, cur; j <= i; ++ j ) {
if ( !( cur = f[i][j] ) ) continue;
for ( int k: trans[i + 1] ) {
addeq ( f[k][j + 1], cur );
}
}
}
for ( int i = 1; i <= n; ++ i ) {
wint ( f[n][i] );
putchar ( i ^ n ? ' ' : '
' );
}
return 0;
}
(mathcal{Details})
还有一种转化成 Kruskal 重构树上 DP 的方法可以去 % 一下 @crashed 的博客。
这个算法居然比她的慢几倍 qwq。