Luogu

分析

我们考虑构造一个矩形 $a$ 满足
$$
a_{i,j}=\begin{cases}1,&i=1,j=1\\2a_{i-1,j},&i>1\\3a_{i,j-1},&j>1\end{cases}
$$
这样子问题就变为在这个矩形中选若干个数，相邻的不能选，求方案数。

我们需要保证 $a_{i,j}\leq n$，因此行数不会超过 $17$，列数不会超过 $11$，因此可以状压 DP。设 $dp_{i,S}$ 表示前 $i$ 行，第 $i$ 行选了 $S$ 的方案数，枚举上一行状态转移即可。

但是这样会有一个问题，就是有一些数（例如 $5$）没有出现在矩形中。因此我们对于每个没有出现过的数，以其为 $a_{1,1}$ 构造出这样一个矩阵跑状压 DP，再将方案数乘起来即可。

代码中有一些小小的优化。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,R=16+10,C=12+10;
const int mod=1e9+1;

int n;
int a[R][C],vis[N],dp[R][1<<11];

inline int check(int S) { return !((S<<1)&S); }
inline int calc(int _) {
    int r[20],c;
    for (re int i=1;;++i) {
        a[i][1]=i==1?_:2*a[i-1][1];
        if (a[i][1]>n) { c=i-1; break; }
        vis[a[i][1]]=1;
        for (re int j=2;;++j) {
            a[i][j]=3*a[i][j-1];
            if (a[i][j]>n) { r[i]=j-1; break; }
            vis[a[i][j]]=1;
        }
    }
    memset(dp,0,sizeof(dp));
    for (re int S=0;S<1<<r[1];++S) dp[1][S]=check(S);
    for (re int i=2;i<=c;++i)
        for (re int S=0;S<1<<r[i];++S) {
            if (!check(S)) continue;
            for (re int T=0;T<1<<r[i-1];++T) {
                if (!check(T)) continue;
                if (T&S) continue;
                dp[i][S]=(dp[i][S]+dp[i-1][T])%mod;
            }
        }
    int ans=0;
    for (re int S=0;S<1<<r[c];++S) ans=(ans+dp[c][S])%mod;
    return ans;
}

int main() {
    n=read(); int ans=1;
    for (re int i=1;i<=n;++i)
        if (!vis[i]) ans=1ll*ans*calc(i)%mod;
    printf("%d\n",ans);
    return 0;
}