问题标题：
ACM数列问题数列通项an=3an-1-2an-2（n>2,a1=2,a2=3）,求数列的Sn,答案模9973,求大神用C来编,第一个数case（0<case
问题描述：
ACM数列问题
数列通项an=3an-1-2an-2（n>2,a1=2,a2=3）,求数列的Sn,答案模9973,求大神用C来编,第一个数case（0
庞政铎回答：
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)
查看更多
八字精批
八字合婚
八字起名
八字财运
2024运势
测终身运
姓名详批
结婚吉日
