# Connected Graph

2019/06/07 07:53

Connected Graph

### 解

$f_i=2^{\frac{n(n-1)}{2}}-\sum_{j=1}^{i-1}f_jC_i^j2^{\frac{(i-j)(i-j-1)}{2}}$

$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}}$

#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;
}
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;
}


0
0 收藏

0 评论
0 收藏
0