求n个点的无向联通图数量，\(n\leq 50\)。
解
直接无向联通图做状态等于是以边点做考虑，难以去重，考虑联通对立面即不联通。
不难求出n个点的总方案数为\(2^{\frac{n\times (n-1)}{2}}\)，所以设\(f_i\)表示n个点的无向联通图个数，因此我们有
\[f_i=2^{\frac{n(n-1)}{2}}-\sum_{j=1}^{i-1}f_jC_i^j2^{\frac{(i-j)(i-j-1)}{2}}
\]
\]
但是这样的转移存在重复，考虑特殊化去重，注意到如果这张图不合法，可以等价于任何一个联通图不合法，于是可以强制让点1不合法，因此有
\[f_i=2^{\frac{n(n-1)}{2}}-\sum_{j=1}^{i-1}f_jC_{i-1}^{j-1}2^{\frac{(i-j)(i-j-1)}{2}}
\]
\]
边界：\(f_1=1\)
答案：\(f_n\)
时间复杂度显然\(O(n^2)\)，但是高精度占去大量时间。
参考代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
#define ll long long
using namespace std;
struct lll{
int num[1001];
lll(){num[0]=1;}
il void clear(){
memset(num,0,sizeof(num)),num[0]=1;
}
il void read(){
string s;cin>>s,num[0]=s.size();
for(ri int i(1);i<=num[0];++i)
num[i]=s[num[0]-i];
}
il void print(){
for(ri int i(num[0]);i;--i)putchar(num[i]+48);
}
il void operator=(string s){
num[0]=s.size();
for(ri int i(1);i<=s.size();++i)
num[i]=num[s.size()-i];
}
il lll operator+(lll x){
lll y;y.clear();ri int i;
for(i=1;i<=num[0]||i<=x.num[0];++i){
y.num[i]+=num[i]+x.num[i];
if(y.num[i]>9)++y.num[i+1],y.num[i]-=10;
}y.num[0]=i;
while(!y.num[y.num[0]]&&y.num[0]>1)--y.num[0];
return y;
}
il lll operator-(lll x){
lll y;y.clear();ri int i;
for(i=1;i<=num[0];++i){
y.num[i]+=num[i]-x.num[i];
if(y.num[i]<0)--y.num[i+1],y.num[i]+=10;
}y.num[0]=i;
while(!y.num[y.num[0]]&&y.num[0]>1)--y.num[0];
return y;
}
il lll operator*(lll x){
lll y;y.clear();ri int i,j,k;
for(i=1;i<=num[0];++i){
k=0;
for(j=1;j<=x.num[0];++j)
y.num[i+j-1]+=num[i]*x.num[j]+k,
k=y.num[i+j-1]/10,y.num[i+j-1]%=10;
y.num[i+x.num[0]]+=k;
}y.num[0]=i+j;
while(!y.num[y.num[0]]&&y.num[0]>1)--y.num[0];
return y;
}
}p2[2501],c[51][51],dp[51];
int main(){
int n,i,j;p2[0]="1";
for(i=1;i<=2500;++i)p2[i]=p2[i-1]+p2[i-1];
for(i=0;i<=50;++i){c[i][0]="1";
for(j=1;j<=i;++j)
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
while(scanf("%d",&n),n){
memset(dp,0,sizeof(dp)),dp[1]="1";
for(i=2;i<=n;++i){
dp[i]=p2[i*(i-1)>>1];
for(j=1;j<i;++j)
dp[i]=dp[i]-dp[j]*c[i-1][j-1]*p2[(i-j)*(i-1-j)>>1];
}dp[n].print(),putchar('\n');
}
return 0;
}