主要思路

这道题的计数方程和思想非常有趣，下面开始进行分析。

我们设\(F[i]\)为点数为\(i\)时的无向连通图种类。我们可以尝试容斥：\(n\)个点的无向图种类有\(2^{\frac{n(n-1)}{2}}\)，我们可以枚举\(k\)，删去大小为\(k\)的连通块来保持连通性。因为本题要求点标号，所以这些连通块的种类为：

\[\sum_{k=1}^{i-1}(F[k]*C_{i-1}^{j-1}*2^{\frac{(i-k)(i-k-1)}{2}})\]

其中，\(F[k]\)为连通块大小为\(k\)时的连通块个数，然后\(C_{i-1}^{j-1}\)是标号对答案的贡献，之后另一个残余块的种类为\(2^{\frac{(i-k)(i-k-1)}{2}}\)，乘起来即可。

这道题的加强版需要使用 NTT 和卷积的知识：BZOJ 3456:城市规划题解

代码

// POJ1737.cpp
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int MAX_N = 60;
ll f[MAX_N], C[MAX_N][MAX_N], tmp;
int main()
{
    C[1][0] = C[1][1] = 1;
    for (int i = 2; i < MAX_N; i++)
    {
        C[i][0] = 1;
        for (int j = 1; j < MAX_N; j++)
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
    f[1] = 1;
    for (int i = 2; i < MAX_N; i++)
    {
        f[i] = (1 << ((i * (i - 1)) >> 1));
        for (int j = 1; j < i; j++)
            f[i] -= f[j] * C[i - 1][j - 1] * (1 << (((i - j) * (i - j - 1)) >> 1));
    }
    while (~scanf("%d", &tmp) && tmp != 0)
        printf("%lld\n", f[tmp]);
    return 0;
}