[HNOI2012]集合选数
题目描述
《集合论与图论》这门课程有一道作业题，要求同学们求出 \(\{ 1, 2, 3, 4, 5 \}\) 的所有满足以下条件的子集：若 \(x\) 在该子集中，则 \(2x\) 和 \(3x\) 不能在该子集中。
同学们不喜欢这种具有枚举性质的题目，于是把它变成了以下问题：对于任意一个正整数 \(n \le 10^5\)，如何求出 \(\{1,2,\ldots ,n\}\) 的满足上述约束条件的子集的个数（只需输出对 \(10^9+1\) 取模的结果），现在这个问题就交给你了。
对于 \(30 \%\) 的数据，\(n \le 20\)。
对于 \(100 \%\) 的数据，\(1 \le n \le 10^5\)。
思路点拨
我看到其余的题解都是从构造的角度讲的，但实际上，这个角度并不好出解。我们可以从图论的角度更加容易地思考这个问题。
我们这么思考，对于一个元素 \(i\) ，我们看作一个编号为 \(i\) 的点。那么我们如果将 \(i\) 将 \(2i\) 和 \(3i\) 连边，那么这个问题就可以被转化为我们给定一个有向图，你可以从中选择一些点，是的这些点两两之间没有直接连边。这个问题没有那么好解决，但是这个图有优美的性质。
首先，这个图是一个个独立的联通块，这些连通块我们可以分开计数。每一个连通块都是以某一个不含 \(2\) 或者 \(3\) 因子的点导出的DAG。你可能会疑惑，这样不会有一个点被多个连通块连到吗？但是你考虑一下每一个数的因子组成就会知道答案了。
但是只有这样，不足以出解。另一个性质就是，这些图是一个个残缺不全的网格图。因为，对于一个 \(x\) ，它会到达 \(2x\) ，和 \(3x\) ，而 \(2x\) 和 \(3x\) 都可以到达 \(6x\) 。可以看出，这些点可以组成网格图，排列下来可以看作半个矩阵。这个问题很好求解，我们要求相邻不可以连边，所以状压一下就可以过了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int MAXN=12,mod=1e9+1;
int n,f[20][1<<MAXN];
int a[20];
int qpow(int a,int b){
int ans=1,base=a;
while(b){
if(b&1) ans=ans*base;
base=base*base;
b>>=1;
}
return ans;
}
int p[1<<MAXN],tot;
bool check(int x){
if(x&(x<<1)) return 0;
if(x&(x>>1)) return 0;
return 1;
}
signed main(){
n=read();
int ans=1;
for(int i=1;i<=n;i++){
if(i%2==0||i%3==0) continue;
memset(a,0,sizeof(a));
int x,y;
for(x=1;i*qpow(3,x-1)<=n;x++);
for(y=1;i*qpow(2,y-1)<=n;y++);
x--,y--;
for(int j=1;j<=y;j++)
for(int k=1;k<=x;k++)
if(i*qpow(3,k-1)*qpow(2,j-1)>n)
a[j]+=(1<<(k-1));
int cnt=0;
memset(f,0,sizeof(f));
tot=0;
for(int i=0;i<(1<<x);i++)
if(check(i)) p[++tot]=i;
for(int j=1;j<=tot;j++)
if(!(a[1]&p[j]))f[1][j]=1;
for(int j=2;j<=y;j++){
for(int k=1;k<=tot;k++)
if(!(a[j]&p[k]))
for(int l=1;l<=tot;l++)
if(!(p[k]&p[l]))
f[j][k]=(f[j][k]+f[j-1][l])%mod;
}
for(int j=1;j<=tot;j++)
cnt+=f[y][j];
ans=ans*cnt%mod;
}
cout<<ans;
return 0;
}