自动搬运

查看原文

来自洛谷，原作者为

	xiaoyaowudi 想回到最初原点 拨琴弦唱起岁月 不畏惧未来渺远 只牵挂那心愿

搬运于2025-08-24 22:47:18，当前版本为作者最后更新于2023-06-21 15:50:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

其他题解都是 $\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;
}