传送门

这个转化好仙啊。

看到约束就想到把$x$和$2x,3x$连边，然后会形成一个图：

看起来非常熟悉（图都是从那搬来的，所以不要在意编号问题），一副不可做的样子。

换种转化方式：

搞一个矩阵，左上角定一个初始值，其他元素都是其左边元素乘$2$或者上面元素乘$3$（这俩是相等的）。

大概这样：

1 2 4 8 ...
3 6 12 24 ...
9 18 36 72 ...
...

这个约束条件就成了在矩阵中选取若干个互不相邻的元素。

矩阵列数是$\log_2 n$的，行数是$\log_3 n$的，直接状压$DP$。

一个问题在于有的元素在矩阵中未出现过。需要从$1$枚举到$n$，每次$DP$时标记矩阵中的元素，访问到未被标记的元素就以它为初始值做$DP$。根据乘法原理全乘起来就是答案。

复杂度看起来挺玄学的，不过感性分析一波应该很小。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 100005
#define inf 0x3f3f3f3f

const int mod = 1e9 + 1;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int f[2][1<<11],cnt[20],n;
bool bad[1<<11],vis[maxn];
int solve(int base){
    memset(cnt,0,sizeof cnt);
    memset(f,0,sizeof f);
    int len,ans=0;
    for(len=1;base<=n;++len,base<<=1){
        int x=base;
        while(x<=n)vis[x]=1,++cnt[len],x*=3;
    }
    --len,f[0][0]=1;
    for(register int i=1;i<=len;++i)
        for(register int j=0;j<1<<cnt[i];++j){
            if(bad[j])continue;
            f[i&1][j]=0;
            for(register int k=0;k<1<<cnt[i-1];++k){
                if(bad[k]||j&k)continue;
                (f[i&1][j]+=f[i&1^1][k])%=mod;
            }
        }
    for(register int i=0;i<1<<cnt[len];++i)if(!bad[i])(ans+=f[len&1][i])%=mod;
    return ans;
}
int main(){
    n=read();
    int ans=1;
    for(register int i=0;i<1<<11;++i){
        for(register int j=1;j<11;++j)
            if(i>>j&1&&i>>j-1&1)bad[i]=1;
    }
    for(register int i=1;i<=n;++i)if(!vis[i])ans=1ll*ans*solve(i)%mod;
    printf("%d\n",ans);
}