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

T3:数列

思考难度：提高?

代码难度：提高?

算法0：暴力

实际得分：0

算法1：

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

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

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

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

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

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

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

故ans=an×an+1−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：

注意到

an2=(x×an−1+y×an−2)2a_n^2=(x\times a_{n-1}+y\times a_{n-2})^2an2​=(x×an−1​+y×an−2​)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-1}\times a_{n-2}=x2×an−12​+y2×an−22​+2xy×an−1​×an−2​

=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 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​)

=x2×an−12+y2×an−22+2xy×(x×an−22+y×an−2×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​)

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

矩阵加速即可。

实际得分：100

转载于:https://www.cnblogs.com/vercont/p/10210016.html

相关资源：数据结构—成绩单生成器