带标号的连通图计数
题目描述：
带标号的连通图计数。统计有n ( n<=50)个顶点的连通图有多少个。图的顶点有编号。例如n=3时有4个不同的图， n=4时有38个图；n=5,6时分别有728，26704个图
分析：
设f（n）为所求答案，g（n）为由n个顶点的非连通图，则f（n）+g（n）=h（n）=2n(n-1)/2 。
g（n）可以这样计算：先考虑1所在连通分量包含哪些顶点。假设1所在连通分量有k(k<n)个顶点，就有C（n-1，k-1）中取法，剩下的n-k的顶点随便共有h（n-k）中方法，根据加法原理
初始状态
f（0）=1；算是一个空图
f（1）=1，h（1）=1，g（1）=0
因为数据较大，所以涉及到高精度乘法减法加法。
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<string>
#include<iostream>
#include<iomanip>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxn=51;
const int branch=26;
const int inf=0x3f3f3f3f;
const int MOD=1e9+7;
struct bign{
ll a[500];//储存 低位到高位 10000进制
int len;//代表有效长度
bign()
{
mset(a,0);
len=1;
}
bign(ll n)
{
mset(a,0);
len=1;
a[0]=n%10000;
n/=10000;
while(n)
{
a[len++]=n%10000;
n/=10000;
}
}
bign operator + (const bign &k)
{
bign ans;
ans.len=max(len,k.len);
for(int i=0;i<ans.len;++i)
{
ans.a[i]+=a[i]+k.a[i];
ans.a[i+1]+=ans.a[i]/10000;
ans.a[i]%=10000;
}
if(ans.a[ans.len]>0)
{
ans.len++;
}
return ans;
}
bign(const bign &aa)
{
len=aa.len;
mset(a,0);
for(int i=0;i<len;++i)
a[i]=aa.a[i];
}
bign operator = (const bign &aa)
{
len=aa.len;
mset(a,0);
for(int i=0;i<len;++i)
a[i]=aa.a[i];
return *this;
}
bign operator *(ll k)//数乘 只支持正整数
{
bign ans;
ans.len=len;
for(int i=0;i<len;++i)
{
ans.a[i]+=a[i]*k;// 加上进位和数乘
ans.a[i+1]+=ans.a[i]/10000;//进位操作
ans.a[i]=ans.a[i]%10000;//
}
while(ans.a[ans.len])
{
ans.a[ans.len+1]+=ans.a[ans.len]/10000;
ans.a[ans.len]%=10000;
ans.len++;
}
return ans;
}
bign operator *(const bign n)//高精度乘法
{
bign ans;
ans.len=len+n.len;
for(int i=0;i<len;++i)
for(int j=0;j<n.len;++j)
ans.a[i+j]+=a[i]*n.a[j];
for(int i=0;i<ans.len;++i)
{
ans.a[i+1]+=ans.a[i]/10000;
ans.a[i]=ans.a[i]%10000;
}
while(!ans.a[ans.len-1]&&ans.len>1)
{
ans.len--;
}
return ans;
}
bign operator - (const bign n)//大数减小数
{
bign ans;
ans=n;
ans=ans*(ll(-1));
ans=ans+*this;
for(int i=0;i<ans.len;++i)
{
if(ans.a[i]<0)
{
ans.a[i]+=10000;
ans.a[i+1]--;
}
}
while(ans.a[ans.len-1]==0&&ans.len>1)
{
ans.len--;
}
return ans;
}
void out()
{
/*先输出最高位*/
/*底位按5个长度输出*/
cout<<a[len-1];
for(int i=len-2;i>=0;--i)
{
cout<<setw(4)<<setfill('0')<<a[i];
// printf("%04llu",a[i]);
}
printf("
");
}
};
bign h[maxn],f[maxn],g[maxn];//分别表示 n个节点图的个数 连通图的个数 非连通图的个数
ll C[maxn][maxn];
void Preprocess()
{
h[1]=bign(1);
for(int i=2;i<=50;++i)
{
h[i]=h[i-1];
for(int k=0;k<i-1;++k)
h[i]=h[i]*2;
}
C[0][0]=1;
for(int i=1;i<=50;++i)
{
C[i][0]=C[i][i]=1;
for(int j=1;j<i;++j)
C[i][j]=C[i-1][j-1]+C[i-1][j];
}
//求完h[50] 和排列组合运算
f[0]=bign(1);
f[1]=bign(1);//g(1)=bign(0)
for(int i=2;i<=50;++i)
{
g[i]=bign(0);
for(int k=1;k<i;++k)
{
g[i]=g[i]+f[k]*C[i-1][k-1]*h[i-k];
}
f[i]=h[i]-g[i];
}
}
int main()
{
int n;
Preprocess();
while(~scanf("%d",&n))//切记 n<=50
{
f[n].out();
}
}