自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:20:46，当前版本为作者最后更新于2020-04-19 19:07:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

打个表可以发现，对于第 $k$ 行（从零开始），实际上是公差为 $(a+b)^k$ 的等差数列，用归纳法可以证明：

对于第 $0$ 行，显然满足。

设第 $k$ 行有相邻三项 $x$，$x+(a+b)^k$，$x+2(a+b)^k$；

那么容易得出第 $k+1$ 行对应的两项为 $ax+bx+b(a+b)^k+c$ 和 $ax+a(a+b)^k+bx+2b(a+b)^k+c$；

做差得到 $(a+b)^{k+1}$，于是得证。

那么设 $f_n$ 为第 $n$ 行第一项的值，就有递推式：

直接矩阵快速幂即可，时间复杂度 $\Theta(\log n)$。