传送门

题意：

给出n，求出 { 1,...,n} { 1 , . . . , n } 的所有满足以 下条件的子集数量：若 x 在该子集中，则 2x 和 3x 不能在该子集中。

n≤100000 n ≤ 100000

Solution:

没见过类似做法的人见到这道题真的是毫无思路啊…

构造矩阵形如 ⎛⎝⎜⎜⎜⎜⎜⎜1248...361224...9183672...2754108216..................⎞⎠⎟⎟⎟⎟⎟⎟ ( 1 3 9 27 . . . 2 6 18 54 . . . 4 12 36 108 . . . 8 24 72 216 . . . . . . . . . . . . . . . . . . )

即每一项的下面是这一项 ∗2 ∗ 2 ,右边是这一项 ∗3 ∗ 3

发现最多是一个 11∗17 11 ∗ 17 的矩阵，而我们的目标就可以转化求为不选取矩阵中相邻的元素的方案数，这可以用一个简单的状压dp求出来

一个矩阵可能不能包含所有数，所以说建出多个矩阵最后把方案数相乘即可

代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int mod=1e9+1;
int n,tot=1,ans,can[1<<11],top;
int f[20][1<<11];
bool vis[100010];
int main()
{
    scanf("%d",&n);
    for (int i=0;i<(1<<11);i++)
    {
        bool p=1;
        for (int j=1;j<11;j++)
            if (((i>>j)&1)&&((i>>j-1)&1)) {p=0;break;}
        if (p) can[++top]=i;
    }
    int nw=1;
    while (nw<=n)
    {
        f[0][1]=1;ans=0;
        int i;int pre=1;
        for (i=1;;i++)
        {
            int pos=nw*(1<<i-1);if (pos>n) break;
            int len=1;vis[pos]=1;
            while (pos*3<=n) vis[pos*3]=1,len++,pos*=3;
            int lim=0;
            while ((can[lim+1]&((1<<len)-1))==can[lim+1]&&lim<top) lim++;
            //for (int j=1;j<=lim;j++) printf("%d %d\n",i,can[j]);
            for (int j=1;j<=pre;j++)
                for (int k=1;k<=lim;k++)
                    if ((can[j]&can[k])==0) f[i][k]=(f[i][k]+f[i-1][j])%mod;
        //  for (int j=1;j<=lim;j++) printf("%d ",f[i][j]);
            pre=lim;
        }
        for (int j=1;j<=top;j++) ans=(ans+f[i-1][j])%mod;
        tot=1ll*tot*ans%mod;
        while (vis[nw]) nw++;
        for (int j=0;j<i;j++)
            for (int k=1;k<=top;k++) f[j][k]=0;
    }
    printf("%d",tot);
}