bzoj 2734 [HNOI2012]集合选数 状压DP+预处理

时间：2021-08-24 06:34:15

这道题很神啊……

神爆了……

思路大家应该看别的博客已经知道了，但大部分用的插头DP。我加了预处理，没用插头DP，一行一行来，速度还挺快。

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <cmath>

#define N 100100

#define M 50

#define yu 1000000001

#define inf 1<<29

using namespace std;

int n;

long long ans=;

long long f[][N/M]={};

int keneng[N/M],kenengnum;

int sushu[N],sushunum;

void make_sushu(int limit) // 这里不是筛素数，而是把不是2,3的倍数的筛出来

{                          // 如果筛素数，25不是素数，但是5的矩阵不能包含25

    int i,j,k;

    int vis[N]={};

    sushunum=;

    for (i=;i<=limit;i++)

        if (i%!=&&i%!=)

            sushu[++sushunum]=i;

}

bool shifou(int now)    // 预处理的判断，判断是否有两个1相连

{                         // 即是否取连续的两个数

    int i,j,k;

    i=now&; now>>=;

    while (now!=)

    {

        j=now&;

        if (i==j&&i&&j)

            return false;

        i=j;

        now>>=;

    }

    return true;

}

void chuli(int limit)  //预处理，把可以选的状态存起来，省时间

{

    int i,j,k;

    int maxn=;

    kenengnum=;

    for (i=;i<=limit;i++)

      maxn*=;

    for (i=;i<maxn;i++)

    {

        if (shifou(i))

        {

            keneng[kenengnum++]=i;

        }

    }

}

int pd_long(int x) // 由于矩阵每一行长度不同，所以预处理某些不能用

{                  // 这个判断每一行长度

    int i=,zanshi=;

    while (i<=x)

    {

        zanshi++;

        i*=;

    }

    return zanshi;

}

long long make_juzhen(int now)

{

    int i,j,k,x=,y,z;

    int limit,lnow,lnowbefore=inf;

    limit=pd_long(n/now);

    chuli(limit);

    f[][]=;

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

    {

        memset(f[i%],,sizeof(f[i%]));

        lnow=pd_long(n/now/x);  // 当前行的长度

        for (j=;j<kenengnum;j++)

        {

            if (keneng[j]>>lnow>) //如果有选超过当前行长度的，不选

            {

                f[i%][j]=;

                continue;

            }

            for (k=;k<kenengnum;k++) // 和上一行比较，是否有相连的1选了

            {

                if (keneng[k]>>lnowbefore>) // 上一行状态不能超过上一行长度

                    continue;

                if (keneng[j]&keneng[k])

                    continue;

                f[i%][j]+=f[(i+)%][k];

                f[i%][j]%=yu;

            }

        }

        lnowbefore=lnow;  // 上一行长度

    }

    return (f[(i+)%][]+f[(i+)%][])%yu; //最后一行一定只有一个，答案只有这两种情况加起来，最后一个选或不选

}

int main()

{

    int i,j,k,x,y,z;

    cin>>n;

    make_sushu(n);

    for (i=;i<=sushunum;i++)

    {

           ans*=make_juzhen(sushu[i]);

           ans%=yu;

    }

    cout<<ans<<endl;

}

相关文章