题解 P6435 【「EZEC-1」数列】

· · 题解

打个表可以发现，对于第 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 行第一项的值，就有递推式：

f_n=af_{n-1}+b\left(f_{n-1}+(a+b)^n\right)+c =(a+b)f_{n-1}+b(a+b)^n+c

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