P3226 [HNOI2012]集合选数

洛咕

状压DP好题，构造神题。

至于我为什么这么说呢。因为这道题的构造思路真的很神奇，没有构造就只能够用暴力了。(插头DP亦可)

题目描述：对于一个有\(n\)个元素的\(\{1,2,3...,n\}\)的集合，我们可以在里面选择一些数构成一个新的集合，但是选出的数必须满足\(\nexists x\)，使得集合中存在\(2x\)或\(3x\)。就是说放了\(x\)后，就不能再放\(2x\)和\(3x\)了。

对此，有一个很妙的构造矩阵。

以25为例

//第一个矩阵
1  2   4   8  16
3  6  12  24
9 18

在这个矩阵中，我们可以发现。每一行的元素一定是前一个元素的两倍，每一列上的元素，一定是前一个的3倍。

那么我们就可以用状压DP了。先预处理每一行的长度，在预处理每一种长度下这一行能够采用的方案。(这可能不好理解)

举个例子：若是这一行长度为3，我们必须保证每一行不能选相邻的数，转化为二进制就是说不能有相邻的1。

所以我们可以使用的方案为\((000)_2,(001)_2,(010)_2,(100)_2,(101_2)\)，转化为十进制就是\(0,1,2,4,5\)。

状压的预处理完成后，我们就可以定一个\(f[i][j]\)表示在第\(i\)行采用\(j\)（\(j\)为你的方案）的总答案。

那么我们就可以枚举行数(最大为\(ceil(log_3n)\))，再枚举第\(i\)行和第\(j\)行，只要满足\((i\&j)==0\)就可以转移（想一想为什么）。

那么最后我们的答案就是最后一行的\(f[wid][i]\)之和了。

还有一个很重要的点，就是一个矩阵不能包含所有的数，对于那些不能整除2和3的数字，每一个都要单独构造一个矩阵（看上去很多，但实际上可以算一下，就是用埃氏筛把2和3的倍数筛掉了）。
***
代码

#include<bits/stdc++.h>
#define ll long long
#define N 100005
#define K 1000000001
using namespace std;
ll n,ans=1,pr[N],zh[N],tot;
ll f[16][1<<18],len[16],wid,a[20][20],siz[20];
vector<int>q[20];
bool check(int x){
    for(int i=0;i<=16;++i){
        if(((x>>i)&1)==(x>>(i+1)&1)&&((x>>i)&1)){
            return false;
        }
    }
    return true;
}
void pre(int x){
    pr[++tot]=1;
    for(int i=2;i<=x;++i){
        if(!zh[i])pr[++tot]=i;
        for(int j=2;j<=tot&&i*pr[j]<=x;++j){
            zh[i*pr[j]]=1;
            if(i%pr[j]==0)break;
        }
    }
    for(int i=2;i<=tot-2;++i)pr[i]=pr[i+2];tot-=2;
    int yyb=1,xzz=1;
    for(int i=1,j=1;i<=n;i*=3,++j)yyb=j;
    for(int i=1,j=1;i<=n;++j,i*=2)xzz=j;
    for(int i=1;i<=xzz;++i){
        for(int j=0;j<(1<<i);++j){
            if(check(j))q[i].push_back(j),siz[i]++;
        }
    }
}
void solve(int x){
    for(int i=x,j=1;i<=n;i=i*3,j++)wid=j;
    a[1][1]=x;len[1]=1;
    for(int i=2;;++i){
        a[1][i]=a[1][i-1]*2;
        if(a[1][i]>n)break;
        len[1]=i;
    }
    for(int i=2;i<=wid;++i){
        for(int j=1;j<=len[i-1];++j){
            a[i][j]=a[i-1][j]*3;
            if(a[i][j]>n)break;
            len[i]=j;
        }
    }
    ll sum=0;
    for(int i=0;i<siz[len[1]];++i)f[1][i]=1;
    for(int i=2;i<=wid;++i){
        for(int j=0;j<siz[len[i]];++j){
            int yyb=q[len[i]][j];
            f[i][j]=0;
            for(int k=0;k<siz[len[i-1]];++k){
                int xzz=q[len[i-1]][k];
                if(!(xzz&yyb))f[i][j]=(f[i][j]+f[i-1][k])%K;
            }
        }
    }
    for(int i=0;i<siz[len[wid]];++i){
        sum=(sum+f[wid][q[len[wid]][i]])%K;
    }
//  cout<<siz[len[1]]<<" "<<x<<" "<<f[2][0]<<endl;
    ans=(ans*sum)%K;
}
int main(){
    cin>>n;
    if(n==1){puts("2");return 0;}
    if(n==2){puts("3");return 0;}
    pre(n);
    for(int i=1;i<=n;++i){
        if(i%2&&i%3)solve(i);
    }
    cout<<ans<<endl;
    return 0;
}

注意事项：模数要看清呐

P3226 [HNOI2012]集合选数

原文：https://www.cnblogs.com/fenghuazhengmao/p/11589390.html