P3226 [HNOI2012]集合选数题解
博客
思路（状压DP）
-
题目要求“若 x 在该子集中，则 2x 和 3x 不能在该子集中”，那么我们就可以构造数个矩阵。
-
这些矩阵中没有重复的数，且保证了它们的并集取到了从1到n。
-
其中每个矩阵都满足==对于矩阵中任意一个数，都满足它是它左边那个数的3倍，同时是上面那个数的2倍==，即
a[i][j]=a[i-1][j]*2=a[i][j-1]*3，如图： -
那么题目就变成了从所构造的矩阵当中取出若干个小于n的数的方法种数，就是典型的状压DP了。
-
由于有多个矩阵，最终答案即为各个矩阵所得到的答案之积。
小细节
-
行间是3倍，列间是2倍，这样可以减少每行的状态数，降低时间空间复杂度。
-
为了保证所有的矩阵中没有重复的数，每次构造矩阵都从未被用过的数中选取最小的一个作为矩阵的a[1][1]。
-
为了使取出的数满足小于等于n，可以通过判断状态所取到的最高位是否大于n，若大于n，则可直接退出（状态是单增的）。
-
但是构造矩阵是不满足小于等于n的 数也一样要计算出，确保上述判断有效。
-
注意开
long long，==能模就模！==代码
#include<cstdio>
#include<cmath>
#define int long long
#define ri register int
const int maxn=1e5+9;
const int p=1e9+1;
int a[20][15],b[20][15];
int s[maxn],lg[maxn];
int dp[20][maxn];
int flag[maxn];
int n,ans=1;
void js(){
int cnt=0;
for(ri i=0;i<maxn;++i)
{
if(a[1][lg[i]]>n) break;
if(!(i&(i>>1))) s[++cnt]=i;
}
for(ri j=1;j<=cnt;++j) dp[1][j]=1;
for(int i=2;i<=18;++i)
{
if(a[i][1]>n) break;
for(int j=1;j<=cnt;++j)
{
if(a[i][lg[s[j]]]>n) break;
for(int k=1;k<=cnt;++k)
{
if(!(s[j]&s[k])) dp[i][j]=(dp[i][j]+dp[i-1][k])%p;
if(a[i-1][lg[s[k]]]>n) break;
}
}
}
int t=0;
for(ri i=1;i<=18;++i)
{
if(a[i+1][1]<=n) continue;
for(ri j=1;j<=cnt;++j)
if(a[i][lg[s[j]]]<=n)
t=(t+dp[i][j])%p;
break;
}
if(t) ans=ans*t%p;
for(ri i=1;i<=18;++i)
for(ri j=1;j<=cnt;++j)
dp[i][j]=s[j]=0;
}
void get_a(int I){
for(ri i=1;i<=18;++i)
for(ri j=1;j<=12;++j)
{
a[i][j]=b[i][j]*I;
if(a[i][j]<=n) flag[a[i][j]]=1;
}
}
void solve(){
scanf("%lld",&n);
b[1][1]=1;
for(ri i=2;i<=12;++i) b[1][i]=b[1][i-1]*3;
for(ri i=1;i<=maxn;++i) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
for(ri i=2;i<=18;++i)
for(ri j=1;j<=12;++j)
b[i][j]=b[i-1][j]*2;
for(ri I=1;I<=n;++I)
{
if(flag[I]) continue;
get_a(I);
if(a[1][1]>n) break;
js();
}
printf("%lld\n",ans);
}
#undef int
int main(){
solve();
return 0;
}