记录编号	273029	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 有标号的DAG计数 I	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	1.211 s
提交时间	2016-06-18 21:25:31	内存使用	191.43 MiB

#include<stdio.h>
#define mod 10007
int n,c[5010][5010],f[5010],pow2[25000010];
inline int POW(int x,int y){
	if(x<0)x+=mod;
	for(int z=1;;x=x*x%mod,y>>=1)
	    if(y&1)z=z*x%mod;
	    else if(!y)return z;
}
int main(){
	freopen("DAG.in","r",stdin);
	freopen("DAG.out","w",stdout);
	scanf("%d",&n),pow2[0]=1;
	for(int i=1,r=n*n;i<=r;++i){
		pow2[i]=pow2[i-1]*2;
		if(pow2[i]>=mod)pow2[i]-=mod;
	}
	for(int i=0;i<=n;++i)c[i][0]=1;
	for(int i=1;i<=n;++i)
	    for(int j=1;j<=i;++j){
			c[i][j]=c[i-1][j]+c[i-1][j-1];
			if(c[i][j]>=mod)c[i][j]-=mod;
	    }
	f[0]=1;
	for(int i=1;i<=n;++i)
	    for(int j=1,w=1;j<=i;w*=-1,++j)
			f[i]=(f[i]+w*c[i][j]*pow2[j*(i-j)]%mod*f[i-j])%mod;
	if(f[n]<0)f[n]+=mod;
	printf("%d",f[n]);
	//while(1);
}