1344. [HNOI2012]集合选数
★★   输入文件：
   bzoj_2734.in   输出文件：
   bzoj_2734.out   
   简单对比
时间限制：10 s   内存限制：128 MB
  
  

   
【题目描述】
   

    
《集合论与图论》这门课程有一道作业题，要求同学们求出{1, 2, 3, 4, 5}的所有满足以 下条件的子集：若 x 在该子集中，则 2x 和 3x 不能在该子集中。同学们不喜欢这种具有枚举性 质的题目，于是把它变成了以下问题：对于任意一个正整数 n≤100000，如何求出{1, 2,..., n} 的满足上述约束条件的子集的个数（只需输出对 1,000,000,001 取模的结果），现在这个问题就 交给你了。 
   
   
【输入格式】
   

    
 只有一行，其中有一个正整数 n，30%的数据满足 n≤20。 
   
   
【输出格式】
   

    
  仅包含一个正整数，表示{1, 2,..., n}有多少个满足上述约束条件 的子集。 
   
   
【样例输入】
   
 4                        
   
【样例输出】
   
8【样例解释】 有8 个集合满足要求，分别是空集，{1}，{1，4}，{2}，{2，3}，{3}，{3，4}，{4}。 
  

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#define V   100050
#define INF 1115006
#define S 1<<10+1
//typedef long long LL;
#define M 1000000001
#define ll long long
using namespace std;
ll ans=1;
int n;
int a[20][20],b[20],f[20][2049];
bool mark[100005];
inline int calc(int x)
{memset(b,0,sizeof(b));a[1][1]=x;int bb;for (int i=2;i<=18;i++)if (a[i-1][1]*2<=n) a[i][1]=a[i-1][1]*2; else{a[i][1]=n+1;bb=i;break;}//for (int i=1;i<=bb;i++)for (int j=2;j<=11;j++)if (a[i][j-1]*3<=n) a[i][j]=a[i][j-1]*3; else{ a[i][j]=n+1;break;}for (int i=1;i<=bb;i++)for (int j=1;j<=11;j++)if (a[i][j]<=n){b[i]+=(1<<(j-1));mark[a[i][j]]=1;}else{break;}memset(f,0,sizeof(f));f[0][0]=1;for (int i=0;i<18;i++)    for (int j=0;j<=b[i];j++)if (f[i][j])for (int k=0;k<=b[i+1];k++)if (((j&k)==0)&&((k&(k>>1))==0))f[i+1][k]=(f[i][j]+f[i+1][k])%M;return f[18][0];
}
int main()
{freopen("bzoj_2734.in","r",stdin);freopen("bzoj_2734.out","w",stdout);//reopen("in.txt","r",stdin);freopen("out.txt","w",stdout);scanf("%d",&n);for (int i=1;i<=n;i++)if (!mark[i]) ans=(ans*calc(i))%M;printf("%d",ans%M);return 0;
}