题解 P5110 【块速递推】

这里讲一种不用生成函数什么的东西求通项公式的方法：待定系数法 首先 $\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)$ 求答案了。