题目链接

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²⁾r\times 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_2\frac{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 n\int^{n}_{0}x{-0.876}\text{d}x=O(n\log 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\n",ans);

    return 0;

}