【题目大意】
给定一个数$n$，从集合$\{1,2,…,n\}$中选数，求满足“如果$x$选了，就不能选$2x$和$3x$”的子集个数(包括空集)
【思路分析】
我觉得这题挺妙的，要转化为在矩阵中选数，类似这样的矩阵$\downarrow$
$$\begin{matrix}x&2x&4x&\cdots\\3x&6x&12x&\cdots\\9x&18x&36x&\cdots\\\vdots&\vdots&\vdots\end{matrix}$$
然后你发现要满足题目要求就是在矩阵内不能选相邻的数(不能上下相邻也不能左右相邻)，于是我们就可以愉快地用状压DP求答案啦！
要注意的就是为了保证不漏答案，我们要把$[1,n]$内每一个既不是2的倍数也不是3的倍数的数作为$x$构造矩阵，然后跑一遍状压DP求答案，这样才能涵盖所有的数，最后根据乘法原理就可以求出整道题目的答案了。
详见代码(有注解)
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #define g() getchar() 8 #define rg register 9 #define ll long long 10 #define go(i,a,b) for(rg ll i=a;i<=b;i++) 11 #define back(i,a,b) for(rg ll i=a;i>=b;i--) 12 #define db double 13 #define il inline 14 #define pf printf 15 #define mem(a,b) memset(a,b,sizeof(a)) 16 using namespace std; 17 ll fr(){ 18 ll w=0,q=1; 19 char ch=g(); 20 while(ch<'0'||ch>'9'){ 21 if(ch=='-') q=-1; 22 ch=g(); 23 } 24 while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=g(); 25 return w*q; 26 } 27 const ll mod=1000000001; 28 const int maxn=(1<<18)+1; 29 const int N=100002; 30 ll n,a[20][20],end,lie[20],mx[20],f[20][maxn]; 31 //f[i][j]表示枚举到当前矩阵第i列状态为j的方案数 32 bool ok[maxn]; 33 ll ans=1,as; 34 il void build(rg ll x){ 35 go(i,1,11){ 36 if(i==1) a[i][1]=x; 37 else a[i][1]=a[i-1][1]*3; 38 if(a[i][1]>n) break; 39 end=i,lie[i]=1;//lie[i]记录第i行有多少列 40 go(j,2,18){ 41 a[i][j]=a[i][j-1]<<1; 42 if(a[i][j]>n) break; 43 lie[i]=j; 44 } 45 mx[i]=(1<<lie[i])-1;//mx[i]记录第i行所有状态压缩后的最大值 46 } 47 return; 48 } 49 il void work(rg ll x){ 50 as=0; 51 go(i,0,mx[1]) f[1][i]=ok[i]; 52 go(i,2,end) go(j,0,mx[i]){ 53 if(!ok[j]) continue;//如果这个状态不合法就跳过 54 f[i][j]=0;//这里要手动赋初始值,用memset会T 55 go(k,0,mx[i-1]) 56 if(ok[k]&&((k&j)==0)) f[i][j]=(f[i][j]+f[i-1][k])%mod; 57 //如果上一行的状态合法且与这一行没有选同一列的数,那么就是合法的,加入答案 58 } 59 go(i,0,mx[end]) if(ok[i]) as=(as+f[end][i])%mod; 60 } 61 int main(){ 62 //freopen("","r",stdin); 63 //freopen("","w",stdout); 64 n=fr(); 65 go(i,0,maxn-1) ok[i]=((i<<1)&i)?0:1; 66 //预处理出单个一行每种状态是否满足条件 67 go(i,1,n) 68 if(i%2&&i%3) build(i),work(i),ans=ans*as%mod; 69 //如果这个数既不是2的倍数也不是3的倍数,那就要造矩阵求答案 70 pf("%lld\n",ans); 71 return 0; 72 }