标签：状压DP
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
4
Sample Output
8
【样例解释】
有8 个集合满足要求，分别是空集，{1}，{1，4}，{2}，{2，3}，{3}，{3，4}，{4}。
题意：定义一个符合要求的集合为a与2a,a与3a不能同时存在，{x|1<=x<=n}的所有子集中有多少个符合要求
可以列出来一个奇奇怪怪的矩阵
1 3 9
2 6 18
4 12 36…….
这个矩阵向右*2，向下*3，矩阵中任何两个相邻的数的x倍都不能出现在同一个集合中
可以将方案数状压DP，最后将方案数用乘法原理相乘就可以了
F[i][j]表示前i行且第i行状态为j时的方案数，转化为状压经典裸题
好妙的一道题呐
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
const LL mod=1000000001;
const int maxn=20;
LL bin[maxn],n,a[maxn][maxn],b[maxn],f[maxn][1<<12],ans=1;
bool mark[100006];LL cal(LL x){mem(b,0);a[1][1]=x;rep(i,2,18)if(a[i-1][1]*2<=n)a[i][1]=a[i-1][1]*2;else a[i][1]=n+1;rep(i,1,18)rep(j,2,11)if(a[i][j-1]*3<=n)a[i][j]=a[i][j-1]*3;else a[i][j]=n+1;//扩展n以内的x矩阵 rep(i,1,18)rep(j,1,11)if(a[i][j]<=n)b[i]+=bin[j-1],mark[a[i][j]]=1;rep(i,0,18)rep(x,0,b[i])f[i][x]=0;f[0][0]=1;rep(i,0,17)rep(x,0,b[i])if(f[i][x])rep(y,0,b[i+1])if(((x&y)==0)&&((y&(y>>1))==0))f[i+1][y]=(f[i+1][y]+f[i][x])%mod;return f[18][0];
}
int main()
{scanf("%lld",&n);bin[0]=1;rep(i,1,19)bin[i]=bin[i-1]<<1;rep(i,1,n)if(!mark[i])ans=(ans*cal(i))%mod;//mark[i]表示这个数是否已经在集合内 printf("%lld\n",ans);return 0;
}