BZOJ2734 HNOI2012集合选数（状压dp）

时间：2023-03-10 01:15:53
BZOJ2734 HNOI2012集合选数（状压dp）

　　完全想不到的第一步是构造一个矩阵，使得每行构成公比为3的等比数列，每列构成公比为2的等比数列。显然矩阵左上角的数决定了这个矩阵，只要其取遍所有既不被2也不被3整除的数那么所得矩阵的并就是所有的数了，并且显然不会有重复。

　　现在要满足题目要求只需要使在矩阵中选取的数不相邻。显然这可以用状压dp以4^n*m的复杂度搞出来。对于每一个矩阵都这样做一遍再乘起来就可以了。

　　看起来复杂度非常爆炸。不过冷静分析一下，这样做的复杂度往大了算是Σ4log3(n/i)*log2n，即Σ(n/i)*log34*log2n，也即复杂度不会超过O(nlog2n)。当然远远跑不满。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

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

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

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define P 1000000001

#define N 100010

int n,len[],p[],lg3[N],f[][<<],q[<<],cnt=,ans=;

int main()

{

#ifndef ONLINE_JUDGE

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

    freopen("bzoj2734.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

    p[]=;for (int i=;i<=;i++) p[i]=p[i-]*;

    lg3[]=;

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

    {

        lg3[i]=lg3[i-];

        if (p[lg3[i]+]<=i) lg3[i]++;

    }

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

    {

        int x=i,last=;q[++cnt]=i;

        while (x)

        {

            if ((x&)&&last) {cnt--;break;}

            last=x&;x>>=;

        }

    }

    q[cnt+]=<<;

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

    if (i%&&i%)

    {

        int m;

        for (m=;(i<<m-)<=n;m++) len[m]=lg3[n/(i<<m-)];

        m--;

        f[][]=;

        for (int k=;k<=m;k++)

            for (int j=;q[j]<(<<len[k]);j++)

            {

                f[k][j]=;

                for (int x=;q[x]<(<<len[k-]);x++)

                if (!(q[j]&q[x])) f[k][j]=(f[k][j]+f[k-][x])%P;

            }

        int tot=;

        for (int j=;q[j]<(<<len[m]);j++) tot=(tot+f[m][j])%P;

        ans=1ll*ans*tot%P;

    }

    cout<<ans;

    return ;

}

相关文章