题目概述

如果选了 $x$ 就不能选 $2x$ 和 $3x$ ，求 $1..n$ 满足条件的子集个数。

解题报告

这种神题完全做不来，一波转化日神仙：

 x  3x  9x ...
2x  6x 18x ...
4x 12x 36x ...
...

也就是说选了矩阵的一个元素就不能选相邻元素，而指数爆炸矩阵的行和列都不多。

那么就可以直接暴算了，状压一下。注意任何一个不是 $2$ 和 $3$ 倍数的数都对应了一个矩阵。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxr=18,maxc=12,maxs=1<<maxc,MOD=1e9+1;

int n,pw[2][maxr+5],f[maxr+5][maxs],h[maxs];bool vis[maxs];

inline bool check(int s) {for (int i=1;i<maxc;i++) if ((s>>i&1)&&(s>>i-1&1)) return false;return true;}
inline void Make(int n){
    for (int i=pw[0][0]=1;i<=maxr;i++) pw[0][i]=pw[0][i-1]*2;
    for (int i=pw[1][0]=1;i<=maxc;i++) pw[1][i]=pw[1][i-1]*3;
    for (int j=0,k;j<(1<<maxc);j++) {for (k=maxc-1;~k;k--) if (j>>k&1) break;h[j]=k;vis[j]=check(j);}
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
#define ex(i,j) (h[j]<0||vis[j]&&(LL)st*pw[0][i]*pw[1][h[j]]<=n)
inline int DP(int st){
    int x,R=1,C=1,ans=0;
    x=st;while (x<n) x*=2,R++;x=st;while (x<n) x*=3,C++;
    for (int j=0;j<(1<<C);j++) f[0][j]=ex(0,j);
    for (int i=1;i<=R;i++)
        for (int j=0;j<(1<<C);j++)
            if (f[i][j]=0,ex(i,j))
                for (int k=0;k<(1<<C);k++)
                    if (!(j&k)) AMOD(f[i][j],f[i-1][k]);
    for (int j=0;j<(1<<C);j++) AMOD(ans,f[R][j]);return ans;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d",&n);Make(n);int ans=1;
    for (int i=1;i<=n;i++) if (i%2&&i%3) ans=(LL)ans*DP(i)%MOD;
    return printf("%d\n",ans),0;
}