题意:求出\(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;
}

思路:

令\(f[i][j]\)表示将\(i\)个数划分为\(j\)个集合的方案数.

则有递推式:

\[f[i][j]=f[i-1][j]*j+f[i-1][j-1]\]

于是\(ans(n)=\sum_{i=1}^{n}f[n][i]*fac(i)\)

数据范围小,随便写写.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
static const int mod=1e4;
struct Int{
    int d[100],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){
            d[i]+=B.d[i];
            if(d[i]>=mod)d[i+1]+=d[i]/mod,d[i]%=mod;
        }if(d[l])l++;
    }
    inline void operator*=(const int&x){
        int p=0;
        for(int i=0;i<l;++i)d[i]=(p+=d[i]*x)%mod,p/=mod;
        if(p)d[l++]=p;
    }
    inline Int 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);
        return C;
    }
    inline void output(){
        printf("%d",d[l-1]);for(int i=l-2;i>=0;--i)printf("%04d",d[i]);
    }
};
 
Int f[51][51],fac[51],res[51];
 
int main(){
    int i,j;
    for(fac[0]=1,fac[1]=1,i=2;i<=50;++i)fac[i]=fac[i-1],fac[i]*=i;
    for(i=1;i<=50;++i){
        f[i][1]=1,f[i][i]=1;
        for(j=2;j<i;++j)f[i][j]=f[i-1][j],f[i][j]*=j,f[i][j]+=f[i-1][j-1];
    }
     
    for(i=1;i<=50;++i)for(j=1;j<=i;++j)res[i]+=f[i][j]*fac[j];
     
    int T;scanf("%d",&T);
    int x;while(T--)scanf("%d",&x),res[x].output(),puts("");
     
    return 0;
}