Question

ACM数列问题

数列通项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 ）。 据说是用矩阵快速幂，没学过，求详解。

Answer 1

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)