BZOJ 2734 [HNOI2012]集合选数 (状压DP、时间复杂度分析)

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=2734

题解

嗯早就想写的题，昨天因为某些不可告人的原因（大雾）把这题写了，今天再来写题解
神仙题，做法大概就是，构造一个矩阵，左上角是(1), 往下每个数都是上面的(3)倍，往右每个数都是左面的(2)倍，然后在上面跑状压DP，求有多少种选法使得没有两个被选的位置有公共边
然后把左上角改成(5,7,11...)分别做一遍，答案相乘即可

嗯，时间复杂度……玄学？
下面给出我的分析:
考虑对一个(r)行(c)列((r<c))的矩阵进行状压DP，长度为(r)的没有连续两个(1)的01序列个数是(Fib(r)=O(1.618^r)), 故状压DP的复杂度为$$O((1.618^2)^r imes c)=O(2.618^rc)$$
对于一个左上角是(i)的矩阵，行数为(O(log_3{frac{n}{i}})), 列数为(O(log_2{frac{n}{i}})), 故进行状压DP的复杂度为$$O(2.618^{log_3{frac{n}{i}}}log_2frac{n}{i})=O((frac{n}{i})^{0.876}log n)$$
而我们要做的就是对(i=1,5,7,11...)求和，那么不妨放缩成对(i=1,2,...,n)求和，$$sum^{n}{i=1}(frac{n}{i})^{0.876}log n=n^{0.876}log nint^{n}{0}x^{-0.876} ext{d}x=O(nlog n)$$

代码

#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<iostream>
#define llong long long
using namespace std;
 
inline int read()
{
    int x=0; bool f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
    for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
    if(f) return x;
    return -x;
}
 
const int N = 1e5;
const int P = 1e9+1;
const int lg2N = 17;
const int lg3N = 11;
int cnt[N+3];
llong dp[lg2N+2][(1<<lg3N)+3];
int n;
llong ans;
 
bool isok(int x) {return (x&(x>>1))==0 && (x&(x<<1))==0;}
void updsum(llong &x,llong y) {x = (x+y)%P;}
 
void solve(int x)
{
    llong ret = 0ll; int x0 = x;
    for(int i=1; x<=n; i++,x*=2)
    {
        int xx = x; cnt[i] = 0;
        for(; xx<=n; cnt[i]++,xx*=3);
        for(int j=0; j<(1<<cnt[i]); j++)
        {
            if(isok(j))
            {
                if(i==1) {dp[i][j] = 1ll;}
                else
                {
                    int jj = ((1<<cnt[i-1])-1)^j;
                    for(int k=jj; k>=0; k=(k==0?-1:((k-1)&jj)))
                    {
                        updsum(dp[i][j],dp[i-1][k]);
                    }
                }
                if(x*2>n) {updsum(ret,dp[i][j]);}
            }
        }
    }
     
    ans = ans*ret%P;
    x = x0;
    for(int i=1; x<=n; i++,x*=2)
    {
        int xx = x,nn = 1;
        for(int j=0; j<(1<<cnt[i]); j++)
        {
            dp[i][j] = 0ll;
        }
        cnt[i] = 0;
    }
}
 
int main()
{
    scanf("%d",&n); ans = 1ll;
    for(int i=1; i<=n;)
    {
        solve(i);
        if(i%6==1) i+=4;
        else i+=2;
    }
    printf("%lld
",ans);
    return 0;
}