记录编号	463795	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012]集合选数	最终得分	100
用户昵称	wumingshi	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2017-10-24 19:39:11	内存使用	2.31 MiB

#include<cstdio>
#include<cstring>
#define N 100005
#define mod 1000000001
int a[1005][500];
int f[2][1000];
bool b[N];
int n,tot,ans=1;
inline void find(int x)
{
	tot=0,a[0][0]=1;
	for(int i=x;i<=n;i<<=1)
	{
		tot++,a[tot][0]=0;
		for(int j=i;j<=n;j*=3)
		  a[tot][0]++,b[j]=1;
		int top=(1<<a[tot][0]);a[tot][0]=0;
		for(int j=0;j<top;j++)
		  if(!(j&(j>>1))) a[tot][++a[tot][0]]=j;
	}
}
inline void dp()
{
	memset(f,0,sizeof(f));
	f[0][1]=1;
	for(int i=1;i<=tot;i++)
	{
		memset(f[i&1],0,sizeof(f[i&1]));
		for(int j=1;j<=a[i-1][0];j++)
		  for(int k=1;k<=a[i][0];k++)
			if(!(a[i-1][j]&a[i][k])) f[i&1][k]=(f[i&1][k]+f[~i&1][j])%mod;
	}
}
inline void solve()
{
	for(int i=1;i<=n;i++)
	  if(!b[i])
	  {
		find(i),dp();
		int tmp=0;
		for(int j=1;j<=a[tot][0];j++)
		  tmp=(tmp+f[tot&1][j])%mod;
		ans=1ll*ans*tmp%mod;
	  }
}
int main()
{
	freopen("bzoj_2734.in","r",stdin);
	freopen("bzoj_2734.out","w",stdout);
	scanf("%d",&n);
	solve();
	printf("%d",ans);
	return 0;
}