题解 P5517 【[MtOI2019]幻想乡数学竞赛】

· · 题解

出题人是没怎么学过数列的相关套路知识吗...

感觉他的解法非常复杂啊，为什么连生成函数都用到了...

给一个简单的思路吧，不放代码。

a_{n}=3a_{n-1}+a_{n-2}-3a_{n-3}+3^n a_{n}-a_{n-2}=3a_{n-1}-3a_{n-3}+3^n

设b_n=a_n-a_{n-2}，就有

b_1=-6,b_2=-9 b_n=3b_{n-1}+3^n \frac {b_n}{3^n}=\frac {b_{n-1}}{3^{n-1}}+1

设c_n=\frac {b_n}{3^n}，就有

c_n=c_{n-1}+1 c_1=-2,c_2=-1,c_n=n-3

代回去，利用错项相交即可得到通项公式。

就是这样...

做一道数列小题还是蛮合适的。