题目描述
《集合论与图论》这门课程有一道作业题，要求同学们求出{1, 2, 3, 4, 5}的所有满足以 下条件的子集：若 x 在该子集中，则 2x 和 3x 不能在该子集中。
同学们不喜欢这种具有枚举性 质的题目，于是把它变成了以下问题：对于任意一个正整数 n<=100000，如何求出{1, 2,…, n} 的满足上述约束条件的子集的个数（只需输出对 1,000,000,001 取模的结果），现在这个问题就 交给你了。
输入输出格式
输入格式：
只有一行，其中有一个正整数 n，30%的数据满足 n<=20。
输出格式：
仅包含一个正整数，表示{1, 2,…, n}有多少个满足上述约束条件 的子集。
输入输出样例
输入样例#1：
复制4输出样例#1： 复制8【样例解释】有8 个集合满足要求，分别是空集，{1}，{1，4}，{2}，{2，3}，{3}，{3，4}，{4}。对于一个数，我们可以把它分解成$k*2^{i}*3^{j}$每个k(不含2，3的因数)可以单独考虑，答案是所有k方案的积即考虑$k*2^i*3^j<=n$的方案构造一个矩阵： k 3k 9k 27k2k 6k 18k 54k4k 12k 36k 108k令f[i][S]表示当前选到2^i，行状态为SS第j位为1表示选了2^i*3^j首先根据题意，S相邻2位不能为1然后转移时前面的状态S’要满足与S&S’=0
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,Log2[],Log3[],pw2[],pw3[];
int ans,Mod=1e9+,f[][],s[],cnt,p,q,sum;
int main()
{int i,j,k,l;
cin>>n;
Log2[]=;
for (i=;i<=n;i++)
Log2[i]=Log2[i/]+;
Log3[]=;
for (i=;i<=n;i++)
Log3[i]=Log3[i/]+;
pw2[]=;
for (i=;i<=;i++)
pw2[i]=pw2[i-]*;
pw3[]=;
for (i=;i<=;i++)
pw3[i]=pw3[i-]*;
for (i=;i<pw2[];i++)
{
s[i]=;
for (j=;j<=;j++)
if ((i&pw2[j])&&(i&pw2[j+])) s[i]=;
}
ans=;
for (i=;i<=n;i++)
if (i%&&i%)
{
k=;
q=Log3[n/i]+;
for (j=;j<pw2[q];j++)
f[][j]=s[j];
while (i*pw2[k]<=n)
{
p=Log3[n/(i*pw2[k])]+;
for (j=;j<pw2[p];j++)
if (s[j])
{
f[k][j]=;
for (l=;l<pw2[q];l++)
if (s[l]&&((j&l)==))
{
f[k][j]=(f[k][j]+f[k-][l])%Mod;
}
}
else f[k][j]=;
q=p;
k++;
}
sum=;
for (j=;j<pw2[q];j++)
sum=(sum+f[k-][j])%Mod;
ans=(1ll*ans*sum)%Mod;
}
cout<<ans;
}
