ACM数列问题
数列通项an=3an-1-2an-2(n>2,a1=2,a2=3),求数列的Sn,答案模9973,求大神用C来编,第一个数case(0<case<=100)表示测试数据的...
数列通项an=3an-1 - 2an-2 (n>2,a1=2,a2=3),求数列的Sn,答案模9973,求大神用C来编,第一个数case ( 0 < case <= 100 )表示测试数据的组数,每组测试数据有一行,每行一个整数n( 0 < n < =
1,000,000,000 )。 据说是用矩阵快速幂,没学过,求详解。 展开
1,000,000,000 )。 据说是用矩阵快速幂,没学过,求详解。 展开
展开全部
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)
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询