Connected Graph

C++(g++ 7.5.0) 解法, 执行用时: 27ms, 内存消耗: 664K, 提交时间: 2022-08-12 17:44:05

#include<bits/stdc++.h>
using namespace std;
int n;
struct A{
    int a[600],len;
    A operator/(const int x)const{
        A ans;
        memset(ans.a,0,sizeof(ans.a));
        ans.len=0;
        int num=0;
        for(int i=len;i;i--){num=num*10+a[i];ans.a[i]=num/x;num%=x;if(!ans.len&&ans.a[i])ans.len=i;}
        return ans;
    }
    A operator+(const A x)const{
        A ans;
        memset(ans.a,0,sizeof(ans.a));
        for(int i=1;i<=max(len,x.len);i++)ans.a[i]+=a[i]+x.a[i],ans.a[i+1]=ans.a[i]/10,ans.a[i]%=10;
        ans.len=max(len,x.len);
        if(ans.a[ans.len+1])ans.len++;
        return ans;
    }
    inline A operator*(const A x)const{
        A ans;
        memset(ans.a,0,sizeof(ans.a));
        for(int i=1;i<=len;i++)for(int j=1;j<=x.len;j++)ans.a[i+j-1]+=a[i]*x.a[j],ans.a[i+j]+=ans.a[i+j-1]/10,ans.a[i+j-1]%=10;
        ans.len=len+x.len-1;
        if (ans.a[ans.len+1]) ++ans.len;
        return ans;
    }
}f[60],p[60];
A C(int x,int y){
    A ans;
    ans.len=ans.a[1]=1;
    for(int i=y,j=1;j<=x;i--,j++){
        int t=i;
        A tmp;
        tmp.len=0;
        while(t)tmp.a[++tmp.len]=t%10,t/=10;
        ans=ans*tmp/j;
    }
    return ans;
}
void print(A x){for(int i=x.len;i;i--)cout<<x.a[i];;cout<<"\n";}
int main() {
    for(int i=1;i<51;i++){long long t=(1ll<<i)-1;while(t)p[i].a[++p[i].len]=t%10,t/=10;}
    f[1].len=f[2].len=f[1].a[1]=f[2].a[1]=1;
    for(int i=3;i<51;i++)for(int j=1;j<i;j++)f[i]=f[i]+C(j-1,i-2)*f[j]*f[i-j]*p[j];
    while(cin>>n&&n)print(f[n]);
    return 0;
}

C++ 解法, 执行用时: 25ms, 内存消耗: 684K, 提交时间: 2022-02-06 10:11:06

#include<bits/stdc++.h>
using namespace std;
int n;
struct A{
	int a[600],len;
	A operator/(const int x)const{
		A ans;
		memset(ans.a,0,sizeof(ans.a));
		ans.len=0;
		int num=0;
		for(int i=len;i;i--){num=num*10+a[i];ans.a[i]=num/x;num%=x;if(!ans.len&&ans.a[i])ans.len=i;}
		return ans;
	}
	A operator+(const A x)const{
		A ans;
		memset(ans.a,0,sizeof(ans.a));
		for(int i=1;i<=max(len,x.len);i++)ans.a[i]+=a[i]+x.a[i],ans.a[i+1]=ans.a[i]/10,ans.a[i]%=10;
		ans.len=max(len,x.len);
		if(ans.a[ans.len+1])ans.len++;
		return ans;
	}
	inline A operator*(const A x)const{
		A ans;
		memset(ans.a,0,sizeof(ans.a));
		for(int i=1;i<=len;i++)for(int j=1;j<=x.len;j++)ans.a[i+j-1]+=a[i]*x.a[j],ans.a[i+j]+=ans.a[i+j-1]/10,ans.a[i+j-1]%=10;
		ans.len=len+x.len-1;
		if (ans.a[ans.len+1]) ++ans.len;
		return ans;
	}
}f[60],p[60];
A C(int x,int y){
	A ans;
	ans.len=ans.a[1]=1;
	for(int i=y,j=1;j<=x;i--,j++){
		int t=i;
		A tmp;
		tmp.len=0;
		while(t)tmp.a[++tmp.len]=t%10,t/=10;
		ans=ans*tmp/j;
	}
	return ans;
}
void print(A x){for(int i=x.len;i;i--)cout<<x.a[i];;cout<<"\n";}
int main() {
	for(int i=1;i<51;i++){long long t=(1ll<<i)-1;while(t)p[i].a[++p[i].len]=t%10,t/=10;}
	f[1].len=f[2].len=f[1].a[1]=f[2].a[1]=1;
	for(int i=3;i<51;i++)for(int j=1;j<i;j++)f[i]=f[i]+C(j-1,i-2)*f[j]*f[i-j]*p[j];
	while(cin>>n&&n)print(f[n]);
	return 0;
}

Python3 解法, 执行用时: 59ms, 内存消耗: 4684K, 提交时间: 2022-03-24 22:30:35

import math
c=[[0]]
for i in range(1,51):
    c.append([])
    c[i].append(1)
    for j in range(1,i):
        c[i].append(c[i-1][j-1]+c[i-1][j])
    c[i].append(1)
F=[0,1]
for i in range(2,50+1):
    F.append(int(pow(2,i*(i-1)//2)))
    for j in range(1,i):
        F[i]-=c[i-1][j-1]*F[j]*pow(2,(i-j)*(i-j-1)//2)
while 1:
    n=int(input())
    if n==0:
        break
    print(int(F[n]))

pypy3(pypy3.6.1) 解法, 执行用时: 43ms, 内存消耗: 19268K, 提交时间: 2020-09-16 11:29:45

fact = [1]
for i in range(1,51):
    fact.append(fact[i-1]*i)
def Comb(n,m):
    return fact[n]//fact[m]//fact[n-m]
f=[0]*51
f[1]=1
for i in range(2,51):
    f[i]=2**(i*(i-1)//2)
    for j in range(1,i):
        f[i]-=f[j]*Comb(i-1,j-1)*(2**((i-j)*(i-j-1)//2))
while(1):
    n=int(input())
    if(n):
        print(f[n])
    else:
        break

详情