「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;
}
------ 本文结束 ------