\(\mathcal{Description}\)

Link.

给定一个 \(n\) 阶完全图，边权为 \(1\sim\frac{n(n-1)}2\) 的排列。称一种将点集划分为 \(k\) 组的方案合法，当且仅当对于每个组，与其他组相连的边均大于组内的边。对于 \(k\in[1,n]\)，求合法的划分方案数，对 \(998244353\) 取模。

\(n\le1500\)。

\(\mathcal{Solution}\)

按边权从小到大加入边，发现原图中某个团可以成为一组，当且仅当存在加边过程中的某个时刻，该团 \((a)\) 已存在（\(m\) 个点间已有 \(\frac{m(m-1)}2\) 条边），\((b)\) 不与其他任何结点邻接。考虑加边过程中维护一个并查集和链表，对于边 \((u,v)\)，令其并查集的根为 \(x,y\)，若 \(x=y\) 则跳过；否则把 \(y\) 的链表接在 \(x\) 的一端，最后 \(y\leftarrow 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 ? ' ' : '\n' );

	}

	return 0;

}

\(\mathcal{Details}\)

还有一种转化成 Kruskal 重构树上 DP 的方法可以去 % 一下 @crashed 的博客。

这个算法居然比她的慢几倍 qwq。

巴特西

Solution -「CF 1480G」Clusterization Counting

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

\(\mathcal{Details}\)

最新文章

热门文章