简要题意

给你一个 \(n\) 个元素的集合，它由前 \(n\) 个正整数构成。你需要求出它有多少个非空子集，满足若 \(x\) 在这个子集中， \(2x,3x\) 不能在子集中。由于答案可能很大，你只需要对 \(10^9+1\) 取模即可。

\(1 \leq n \leq 10^5\)

思路

这道题的构造思想非常清奇。我们可以构造一个矩阵：

\[A=\begin{bmatrix}
1 & 2 & 4 & 8 & \cdots\\
3 & 6 & 12 & 24 & \cdots\\
9 & 18 & 36 & 72 & \cdots\\
27 & 54 & 108 & 216 & \cdots\\
81 & 162 & 324 & 648 & \cdots \\
\cdots & \cdots & \cdots & \cdots & \cdots
\end{bmatrix}
\]

具体来说：

\[A_{i,j}=\begin{cases}
& 1 & i=1,j=1\\
& 3\cdot f_{i-1,j} & i\neq 1,j=1\\
& 2\cdot f_{i,j-1} & \text{otherwise}
\end{cases}
\]

这样子我们就将原问题转化成了给出一个矩阵，如果你选择 \((i,j)\)，就不能选择 \((i-1,j)\) 和 \((i,j-1)\)，求方案数。这个问题可以使用状压 DP 解决。

我们设 \(f_{i,S}\) 为考虑到第 \(i\) 行，这一行选择 \(S\) 中的元素的方案数。不难发现：

\[f_{i,S}=\begin{cases}
& \operatorname{valid}(S) & i=1 \\
& \sum\limits_{T\cup S=\emptyset,\operatorname{valid}(T)}{f_{i-1,T}} & \text{otherwise}
\end{cases}
\]

其中 \(\operatorname{valid}(S)\) 是指选择该行中 \(S\) 中的元素是否合法，也就是两两是否相邻。用状态压缩的话可以简单地这样实现：

\[\operatorname{valid}(S)=S\&(S>>1)?0:1
\]

当然左移也可以。其实原理就是将原本一样的位错开，相邻的进行与运算。

最后注意这个表不是所有元素都会覆盖到（具体来说，只会覆盖到 \(\forall i,j\in \mathbb{N},2^{i}3^{j}\)）。所以我们如果遇到了一个没有被之前覆盖到的元素，我们需要将它设为 \(f_{1,1}\) 重新生成矩阵 \(A\)，并重新 DP，最后按照乘法原理（因为这些都可以同时选）将结果累乘。

然后这道题就做完了。最后提醒大家一句，位运算优先级比较低，建议大家勤添括号。

代码

点击查看代码 
#include <bits/stdc++.h>
#define int long long
#define valid(x) (x&(x>>1)?0:1)
using namespace std;

const int mod = 1e9+1;
int M(const int x){return (x%mod+mod)%mod;}
const int N = 1e5+5;

int n,vis[N],a[25][25],col[N],f[25][1000005],final,ans=1;

inline void init(int x){
    for(int i=1;i<=11;i++){
        if(i==1) a[i][1]=x;
        else a[i][1]=a[i-1][1]*3;
        if(a[i][1]>n) break;
        vis[a[i][1]]=1;col[i]=1;final=i;
        for(int j=2;j<=18;j++){
            a[i][j]=a[i][j-1]<<1;
            if(a[i][j]>n) break;
            col[i]=j;vis[a[i][j]]=1;
        }
    }
}

inline int dp(int x){
    for(int i=0;i<(1<<col[1]);i++){
        f[1][i]=valid(i);
    }
    for(int i=2;i<=final;i++){
        for(int j=0;j<(1<<col[i]);j++){
            if(!valid(j)) continue;
            f[i][j]=0;
            for(int k=0;k<(1<<col[i-1]);k++){
                if(valid(k) && ((k&j) == 0)) f[i][j]=M(f[i][j]+f[i-1][k]);
            }
        }
    }
    int ret=0;
    for(int i=0;i<(1<<col[final]);i++) ret=M(ret+f[final][i]);
    return ret;
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        init(i);ans=M(ans*dp(i));
    }
    cout<<ans;
    return 0;
}