[HNOI2012] 集合选数
目录题目描述
《集合论与图论》这门课程有一道作业题，要求同学们求出 \(\{ 1, 2, 3, 4, 5 \}\) 的所有满足以下条件的子集：若 \(x\) 在该子集中，则 \(2x\) 和 \(3x\) 不能在该子集中。
同学们不喜欢这种具有枚举性质的题目，于是把它变成了以下问题：对于任意一个正整数 \(n \le 10^5\)，如何求出 \(\{1,2,\ldots ,n\}\) 的满足上述约束条件的子集的个数（只需输出对 \(10^9+1\) 取模的结果），现在这个问题就交给你了。
输入格式
只有一行，其中有一个正整数 \(n\)。\(30 \%\) 的数据满足 \(n \le 20\)。
输出格式
仅包含一个正整数，表示 \(\{1,2,\ldots ,n\}\) 有多少个满足上述约束条件的子集。
样例 #1
样例输入 #1
4
样例输出 #1
8
提示
【样例解释】
有 \(8\) 个集合满足要求，分别是空集，\({1}\)，\(\{1,4\}\)，\(\{2\}\)，\(\{2,3\}\)，\(\{3\}\)，\(\{3,4\}\)，\(\{4\}\)。
【数据范围】
对于 \(30 \%\) 的数据，\(n \le 20\)。
对于 \(100 \%\) 的数据，\(1 \le n \le 10^5\)。
题意概括
就是让你在\(1-n\)里面选数，要求选了\(x\)就不能选\(2x,3x\)，求最大方案数。
思路历程：
私货：当代互联网天下第一！！！
1.设计状态
显然我们应该设计是否选择\(x\)为状态，而是否满足条件在转移前判断。
满足条件是不满足条件的对立事件，所以我们可以先把不能在一起的点做出来，这样我们就把问题转化为了不能选择矩阵中相邻的点：
以\(1\)举例子，\(n=100\)：
1 2 4 8 16 32 64
3 6 12 24 48 96
9 18 36 72
27 54
81
可见矩阵横着是乘\(2\)，竖着是乘\(3\)，均小于\(n=100\)
但是我们这个显然是不全的啊，要满足条件又不止满足\(1\)。
我们可以发现，这个矩阵里面，\(2\)，\(3\)这样的\(1*2\)的倍数或\(1*3\)的倍数的数已经选入，不用再管，但是像\(5\)这样的数，我们还需要继续再列一个矩阵。
因此我们用一个特判数组，只要矩阵里出现过这个点就是\(true\)，否则再列一个矩阵。
matrix pre
inline void pre(int x){
for(int i=1;i<=lg3n;++i){
if(i==1) a[i][1]=x;
else a[i][1]=a[i-1][1]*3;
if(a[i][1]>n) break;
yend=i,line[i]=1,judge[a[i][1]]=true;
for(int j=2;j<=lg3n;++j){
a[i][j]=a[i][j-1]<<1;
if(a[i][j]>n) break;
line[i]=j;
judge[a[i][j]]=true;
}
len[i]=(1<<line[i])-1;
}
}
for(int i=1;i<=n;++i){
if(!judge[i]){
pre(i);
}
}
而对于状态，我们不能选择具有在矩阵中相邻的点的状态，可以进行初始化：
pre2
for(int i=0;i<=maxn-1;++i){
if( (i<<1) & i) g[i]=0;
else g[i]=1;
}
2.设计转移
我们的状态是以一个数扩展而成的矩阵，状态也应该是这样的。
因此我们的状态建立在以某数\(x\)构造的矩阵上，有\(f_{i,j}\)表示矩阵内\(1-i\)行中第\(i\)行选择状态\(j\)有多少种方案，显然有转移：
\[\begin{aligned} & if(上一行的状态k合法 并且 上一行的状态k与改行枚举的状态j没有重合点)\\ & f_{i,j}=f_{i,j}+f_{i-1,k} \end{aligned} \]最后，因为我们每个矩阵是不会存在交叉部分的，比如\(1\)的矩阵里可以选出\(1,2,3\)，\(5\)的矩阵里可以选出\(5,10,15\)，显然我们可以选出\(1,2,3,5\),或者\(1,2,3,5,10\)，不同矩阵之间的方案数是遵循乘法原则的。
代码实现：
Miku's Code
#include<bits/stdc++.h>
using namespace std;
typedef long long intx;
const int maxn=1e5+50,mod=1e9+1;
const int lg2n=18,lg3n=13;
intx n,ans,num;
intx g[(1<<lg2n)+2];
intx a[lg2n+2][lg2n+2],line[lg2n+2],len[lg2n+2],yend;
bool judge[maxn];
intx f[lg2n+2][(1<<lg2n)+2];
inline void pre(intx x){ //矩阵初始化
for(intx i=1;i<=lg3n;++i){ //第一列初始化
if(i==1) a[i][1]=x;
else a[i][1]=a[i-1][1]*3;
if(a[i][1]>n) break;
yend=i,line[i]=1,judge[a[i][1]]=true; //yend表示第一列的最后一行,line表示某一行的最后一列
for(intx j=2;j<=lg2n;++j){
a[i][j]=a[i][j-1]*2;
if(a[i][j]>n) break;
line[i]=j,judge[a[i][j]]=true;
}
len[i]=(1<<line[i])-1; //len表示某一行最大状态
}
}
inline intx work(){
num=0;
for(intx i=0;i<=len[1];++i){
f[1][i]=g[i];
}
for(intx i=2;i<=yend;++i){
for(intx j=0;j<=len[i];++j){
if(!g[j]) continue;
f[i][j]=0;
//一定要记得清空啊,或者说在pre()里面memset,但是用到在清省复杂度
for(intx k=0;k<=len[i-1];++k){
if( g[k] && ((k & j)==0) ){
f[i][j]+=f[i-1][k];
f[i][j]%=mod;
}
}
}
}
for(intx i=0;i<=len[yend];++i){
num+=f[yend][i];
num%=mod;
}
return num;
}
int main(){
scanf("%lld",&n);
ans=1;
for(intx i=0;i<=(1<<lg2n)-1;++i){
if( (i<<1) & i) g[i]=0;
else g[i]=1;
}
for(intx i=1;i<=n;++i){
if(!judge[i]){
pre(i);
int s=work();
ans=ans*s%mod;
}
}
printf("%lld",ans);
return 0;
}