洛谷3226 [HNOI2012]集合选数

题意

给出一个 $n(\le 10^5)$ ，求集合 $\{1,2,...,n\}$ 的满足：若 $x$ 在集合中，则 $2x$ 和 $3x$ 不能出现在集合中 的子集个数。

题解

可以构造一个矩形，横向依次 $\times 3$ ，纵向依次 $\times 2$ ，如下图所示：

1 3 9 27 81 243
2 6 18 54 162 486
4 12 36 108 324 972

在这个矩形中选不相邻的数即可满足条件 。

当然一个矩形不能出现所有数字，所以对每个没有出现过的 $x$ ，都把它放到 $(1,1)$ 构造一个矩形。最后乘法原理统计答案。

#include<bits/stdc++.h>
#define ha 1000000001

using namespace std;

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

const int N=100005,M=20;
bool vis[N];
int n,f[M][1<<11],s[M][M],mx[M];

inline int dp(int x)
{
    memset(f,0,sizeof(f));
    memset(s,0,sizeof(s));
    memset(mx,0,sizeof(mx));
    s[1][1]=x;
    for (int i=2;i<=11 && s[1][i-1]*3<=n;i++)
        s[1][i]=s[1][i-1]*3;
    for (int i=2;i<=18 && s[i-1][1]*2<=n;i++)
        for (int j=1;j<=11 && s[i-1][j]*2<=n;j++)
            s[i][j]=s[i-1][j]*2; //构造矩形
    for (int i=1;i<=18;i++)
    {
        for (int j=1;j<=11 && s[i][j];j++)
        {
            mx[i]|=1<<(j-1);
            vis[s[i][j]]=1;
        }
    }
    f[0][0]=1;
    for (int i=0;i<18;i++)
    {
        for (int j=0;j<=mx[i];j++) //当前行
        {
            if (!f[i][j]) continue;
            for (int k=0;k<=mx[i+1];k++) //下一行
            {
                if (j&k || k&(k<<1)) continue;
                f[i+1][k]=(f[i+1][k]+f[i][j])%ha;
            }
        }
    }
    return f[18][0];
}

signed main()
{
    n=read();
    int ans=1;
    for (int i=1;i<=n;i++)
    {
        if (vis[i]) continue;
        ans=1ll*ans*dp(i)%ha;
    }
    return !printf("%d",ans);
}