BZOJ2734 HNOI2012集合选数（状压dp）

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

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

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

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
    int x=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
#define P 1000000001
#define N 100010
int n,len[20],p[20],lg3[N],f[20][1<<17],q[1<<17],cnt=0,ans=1;
int main()
{
#ifndef ONLINE_JUDGE
    freopen("bzoj2734.in","r",stdin);
    freopen("bzoj2734.out","w",stdout);
    const char LL[]="%I64d
";
#else
    const char LL[]="%lld
";
#endif
    n=read();
    p[1]=1;for (int i=2;i<=15;i++) p[i]=p[i-1]*3;
    lg3[1]=1;
    for (int i=2;i<=n;i++)
    {
        lg3[i]=lg3[i-1];
        if (p[lg3[i]+1]<=i) lg3[i]++;
    }
    for (int i=0;i<(1<<17);i++)
    {
        int x=i,last=0;q[++cnt]=i;
        while (x)
        {
            if ((x&1)&&last) {cnt--;break;}
            last=x&1;x>>=1;
        }
    }
    q[cnt+1]=1<<17;
    for (int i=1;i<=n;i++)
    if (i%2&&i%3)
    {
        int m;
        for (m=1;(i<<m-1)<=n;m++) len[m]=lg3[n/(i<<m-1)];
        m--;
        f[0][1]=1;
        for (int k=1;k<=m;k++)
            for (int j=1;q[j]<(1<<len[k]);j++)
            {
                f[k][j]=0;
                for (int x=1;q[x]<(1<<len[k-1]);x++)
                if (!(q[j]&q[x])) f[k][j]=(f[k][j]+f[k-1][x])%P;
            }
        int tot=0;
        for (int j=1;q[j]<(1<<len[m]);j++) tot=(tot+f[m][j])%P;
        ans=1ll*ans*tot%P;
    }
    cout<<ans;
    return 0;
}