题解 P5110 【块速递推】

ezoixx130 · 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 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 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) 求答案了。