我们先建一个矩阵：
\(\begin{bmatrix}
1 &2 & 4 & 8 & 16 & 32\\
3 & 6 & 12 & 24 & 48 & 96\\
9 & 18 & 36 & 72 & 144 & 288\\
27 & 54 & 108 & 216 & 432 & 864
\end{bmatrix}\)
横排的每个数是左侧的两倍，竖排的每个数是上侧的三倍。
那么不能有 \(2\) 或 \(3\) 倍关系就是矩阵上选出不相邻的点（相邻在这里指四连通），用状压 dp 即可。
由于 \(n\le 10^5\)，所以我们的矩阵不会太大。
对于每一个不在矩阵中的数开一个形如上方的矩阵，这样的数不会太多。
点击查看代码
#include<bits/stdc++.h>
#define int ll
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define inn(i,n,a) For(i,1,n) a[i]=read();
#define ll long long
#define i128 __int128
using namespace std;
inline int read() {
int xx= 0;int f= 1;
char c = getchar();
while(c<'0'||c>'9') {
if(c=='-') f= -1;
c= getchar();
}
while(c>='0'&&c<='9') {
xx= (xx<<1)+(xx<<3)+(c^48);
c= getchar();
}
return xx*f;
}
#define maxn 100050
const int mod = 1e9+1;
int n,m;
bool vis[maxn];
int a[19][13];
int f[2][(1<<12)+514];
int siz[19],lim[19];
int use[(1<<18)];
void init(int x) {
For(i,1,18) {
if(i==1) a[i][1]=x;
else a[i][1]=a[i-1][1]<<1;
if(a[i][1]>n) break;
m=i,siz[i]=1,vis[a[i][1]]=1;
For(j,2,18) {
a[i][j]=(a[i][j-1]<<1)+a[i][j-1];
if(a[i][j]>n) break;
siz[i]=j,vis[a[i][j]]=1;
}
lim[i]=(1<<siz[i])-1;
}
}
int work() {
i128 res=0;
For(i,0,lim[1]) f[1][i]=use[i];
For(i,2,m) For(j,0,lim[i]) {
if(!use[j]) continue;
f[i&1][j]=0;
For(k,0,lim[i-1]) {
if(use[k]&&!(k&j))
f[i&1][j]+=f[(i-1)&1][k];
}
if(f[i&1][j]>mod) f[i&1][j]%=mod;
}
For(i,0,lim[m]) {
res+=f[m&1][i];
}
return res%mod;
}
void works() {
in1(n);
int ans=1;
For(i,1,n) if(!vis[i]) {
init(i);
ans=ans*work()%mod;
}
cout<<ans<<'\n';
For(i,1,n) vis[i]=0;
}
signed main() {
For(i,0,(1<<12)-1) use[i]=(i&(i<<1))?0:1;
works();
}