题目描述
《集合论与图论》这门课程有一道作业题，要求同学们求出{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}。
题解:
这题很有意思,首先你得想到画出所有的倍数表,然后再发现规律......
如:
1 3 9
2 6 18
4 12 36
8 24 72
16 48 144
32 96 288
大概是这样横着是乘三,竖着乘二
这样画出来就发现题目要求的就是所选的数不能相邻......且行列都是log的所以可以直接状压dp
设f[i][j] 表示前i行,第j行状态为j 那么判断一下直接转移就是了
注意状压的要是乘三的,状态比乘二的少很多.
做到这样发现这个矩阵并没有包括所有的数字
所以还需要找到一个没出现的数继续构造矩阵并dp统计
如没出现的7
7 21 63.....
14 42 126...
继续构造即可
最后答案统计时相乘即可
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
using namespace std;
typedef long long ll;
const int N=<<,M=,mod=;
int f[][N],lim,sz[N];
bool vis[M];
il int deal(int sta){
int n=,s=sta,t=sta;
for(int i=;i<=;i++){
if(s>lim){
n=i-;
break;
}
vis[s]=true;t=s;
sz[i]=;
for(int j=;j<=;j++){
if(t>lim)break;
vis[t]=true;
sz[i]++;
t=(t<<)+t;
}
s<<=;
}
f[][]=;
for(int i=;i<=n;i++){
int tot=(<<sz[i])-;
for(RG int j=;j<=tot;j++){
if((j<<)&j)continue;
int tmp=(<<sz[i-])-;
f[i][j]=;
for(RG int k=;k<=tmp;k++){
if((k<<)&k)continue;
if(j&k)continue;
f[i][j]+=f[i-][k];
if(f[i][j]>=mod)f[i][j]-=mod;
}
}
}
int tot=(<<sz[n])-,ret=;
for(RG int j=;j<=tot;j++){
if(j&(j<<))continue;
ret+=f[n][j];if(ret>=mod)ret-=mod;
}
return ret;
}
void work()
{
scanf("%d",&lim);
ll ans=;
for(int i=;i<=lim;i++){
if(!vis[i])
ans*=deal(i),ans%=mod;
}
printf("%lld\n",ans);
} int main()
{
work();
return ;
}