自动搬运

查看原文

来自洛谷，原作者为

	ezoixx130 浴乎沂，风乎舞雩，咏而归

搬运于2025-08-24 22:07:16，当前版本为作者最后更新于2018-12-23 12:41:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这里讲一种不用生成函数什么的东西求通项公式的方法：待定系数法

首先 $\Large a_n=233a_{n-1}+666a_{n-2},a_0=0,a_1=1$

设$\Large a_{n+2}+pa_{n+1}=q(a_{n+1}+pa_n)$

则$\Large p,q$ 满足$\Large q-p=233$ ， $\Large pq=666$

即$\Large q^2-233q-666=0$

解得$\Large q=\frac{233\pm\sqrt{56953}}{2},p=\frac{-233\pm\sqrt{56953}}{2}$

当$\Large q=\frac{233+\sqrt{56953}}{2},p=\frac{-233+\sqrt{56953}}{2}$ 时

$\Large a_{n+2}+\frac{-233+\sqrt{56953}}{2}a_{n+1}=\frac{233+\sqrt{56953}}{2}(a_{n+1}+\frac{-233+\sqrt{56953}}{2}a_n)$ （①式）

设$\Large b_n=a_{n+1}+\frac{-233+\sqrt{56953}}{2}a_n$

则$\Large b_{n+1}=a_{n+2}+\frac{-233+\sqrt{56953}}{2}a_{n+1}$

将上两式代入①式得$\Large b_{n+1}=\frac{233+\sqrt{56953}}{2}b_n$

于是我们知道了$\Large \{b_n\}$ 是等比数列。

又因为$\Large b_1=a_2+\frac{-233+\sqrt{56953}}{2}a_1=233+\frac{-233+\sqrt{56953}}{2}$

所以$\Large b_n=(\frac{233+\sqrt{56953}}{2})^{n-1}(233+\frac{-233+\sqrt{56953}}{2})=(\frac{233+\sqrt{56953}}{2})^n$

所以$\Large a_{n+1}+\frac{-233+\sqrt{56953}}{2}a_n=(\frac{233+\sqrt{56953}}{2})^n$

当$\Large q=\frac{233-\sqrt{56953}}{2},p=\frac{-233-\sqrt{56953}}{2}$ 时

同理得到$\Large a_{n+1}+\frac{-233-\sqrt{56953}}{2}a_n=(\frac{233-\sqrt{56953}}{2})^n$

上两式相减就可以得到$\Large \sqrt{56953}a_n=(\frac{233+\sqrt{56953}}{2})^n-(\frac{233-\sqrt{56953}}{2})^n$

$\Large a_n=\frac{(\frac{233+\sqrt{56953}}{2})^n-(\frac{233-\sqrt{56953}}{2})^n}{\sqrt{56953}}$

这就已经是这个数列的通项公式了。

但是我们只需要求这个数列在模$\Large 10^9+7$意义下的值，因此还可以继续推。

我们要求$\Large \sqrt{56953}$ 在模$\Large 10^9+7$意义下的值，就是要找到满足$\Large x^2 \equiv 56953 (\mod 10^9+7)$的$\Large x$ 。然后我们发现出题人选数选得刚刚好，我们找到了$\Large 188305837^2 \equiv 56953 (\mod 10^9+7)$ 。

然后就可以推出$\Large a_n \equiv \frac{(\frac{233+188305837}{2})^n-(\frac{233-188305837}{2})^n}{188305837} (\mod 10^9+7)$

最后得到$\Large a_n=233230706(94153035^n-905847205^n) (\mod 10^9+7)$

完美！

然后就可以用光速幂每次$O(1)$ 求答案了。