BZOJ 2734: [HNOI2012]集合选数 [DP 状压 转化]

时间：2024-09-05 09:34:56

传送门

题意：对于任意一个正整数 n≤100000，如何求出{1, 2,..., n} 的满足若 x 在该子集中，则 2x 和 3x 不能在该子集中的子集的个数（只需输出对 1,000,000,001 取模的结果）

好巧妙的转化啊：

构造一个矩阵，把限制关系转化成矩阵的相邻元素不能同时选

1 3  9  27…

2 6 18 54…

4 12 36 108…

然后愉♂悦的状压DP就可以啦

注意每一个既不被$2$又不被$3$整除的数都可以作为矩阵的第一个元素，还有矩阵不一定填满

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=,S=(<<)+,P=1e9+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,f[N][S];

inline void mod(int &x){if(x>=P) x-=P;}

ll ans=;

int col[N];

void dp(int x){

    for(int i=x,r=;i<=n;i*=,r++){

        int c=;

        for(int j=i;j<=n;j*=,c++);

        col[r]=<<c;

        //printf("col %d %d\n",r,c);

    }

    int r=;

    for(int i=x;i<=n;i*=,r++);

    //printf("dp %d %d \n",x,r);

    f[][]=;col[]=;

    for(int i=;i<=r;i++)

        for(int j=;j<col[i];j++) if( (j&(j<<))== ){

            f[i][j]=;

            for(int k=;k<col[i-];k++) if( (j&k)== ) mod(f[i][j]+=f[i-][k]);

            //printf("f %d %d %d\n",i,j,f[i][j]);

        }

    int _=;

    for(int j=;j<col[r];j++) mod(_+=f[r][j]);

    //printf("_ %d\n",_);

    ans=ans*_%P;

}

int main(){

    freopen("in","r",stdin);

    n=read();

    for(int i=;i<=n;i++) if(i% && i%) dp(i);

    printf("%lld",ans);

}

相关文章