首页 > 代码库 > BZOJ 2734 集合选数（状态压缩DP）

BZOJ 2734 集合选数（状态压缩DP）

2024-07-08 23:54:28   223人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2734

题意：给出一个由1到n的数字组成的集合。定义合法子集为若x在子集中则2x、3x均不能在子集中。求有多少个合法的子集。

思路：

1   3    9

2   6    12

4   12   36

对于上面的矩阵，我们发现就等价于不选相邻数字的方案数。因此枚举每个还没有用到的数字，建立以该数字为左上角的矩阵。接着就是状态压缩DP。

 

int a[N][N];i64 f[2][1<<12];int n,r,c,h[100005];void init(int x){    r=0,c=0; clr(a,0);    int p1=x,p2,tempC;    while(p1<=n)    {        tempC=0;        for(p2=p1;p2<=n;p2*=3) a[r][tempC++]=p2,h[p2]=1;        upMax(c,tempC);        r++;        p1<<=1;    }}int set0(int st,int k){    if(st&(1<<k)) return st^(1<<k);    return st;}int get(int st,int k){    return st&(1<<k);}void up(i64 &x,i64 y){    x+=y;    if(x>=mod) x-=mod;}i64 DP(){    int pre=0,cur=1,M=1<<c;    int i,j,k,t;    FOR0(i,M) f[pre][i]=0;    f[pre][0]=1;    FOR0(i,r) FOR0(j,c)    {        FOR0(k,M) f[cur][k]=0;        FOR0(t,M) if(f[pre][t])        {            up(f[cur][set0(t,j)],f[pre][t]);            if(!a[i][j]) continue;            if(j==0)            {                if(!(t&1)) up(f[cur][t|1],f[pre][t]);            }            else            {                if(!get(t,j)&&!get(t,j-1)) up(f[cur][t|(1<<j)],f[pre][t]);            }        }        swap(pre,cur);    }    i64 ans=0;    FOR0(i,M) up(ans,f[pre][i]);    return ans;}int main(){    RD(n);    i64 ans=1;    int i;    FOR1(i,n) if(!h[i])    {        init(i);        ans=ans*DP()%mod;    }    PR(ans);}

 

 

 


联系
我们