HNOI 集合选数

题目大意

从 以内的自然数里面选，对于任意一个自然数 选中的数中不能有 ，计算出总的方案数

题解

考虑建图，在一个矩阵上 从左到右 依次为前一个数的两倍 ，从上至下依次是前一个数的三倍

题意转化为在这样一个矩阵上, 选择不相邻的数， 因为长和宽都是 级别的所有我们考虑状压DP

用 表示第 行，合法状态 时 累计的方案数

满足自身和下一行均合法 即使 是一个和 行冲突的一个合法状态 ，但是这样的话方案数也为 对答案无影响

#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
static const int maxm = 1e5 + 10;
static const int maxn = 20 + 10;
static const int MOD = 1000000001;
int f[maxn][maxm],lmt[maxm],mtx[maxn][maxn],vis[maxm],bin[maxm];
int n;
LL ans = 1;
int dp(int x){
    for(int i = 1;i <= 18;i++)lmt[i] = 0;
    mtx[1][1] = x;
    for(int i = 2 ;i <= 18;i++)
        if(mtx[i - 1][1] * 2 <= n)mtx[i][1] = mtx[i - 1][1] * 2;
        else mtx[i][1] = n + 1;
    for(int i = 1 ;i <= 18 ;i++)
        for(int j = 2;j <= 11 ;j++)
            if(mtx[i][j - 1] * 3 <= n)mtx[i][j] = mtx[i][j - 1] * 3;
            else mtx[i][j] = n + 1;
    for(int i = 1;i <= 18;i++)
        for(int j = 1;j <= 11;j++)
            if(mtx[i][j] <= n) lmt[i] += bin[j-1] , vis[mtx[i][j]] = 1;
    /*
    bin是用来占位的 考察这一行最多可以塞几个
    */
    for(int i = 0;i <= 18;i++)
        for(int j = 0;j <= lmt[i];j++)
            f[i][j] = 0;
    f[0][0] = 1;
    for(int i = 0;i <= 18;i++)
        for(int j = 0;j <= lmt[i];j++)
            if(f[i][j])
                for(int k = 0;k <= lmt[i + 1];k++)
                    if(!(j & k) && (!(k & (k << 1))))  // 自身合法且与下一行合法
                        f[i + 1][k] = (f[i + 1][k] + f[i][j]) % MOD;
    return f[18][0];
}
int main(){
    scanf("%d",&n);
    bin[0] = 1;
    for(int i = 1;i <= n;i++)bin[i] = bin[i-1] << 1;
    for(int i = 1;i <= n;i++)
        if(!vis[i]) ans = (ans * dp(i)) % MOD;
    printf("%lld\n",ans);
    return 0;
}