@atcoder - CODE FESTIVAL 2017 Elimination Tournament Round 3 F@ Unicyclic Graph Counting

@description@
@solution@
@accpeted code@
@details@

@description@

求有多少 n 点 n 边的无向连通图，满足第 i 个点的度数为 \(d_i\)。

原题传送门。

@solution@

如果是树显然就 prufer 定理；基环树就考虑拓展一下。

枚举环上的点集合 S，则环内部能够连出的方案数为 \(\frac{(|S| - 1)!}{2}\)（注意环的大小 \(|S| \geq 3\)）。

接着，将环缩成一个新点 x'，则它的度数为 \(d_{x'} = \sum_{i\in S}(d_i - 2)\)（注意 \(d_i \geq 2\)）。

对缩点后的新图运用 prufer 定理，得到：

\[\frac{(n - |S| - 1)!}{(\sum_{i\in S}(d_i - 2) - 1)!\times \prod_{i\not \in S}(d_i - 1)!}
\]

不过 x' 的出边并不是全部相同。对于 x' 还有个系数 \(\frac{(\sum_{i\in S}(d_i - 2))!}{\prod_{i\in S}(d_i - 2)!}\)，表示邻接边的分配方案。

因此整合得到：

把 \((|S|, \sum(d_i - 2))\) 当作状态做一个 O(n^3) 的 dp 求 \(\prod_{i\in S}(d_i - 1)\) 即可。

特判 n 个点连成一个大环的情况。

@accpeted code@

#include <cstdio>

#include <algorithm>

using namespace std;

const int MAXN = 300;

const int MOD = int(1E9) + 7;

const int INV2 = (MOD + 1) / 2;

inline int add(int x, int y) {return (x + y >= MOD ? x + y - MOD : x + y);}

inline int sub(int x, int y) {return (x - y < 0 ? x - y + MOD : x - y);}

inline int mul(int x, int y) {return 1LL * x * y % MOD;}

int pow_mod(int b, int p) {

	int ret = 1;

	for(int i=p;i;i>>=1,b=mul(b,b))

		if( i & 1 ) ret = mul(ret, b);

	return ret;

}

int fct[2*MAXN + 5], ifct[2*MAXN + 5];

void init() {

	fct[0] = 1; for(int i=1;i<=2*MAXN;i++) fct[i] = mul(fct[i - 1], i);

	for(int i=0;i<=2*MAXN;i++) ifct[i] = pow_mod(fct[i], MOD - 2);

}

int dp[2][MAXN + 5][MAXN + 5];

int d[MAXN + 5], N;

int main() {

	init(), scanf("%d", &N);

	for(int i=1;i<=N;i++)

		scanf("%d", &d[i]), d[i]--;

	int tot = 0; dp[0][0][0] = 1;

	for(int i=1;i<=N;i++) {

		if( d[i] ) {

			for(int j=0;j<i;j++)

				for(int k=0;k<=tot;k++)

					dp[1][j][k] = dp[0][j][k];

			for(int j=0;j<i;j++)

				for(int k=0;k<=tot;k++)

					dp[0][j+1][k+d[i]-1] = add(dp[0][j+1][k+d[i]-1], mul(d[i], dp[1][j][k]));

			tot += d[i] - 1;

		}

	}

	int ans = mul(mul(fct[N-1], INV2), dp[0][N][0]), tmp = 1;

	for(int i=1;i<=N;i++) tmp = mul(tmp, ifct[d[i]]);

	for(int i=3;i<N;i++)

		for(int j=1;j<=tot;j++) {

			int coef = mul(mul(fct[i-1], INV2), mul(fct[N-i-1], tmp));

			ans = add(ans, mul(mul(coef, j), dp[0][i][j]));

		}

	printf("%d\n", ans);

}

@details@

如果是不带度数限制基环树，还是用的 prufer 序列，和上述方法相同（貌似矩阵树解不了的样子。。。）

本题还有一个更快的 O(n^2) 做法：

\[\begin{aligned}
&\frac{(|S| - 1)!}{2}\times \frac{(n - |S| - 1)!}{(\sum_{i\in S}(d_i - 2) - 1)!\times \prod_{i\not \in S}(d_i - 1)!}\times \frac{(\sum_{i\in S}(d_i - 2))!}{\prod_{i\in S}(d_i - 2)!}\\
=&\frac{(|S| - 1)!\times (n - |S| - 1)!}{2}\times \frac{\sum_{i\in S}(d_i - 2)}{\prod_{i\not \in S}(d_i - 1)!\prod_{i \in S}(d_i - 2)!}\\
=&\frac{(|S| - 1)!\times (n - |S| - 1)!}{2}\times \sum_{i\in S}\frac{1}{\prod_{j\not \in S}(d_j - 1)!\times \prod_{j \in S, j\not = i}(d_j - 2)!\times (d_i - 3)}
\end{aligned}
\]

只需要存状态 \(|S|\) 以及是否贡献了 \(\frac{1}{d_i - 3}\)。一样需要特判。

巴特西

@atcoder - CODE FESTIVAL 2017 Elimination Tournament Round 3 F@ Unicyclic Graph Counting

@description@

@solution@

@accpeted code@

@details@

最新文章

热门文章