记录编号	239115	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 帕秋莉的超级星象图	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	3.440 s
提交时间	2016-03-19 20:03:58	内存使用	149.56 MiB

#include<stdio.h>
#define mod 1000000007
#define ll long long
ll ans,f[5100],g[5100];
int n,C[5100][5100],pow[13100000];
int main(){
	freopen("super_graph.in","r",stdin);
	freopen("super_graph.out","w",stdout);
	scanf("%d",&n);
	C[0][0]=g[1]=g[2]=pow[0]=1;
	for(int i=1;i<=n;++i){
		C[i][0]=1;
	    for(int j=1;j<=n;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
	for(int i=1,R=n*(n-1)>>1;i<=R;++i) pow[i]=(pow[i-1]<<1)%mod;
	for(int i=3;i<=n;++i){
		g[i]=pow[i*(i-1)>>1];
		for(int j=1;j<i;++j)
		    g[i]=(g[i]-(g[j]*C[i-1][j-1]%mod)*pow[(i-j)*(i-j-1)>>1]%mod)%mod;
	}
	for(int i=2;i<=n;++i) g[i]=g[i]*pow[i]%mod;
	f[0]=f[1]=1;
	for(int i=2;i<=n;++i)
	    for(int j=1;j<=i;++j)
	        f[i]=(f[i]+(g[j]*C[i-1][j-1]%mod)*f[i-j])%mod;
	printf("%lld",(f[n]%mod+mod)%mod);
	//while(1);
}