[BZOJ2734][HNOI2012] 集合选数（状态压缩+思维）

#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 100010
using namespace std;

const int mo=1000000001;
int n,g[20][20],b[20],dp[20][2049],Ans=1;
bool vis[N];

int DP(int x){
    memset(b,0,sizeof(b));
    memset(g,0x3f,sizeof(g));
    memset(dp,0,sizeof(dp));
    g[1][1]=x;
    for(int i=2;i<=18&&g[i-1][1]*1ll*2<=n;++i) g[i][1]=g[i-1][1]*2;
    for(int i=1;i<=18;++i)
        for(int j=2;j<=11&&g[i][j-1]*1ll*3<=n;++j)
            g[i][j]=g[i][j-1]*3;
    for(int i=1;i<=18;++i)
        for(int j=1;j<=11;++j)
            if(g[i][j]<=n) b[i]|=(1<<(j-1)),vis[g[i][j]]=1; 
    dp[0][0]=1;
    for(int i=0;i<18;++i)
        for(int S=0;S<=b[i];++S)
            if(dp[i][S])
                for(int nxS=0;nxS<=b[i+1];++nxS)
                    if(((S&nxS)==0)&&((nxS&(nxS>>1))==0))//满足限制
                        (dp[i+1][nxS]+=dp[i][S])%=mo;           
    return dp[18][0];
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        if(!vis[i]) Ans=(Ans*1ll*DP(i))%mo;//乘法原理
    printf("%d\n",Ans);
    return 0;
}