「poj 1737」Connected Graph (DP + 组合数, 无向连通有标号图计数)

poj 1737
题意：给定$n$，求出$n$个点无向连通有标号图的个数

显然设$dp(i)$为$i$个点的无向连通有标号图的个数。
但是并不好直接算出来，所以我们可以先算不连通的，那么相当于求的图是至少有两个连通块。
然后我们通过$1$所在的连通分量来划分，即对当前的$dp(i)$, 枚举$1$所在的连通分量的节点个数$j$，显然有 $C^{j-1}_{i-1}$ 种情况。然后另外$i-j$个点任意构成无向图。所以最后的答案

$$
dp(i)=2^{\frac{i(i-1)}{2}} - \sum_{j=1}^{i-1}dp(j) \times C^{j-1}_{i-1} \times 2^{\frac{(i-j)(i-j+1)}{2}}
$$

转移即可。

1、通过$1$（某点）所在的连通分量来划分在组合数学中划分非常好用。

// 无高精度
#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    LL n, dp[55];

    LL C(LL n, LL m) {
        LL ans = 1ll;
        for (LL i = 1ll; i <= n; ++i) ans *= i;
        for (LL i = 1ll; i <= m; ++i) ans /= i;
        for (LL i = 1ll; i <= n - m; ++i) ans /= i;
        return ans;
    }

    void clean() {
        ms(dp, 0);
    }
    int solve() {
        clean();
        dp[1] = 1ll;
        for (LL i = 2; i <= n; ++i) {
            dp[i] = (1ll << (i * (i - 1ll) / 2ll));
            for (LL j = 1; j < i; ++j) {
                dp[i] -= dp[j] * C(i - 1ll, j - 1ll) * (1 << ((i - j) * (i - j - 1) / 2ll));
            }
        }
        cout << dp[n] << endl;
        return 0;
    }
}
int main() {
    while (scanf("%lld", &flyinthesky::n) == 1 && flyinthesky::n) flyinthesky::solve();
    return 0;
}