bzoj2734: [HNOI2012]集合选数

Description

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

Input

只有一行，其中有一个正整数 n，30%的数据满足 n≤20。

Output

仅包含一个正整数，表示{1, 2,..., n}有多少个满足上述约束条件的子集。

Sample Input

Sample Output

8

【样例解释】

有8 个集合满足要求，分别是空集，{1}，{1，4}，{2}，{2，3}，{3}，{3，4}，{4}。

题解：

Orz hzwer

链接：http://hzwer.com/5149.html

code：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #define maxn 100005
 7 #define mod 1000000001
 8 using namespace std;
 9 typedef long long int64;
10 char ch;
11 bool ok;
12 void read(int &x){
13     for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=1;
14     for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());
15     if (ok) x=-x;
16 }
17 int n,m,list[12],cnt,sta[2050];
18 bool bo[maxn];
19 int64 f[20][2050],ans;
20 bool check(int s){
21     int last=0;
22     for (;s;s>>=1)
23         if (s&1){if (last) return false;else last=1;}
24         else last=0;
25     return true;
26 }
27 void prepare(){
28     m=(int)ceil((log(n)/log(3)));
29     for (int i=0;i<(1<<m);i++) if (check(i)) sta[++cnt]=i;
30 }
31 int64 calc(int st){
32     memset(list,0,sizeof(list));
33     int lim,dep,last; list[0]=st,bo[st]=1;
34     for (lim=1;1LL*list[lim-1]*3<=n;lim++) list[lim]=list[lim-1]*3,bo[list[lim]]=1;
35     memset(f,0,sizeof(f));
36     for (int i=1;i<=cnt;i++){
37         int s1=sta[i];
38         if (s1>=(1<<lim)) break;
39         f[0][s1]=1;
40     }
41     last=lim;    
42     for (lim=0;1LL*list[lim]*2<=n&&list[lim];lim++) list[lim]*=2,bo[list[lim]]=1;
43     for (dep=0;lim;){
44         dep++;
45         for (int i=1;i<=cnt;i++){
46             int s1=sta[i];
47             if (s1>=(1<<last)) break;
48             for (int j=1;j<=cnt;j++){
49                 int s2=sta[j];
50                 if (s2>=(1<<lim)) break;
51                 if (s1&s2) continue;
52                 f[dep][s2]+=f[dep-1][s1],f[dep][s2]%=mod;
53             }
54         }
55         last=lim;
56         for (lim=0;1LL*list[lim]*2<=n&&list[lim];lim++) list[lim]*=2,bo[list[lim]]=1;
57     }
58     int64 ans=0;
59     for (int i=0;i<(1<<last);i++) ans+=f[dep][i],ans%=mod;
60     return ans;
61 }
62 int main(){
63     read(n),prepare(),ans=1;
64     for (int i=1;i<=n;i++) if (!bo[i]) ans=ans*calc(i)%mod;
65     printf("%lld
",ans);
66     return 0;
67 }