题意:求出\(n\)个点的无向完全图的子图中有多少个是连通图.
思路:
令\(f_i\)表示\(i\)个点时的连通图个数.
考虑如果图不连通,那么必定存在某些点与\(1\)号点不在一个连通分量中.
如果我们要计算\(f_n\),那就枚举和\(1\)号点在一个连通分量中中的有几个点,那么与这个连通分量无关的点的集合内部就可以随便连边了.这种情况下我们要考虑是哪些点和\(1\)号点在一个连通分量中,另外还要乘上这个连通分量的内部连边数.这个是之前已经搞出来的.
随后利用高精度预处理一下直接输出.
#include<cstdio> #include<cstring> #include<cctype> #include<iostream> #include<algorithm> using namespace std; static const int mod=1e4; struct Int{ int d[500],l; Int():l(1){memset(d,0,sizeof d);} inline void operator=(const int&x){memset(d,0,sizeof d),l=1,d[0]=x;} inline void operator+=(const Int&B){ l=l>B.l?l:B.l;for(int i=0;i<l;++i)if((d[i]+=B.d[i])>=mod)d[i]-=mod,d[i+1]++; if(d[l])l++; } inline void operator*=(const Int&B){ Int C; for(int i=0;i<l;++i)for(int j=0;j<B.l;++j){ C.d[i+j]+=d[i]*B.d[j];if(C.d[i+j]>=mod)C.d[i+j+1]+=C.d[i+j]/mod,C.d[i+j]%=mod; } for(C.l=l+B.l+1;!C.d[C.l-1];--C.l); *this=C; } inline void operator-=(const Int&B){ for(int i=0;i<B.l;++i){if((d[i]-=B.d[i])<0){d[i]+=mod,d[i+1]--;}} while(l>1&&d[l-1]==0)--l; } Int operator*(const Int&B)const{Int r=*this;r*=B;return r;} inline void print(){ printf("%d",d[l-1]);for(int i=l-2;i>=0;--i)printf("%04d",d[i]); } }; Int pow(int y){ Int t,r;for(t=2,r=1;y;y>>=1,t*=t)if(y&1)r*=t;return r; } Int C[51][51]; inline void Init(){ C[0][0]=1,C[1][0]=1,C[1][1]=1; for(int i=2;i<=50;++i){ C[i][0]=1,C[i][i]=1; for(int j=1;j<i;++j)C[i][j]=C[i-1][j-1],C[i][j]+=C[i-1][j]; } } Int f[51]; int main(){ f[1]=1;Init(); for(int i=2;i<=50;++i){ f[i]=pow(i*(i-1)>>1); for(int j=0;j<i-1;++j)f[i]-=C[i-1][j]*f[j+1]*pow((i-j-1)*(i-j-2)>>1); } int x;while(scanf("%d",&x)&&x)f[x].print(),puts(""); return 0; }