EGOI Legowall 简单计数题

· · 题解

其他题解都是 \mathcal{O}\left(\left(nm\right)^{4/3}\right) 的，但这题可以做到 \mathcal{O}\left(nm\right)。

第一种做法，直接容斥：

设 f_i 表示长为 i，高度为 m 的方案数，那么，f_i 可以通过容斥第一个不相等的位置得到：

f_i=F_i^m-\sum_{j<i}f_jF_{i-j}^m

其中 F_i 表示斐波那契数列第 i 项。复杂度 n^2，不够优秀。

第二种做法：

另外一种理解也可以得到上述式子：设联通的生成函数是 f，那么不一定联通的生成函数是 G=1/\left(1-f\right)。

注意到 G 的第 i 项是斐波那契数列的第 i 项的 m 次方，那么其应该有 \mathcal{O}\left(m\right) 次递推式。

由于斐波那契数列第 i 项的 m 次方满足：

\begin{aligned} F^{m}_i=&c\times \left(\phi^i-\hat{\phi}^i\right)^m\\ =&c\times \sum_{j=0}^m\binom{m}{j}\left(-1\right)^j\left(\phi^{m-j}\hat{\phi}^j\right)^i \end{aligned}

其中 c=\sqrt{5}^{-m}，\phi=\left(1+\sqrt{5}\right)/2，\hat{\phi}=\left(1-\sqrt{5}\right)/2。那么 G 的递推式有 h+1 个特征根，\phi^{m-j}\hat{\phi}^j,j=0,1,\cdots m。

设 P\left(x\right)=\prod_{j=0}^m\left(x-\phi^{m-j}\hat{\phi}^j\right)，那么 G\left(x\right)=Q\left(x\right)/P\left(x\right)，其中 Q\left(x\right) 为 m 次多项式。

考虑如何求出 P。不妨设 2j\le m，那么 \phi^{j}\hat{\phi}^{m-j}+\phi^{m-j}\hat{\phi}^j=\left(-1\right)^j\left(\phi^{m-2j}+\hat{\phi}^{m-2j}\right)。而 \phi^{k}+\hat{\phi}^k=\left(\left(1+\sqrt{5}\right)/2\right)^k+\left(\left(1-\sqrt{5}\right)/2\right)^k=2^{1-k}\sum_{j\bmod 2=0}\binom{k}{j}5^{j/2} 是好计算的。因此将 P 中的项两两配对，进行 \mathcal{O}\left(m\right) 二次多项式乘法即可 \mathcal{O}\left(m^2\right) 得到 P。

求出 P\left(x\right) 后就可以 \mathcal{O}\left(m^2\right) 进行 P,G 乘法得到 Q。又 1-f=G^{-1}=P/Q，因此直接 \mathcal{O}\left(nm\right) 递推即可得到答案。

平衡一下复杂度即为 \mathcal{O}\left(nm\right)。

代码：

#include <iostream>
#include <algorithm>
constexpr int N(5e5+10),p(1e9+7),_2((p+1)/2);
int fp(int a,int b){int ans(1),off(a);while(b){if(b&1) ans=1ll*ans*off%p;off=1ll*off*off%p;b>>=1;}return ans;}
int W(int k){return k>=p?k-p:k;}
int main()
{
    int n,m;std::cin>>n>>m;
    if(n<=m)
    {
        static int fib[N],f[N],g[N];fib[0]=g[0]=1;
        for(int i(1);i<=n;++i)
        {
            fib[i]=W(fib[i-1]+(i>1?fib[i-2]:0));
            f[i]=g[i]=fp(fib[i],m);
            for(int j(0);j<i;++j) f[i]=(f[i]+1ll*(p-f[j])*g[i-j])%p;
        }
        std::cout<<f[n]<<std::endl;
    }
    else
    {
        static int f[N],fac[N],ifac[N],fib[N];int d(0);
        fac[0]=1;for(int i(1);i<N;++i) fac[i]=1ll*fac[i-1]*i%p;
        ifac[N-1]=fp(fac[N-1],p-2);for(int i(N-1);i;--i) ifac[i-1]=1ll*i*ifac[i]%p;
        if(m%2==0)
        {
            d=1;f[0]=(m%4)?1:p-1;
            f[1]=1;
        }
        else f[0]=1;
        for(int i(2-(m&1));i<=m;i+=2)
        {
            int cur(0);
            for(int j(0),t(fac[i]);j<=i;j+=2,t=5ll*t%p)
            {
                cur=(cur+1ll*t*ifac[j]%p*ifac[i-j])%p;
            }
            cur=1ll*cur*fp(_2,i-1)%p;
            int b(((m-i)%4)?cur:p-cur);
            static int g[N];
            for(int t(0);t<=d+2;++t)
            {
                unsigned long long num((m&1)?p-f[t]:f[t]);
                if(t) num+=1ll*b*f[t-1];
                if(t>1) num+=f[t-2];
                g[t]=num%p;
            }
            d+=2;
            std::copy(g,g+d+1,f);
        }
        std::reverse(f,f+d+1);
        static int F[N],H[N];
        for(int i(0);i<d;++i)
        {
            if(i<2) fib[i]=1;
            else fib[i]=W(fib[i-1]+fib[i-2]);
            F[i]=fp(fib[i],m);
        }
        for(int i(0);i<d;++i)
        {
            for(int j(0);j<=i;++j) H[i]=(H[i]+1ll*f[j]*F[i-j])%p;
        }
        int iv(fp(H[0],p-2));
        for(int i(0);i<=n;++i)
        {
            int v(f[i]);
            for(int j(1);j<=i && j<d;++j) v=(v+1ll*(p-f[i-j])*H[j])%p;
            f[i]=1ll*v*iv%p;
        }
        std::cout<<(p-f[n])%p<<std::endl;
    }
    return 0;
}