题意

《集合论与图论》这门课程有一道作业题，要求同学们求出{1, 2, 3, 4, 5}的所有满足以 下条件的子集：若 x 在该子集中，则 2x 和 3x 不能在该子集中。

同学们不喜欢这种具有枚举性 质的题目，于是把它变成了以下问题：对于任意一个正整数 n<=100000，如何求出{1, 2,..., n} 的满足上述约束条件的子集的个数（只需输出对 1,000,000,001 取模的结果），现在这个问题就 交给你了。

分析

参照hzwer的题解。

写出如下矩阵

1 3 9 27…

2 6 18 54…

4 12 36 108…

发现最多有11列。。。

我们在其中选取一些数，相邻的不能选择

然后就可以状压求方案数了，但是5没有出现，同样5的倍数也没有出现，7也如此。。

应该记录哪些数字出现过，没出现过就作为矩阵的第一个元素，最后把若干个矩阵的方案相乘

时间复杂度

因为这是按照整除关系构建的三角形图，所以三角形并不高，最坏的情况是第一行是1，最后第k行是\(2^k\)，深度是\(O(\log n)\)的，每一行的元素最多也是\(O(\log n)\)的，一个元素推到下一行的状态是\(O(2^k)\)的，越深枚举次数越多，但点数也越少，可以考虑对每个三角形图进行分析，一个很难达到的上界时间复杂度是\(O(n \log n)\)。

这大概是口胡，不过还是蛮有道理的、

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<algorithm>
#include<cstring>
#define rg register
#define il inline
#define co const
template<class T>T read()
{
    T data=0;
    int w=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        data=data*10+ch-'0';
        ch=getchar();
    }
    return data*w;
}
template<class T>T read(T&x)
{
    return x=read<T>();
}
using namespace std;
typedef long long ll;

co int MAXN=1e5+7,MAXL=20,mod=1e9+1;
int n;
int a[MAXL][MAXL];
int b[MAXL],f[MAXL][1<<MAXL];
bool mark[MAXN];
int ans=1;

int add(int x,int y)
{
    x+=y;
    return x>=mod?x-mod:x;
}

int mul(int x,int y)
{
    return (ll)x*y%mod;
}

int cal(int x)
{
    memset(b,0,sizeof b);
    a[1][1]=x;
    for(int i=2;i<=18;++i)
        if(a[i-1][1]*2<=n)
            a[i][1]=a[i-1][1]*2;
        else
            a[i][1]=n+1;
    for(int i=1;i<=18;++i)
        for(int j=2;j<=11;++j)  
            if(a[i][j-1]*3<=n)
                a[i][j]=a[i][j-1]*3;
            else
                a[i][j]=n+1;
    for(int i=1;i<=18;++i)
        for(int j=1;j<=11;++j)
            if(a[i][j]<=n)
            {
                b[i]+=(1<<(j-1));
                mark[a[i][j]]=1;
            }
    for(int i=0;i<=18;++i)
        for(int x=0;x<=b[i];++x)
            f[i][x]=0;
    f[0][0]=1;
    for(int i=0;i<18;++i)
        for(int x=0;x<=b[i];++x)
            if(f[i][x])
                for(int y=0;y<=b[i+1];++y)
                    if((x&y)==0&&(y&(y>>1))==0)
                        f[i+1][y]=add(f[i+1][y],f[i][x]);
    return f[18][0];
}

int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    read(n);
    for(int i=1;i<=n;++i)
        if(!mark[i])
            ans=mul(ans,cal(i));
    printf("%d\n",ans);
    return 0;
}

BZOJ2734 [HNOI2012] 集合选数

原文：https://www.cnblogs.com/autoint/p/9998156.html