自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 22:54:29，当前版本为作者最后更新于2024-01-20 19:53:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

通过找规律，发现 $f(n,m)$ 满足如下关系式：

$$f(2,m)=(m+1)^2$$ $$f(3,m)=\frac{1}{3}m^3+2m^2+\frac{8}{3}m+1$$ $$f(4,m)=\frac{7}{3}m^3+5m^2+\frac{11}{3}m+1$$ $$f(5,m)=\frac{7}{12}m^4 + \frac{17}{3}m^3+\frac{89}{12} m^2+\frac{13}{3}m+1 $$$$f(6,m)=\frac{25}{6}m^4 + \frac{38}{3}m^3+\frac{71}{6} m^2+\frac{16}{3}m+1 $$$$f(7,m)=\frac{5}{6}m^5 + \frac{37}{3}m^4 + \frac{133}{6}m^3+\frac{47}{3} m^2+6m+1 $$$$f(n,m) = 2f(n-1,m)+2m\cdot f(n-2,m)-(2m+2)f(n-3,m)-(m^2+2m-1)f(n-4,m)+2m\cdot f(n-5,m)+m^2f(n-6,m) $$

据此计算即可。时间复杂度 $O(n)$，可以优化到 $O(\log n)$。

核心代码：

int n;
modint m;
modint f[maxn];

signed main()
{
	n=read(),m=read(),initmod();
	f[2]=(m+1)*(m+1);
	f[3]=m*m*m/3+m*m*2+m*8/3+1;
	f[4]=m*m*m*7/3+m*m*5+m*11/3+1;
	f[5]=m*m*m*m*7/12+m*m*m*17/3+m*m*89/12+m*13/3+1;
	f[6]=m*m*m*m*25/6+m*m*m*38/3+m*m*71/6+m*16/3+1;
	f[7]=m*m*m*m*m*5/6+m*m*m*m*37/3+m*m*m*133/6+m*m*47/3+m*6+1;
	For(i,8,n)f[i]=f[i-1]*2+f[i-2]*2*m+f[i-3]*((-m)*2-2)+f[i-4]*((-m)*m-m*2+1)+f[i-5]*m*2+f[i-6]*m*m;
	cout<<f[n].x;
	return 0;
}

---

我们不加证明地猜测两个结论：

• 当 $n$ 固定时，答案是一个关于 $m$ 的多项式。
• 当 $m$ 固定时，答案序列 $f_n$ 存在一个较短的递推式。

首先写一个快一点的指数级暴力，比如对每种差分数组算上下界然后加起来，可以跑出 $n\le 13,0\le m\le 3$ 的结果。

据此可以 BM 求出 $1\le m\le 3$ 的所有递推式，发现第二条结论是正确的，而且递推式长度仅为 $6$：

• $m=1$：$(2,2,-4,-2,2,1)$
• $m=2$：$(2,4,-6,-7,4,4)$
• $m=3$：$(2,6,-8,-14,6,9)$

容易找规律观察出递推式为 $(2,2m,-(2m+2),-((m+1)^2-2),2m,m^2)$。

那现在问题在于固定 $m$ 求出 $f(2\sim 7,m)$ 的值，之后可以使用递推式。

由于第一条结论，可以暴力跑出 $n,m\le 8$ 的答案，然后插值求出 $n=2\sim 7$ 时 $m$ 满足的多项式。