数论出题组比赛用题：数列

T3:数列

思考难度：提高?

代码难度：提高?

算法0：暴力

实际得分：0

算法1：

考虑 $x=y=1$x=y=1的情况，显然有 $a_n=a_{n-1}+a_{n-2}$an​=an−1​+an−2​(废话)，故

$a_n\times a_{n+1}$an​×an+1​

$=a_n\times (a_n+a_{n-1})$=an​×(an​+an−1​)

$=a_n^2+a_{n-1}\times a_n$=an2​+an−1​×an​

$=a_n^2+a_{n-1}^2+a_{n-2}\times a_{n-1}$=an2​+an−12​+an−2​×an−1​

$=...+a_2^2+a_1\times a_2$=...+a22​+a1​×a2​

$=...+a_2^2+a_1^2+a_1\times (a_2-a_1)$=...+a22​+a12​+a1​×(a2​−a1​)

故 $ans=a_n\times a_{n+1}-a_1\times (a_2-a_1)$ans=an​×an+1​−a1​×(a2​−a1​)

实际得分：20分

算法2：

注意到

$a_n^2=(x\times a_{n-1}+y\times a_{n-2}{)}^2$an2​=(x×an−1​+y×an−2​)2

$=x^2\times a_{n-1}^2+y^2\times a_{n-2}^2+2xy\times a_{n-1}\times a_{n-2}$=x2×an−12​+y2×an−22​+2xy×an−1​×an−2​

$=x^2\times a_{n-1}^2+y^2\times a_{n-2}^2+2xy\times a_{n-2}\times (x\times a_{n-2}+y\times a_{n-3})$=x2×an−12​+y2×an−22​+2xy×an−2​×(x×an−2​+y×an−3​)

$=x^2\times a_{n-1}^2+y^2\times a_{n-2}^2+2xy\times (x\times a_{n-2}^2+y\times a_{n-2}\times a_{n-3})$=x2×an−12​+y2×an−22​+2xy×(x×an−22​+y×an−2​×an−3​)

故 $a_n^2$an2​可以由 $a_{n-1}^2,a_{n-2}^2,a_{n-1}\times a_{n-2}$an−12​,an−22​,an−1​×an−2​转移过来，而 $a_{n-1}\times a_{n-2}$an−1​×an−2​可以由 $a_{n-1}^2,a_{n-2}\times a_{n-3}$an−12​,an−2​×an−3​转移过来。

矩阵加速即可。

实际得分：100