题解：P10982 Connected Graph

wangbinfeng · 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];
}