自动搬运

查看原文

来自洛谷，原作者为

	wangbinfeng 今天搞完大概就永远不会碰 OI 了，大家祝好！

搬运于2025-08-24 23:03:09，当前版本为作者最后更新于2024-09-06 18:29:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑到，$n$ 个节点的连通图个数等于 $n$ 个节点的图的个数减去 $n$ 个节点不连通的图的个数。

对于 $n$ 个点的图可以发现其最多有 $\frac {n\times(n-1)}{2}$ 条边，每条边可以选或者不选，共计 $2^{\frac {n\times(n-1)}{2}}$ 种方案。

对于 $n$ 个节点不连通的图，发现可以由①一个连通的 包含一个固定节点 的有 $k$ 个节点的子图和②一个与之不连通的任意的子图构成。①的值可以用之前的数据（即 $ans_k$），而②因为剩下共计 $n-k$ 个节点，$\frac{(n-k)\times(n-k-1)}{2}$ 条边，可知能贡献 $2^{\frac{(n-k)\times(n-k-1)}{2}}$ 种方案。注意到①选择 $k$ 个节点的方案有 $C_{n-1}^{k-1}$ 种，故最终转移方程为 $\displaystyle ans_n=2^{\frac {n\times(n-1)}{2}}-\sum_{k=1}^{n-1}\left(C_{n-1}^{k-1}\times ans_k\times 2^{\frac{(n-k)\times(n-k-1)}{2}}\right)$。

按照转移方程实现即可，时间复杂度 $\Theta(n^2)$，不要忘记取模，且模数需要用 long long 存储。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1000 + 9, mod = 1004535809LL;
int n, pw[maxn * maxn], c[maxn][maxn], f[maxn];
signed main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> n, pw[0] = 1;
	for (int i = 1; i <= n * n; i++)
		pw[i] = pw[i - 1] * 2 % mod; // O(n) 预处理出 2 的若干次方
	for (int i = 0; i <= n; i++)	 // 预处理出组合数
		for (int j = 0; j <= i; j++)
			if (!j)
				c[i][j] = 1;
			else
				c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
	for (int i = 1; i <= n; i++)
	{
		f[i] = pw[i * (i - 1) / 2];
		for (int j = 1; j < i; j++)
			f[i] = (f[i] - f[j] * c[i - 1][j - 1] % mod * pw[(i - j) * (i - j - 1) / 2] % mod + mod) % mod;
	}
	cout << f[n];
}