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 Input4Sample Output8【样例解释】有8 个集合满足要求，分别是空集，{1}，{1，4}，{2}，{2，3}，{3}，{3，4}，{4}。
一开始是这样想的，不能一起选的连一条边然后在图上dp
1
2 3
4 6 9
8 12 18
但是好像不行
看了题解才知道
我们把图弄成这样（往下走是*2，往右走是*3，就变成相邻的数不能选，可以用状压dp）
1 3 9
2 6 18
4 12 36
8 24 72
............
但是要注意这个时候我们并没有把所有的数都考虑到，比如5的倍数，所以我们枚举左上角的数，然后用乘法定理
具体做法是用一个flag存这个数是否考虑过，没考虑就把他当做左上角的数做一遍
1 const 2 h=1000000001; 3 maxn=100010; 4 var 5 f:array[0..18,0..2048]of longint; 6 num:array[0..18]of longint; 7 flag:array[0..maxn]of boolean; 8 n:longint; 9 ans:int64;10 11 function get(x:longint):int64;12 var13 i,j,k,s,w:longint;14 begin15 get:=0;16 s:=x;17 w:=x;18 flag[x]:=true;19 num[1]:=1;20 while w*3<=n do21 begin22 w:=w*3;23 flag[w]:=true;24 inc(num[1]);25 end;26 for j:=0 to 1<<(num[1])-1 do27 if j and(j<<1)=0 then f[1,j]:=1;28 i:=1;29 while s*2<=n do30 begin31 inc(i);32 s:=s*2;33 w:=s;34 num[i]:=1;35 flag[w]:=true;36 while w*3<=n do37 begin38 w:=w*3;39 flag[w]:=true;40 inc(num[i]);41 end;42 for j:=0 to 1<<(num[i])-1 do43 f[i,j]:=0;44 for j:=0 to 1<<(num[i])-1 do45 for k:=0 to 1<<(num[i-1])-1 do46 if (j and(j<<1)=0) and (j and k=0) then f[i,j]:=(f[i,j]+f[i-1,k])mod h;47 end;48 for j:=0 to 1<<(num[i])-1 do49 inc(get,f[i,j]);50 end;51 52 procedure main;53 var54 i:longint;55 begin56 read(n);57 ans:=1;58 for i:=1 to n do59 if flag[i]=false then ans:=(ans*get(i))mod h;60 writeln(ans);61 end;62 63 begin64 main;65 end.