ACM数列问题数列通项an=3an-1 - 2an-2 （n>2,a1=2,a2=3）,求数列的Sn,答案模9973,求

Sn是求和吗?
先说说求an对9973取余吧


对于这个数列我们要构造一个矩阵


我们构造矩阵的目的,就是要从低阶向高阶推.


比如,我们现在有an,a(n-1)
那么我们想要推出a(n+1)


由于这儿每一次都是两项推出一项的,所以矩阵每一次都有两项.


由上述式子,我们可以构造矩阵
[3,-2][an]
[1,0 ][a(n-1)]


=
[a(n+1)]
[an]


这样我们就实现了递推.


那么对于任意的an(n>2)
我们可以
[3,-2]^(n-2)[a2]
[1,0 ][a1]


=
[an]
[a*(n-1)]


[3,-2]^(n-2)
[1,0 ]


这一部分,我们可以先用矩阵的快速幂计算出结果.


总复杂度是2*2*2*log(n)