题目描述：
给定a0,a1,以及an=p*a(n-1) + q*a(n-2)中的p,q。这里n >= 2。 求第k个数对10000的模。
输入：
输入包括5个整数：a0、a1、p、q、k。
输出：
第k个数a(k)对10000的模。
样例输入：
20 1 1 14 5
样例输出：
8359
代码：
本题最直观的方法是根据公式一步一步求出ａ(ｋ)，如下
#include <stdio.h>
int main (void)
{
unsigned long long int a,a0,a1,p,q;
int k;
while (scanf("%llu%llu%llu%llu%d",&a0,&a1,&p,&q,&k) != EOF)
{
if (k == 0) a = a0;
if (k == 1) a = a1;
while ( k-1 > 0)
{
if (a1 > 10000) a1 %= 10000;
if (a0 > 10000) a0 %= 10000;
a = p*a1 + q*a0;
a0 = a1; a1 = a;
--k;
}
printf ("%llu\n",a % 10000);
}
return 0;
}
对于ｋ比较小的情况，这种方法还可以，但是ｋ比较大时就不行了，代码提交上去会返回TLE（超时），这段代码的时间复杂度为O(n)，所以我们要想办法把时间复杂度降低。这里有一个比较好的办法就是采用矩阵的方法。以前学习线性代数的时候，对矩阵的认识不够深刻，所以一开始并没有体会到用矩阵会有什么用处。先来看看这个题和矩阵的关系。
（1）
（2）
上面两个公式列出来，应该就会有所启发，会发现矩阵和乘法和数列递推公式之间的关系，那么，转化为矩阵之后有什么好处呢？我们要求一个数列的第n项，如果知道这个数列的通项公式就好了，可是这个递推公式的通项公式却不好求。转化为矩阵运算后，就可以很容易写出a(k),a(k-1)和a(0),a(1)之间的关系：
（3）
这里出现了矩阵M的(k-1)次幂，这对我们是一个启发，这时候就可以用二分法进行计算，我对二分法举一个例子：
M^5 = MMMMM; (5次乘法)
M^5 = ((M^2)^2)*M; (3次乘法)
第二种乘法运算就使用了二分法减少了乘法运算的次数。这样计算M^n算法时间复杂度可以从O(n)降低到O(lgn)，这正好符合前面提出的目标。
相应的实现如下：
#include <stdio.h>
#define MOD 10000
// m = m * n
void MatrixMul ( int m[2][2], int n[2][2] )
{
int s[2][2]={{0,0},{0,0}};
int i, j, k;
for(i=0;i<2;i++)
for(j=0;j<2;j++)
for(k=0;k<2;k++)
s[i][j]+=m[i][k]*n[k][j];
for(i=0;i<2;i++)
for(j=0;j<2;j++)
m[i][j]=s[i][j]%MOD;
}
// m = m^n
void MatrixN ( int m[2][2], int n )
{
int t[2][2]={{m[0][0],m[0][1]},{m[1][0],m[1][1]}};
if (n==1) return;
else if (n%2==0)
{
MatrixN(m,n/2);
MatrixMul(m,m);
}
else
{
MatrixN(m,n-1);
MatrixMul(m,t);
}
}
int main(void)
{
int a,a0,a1,p,q,k;
int m[2][2];
while (scanf("%d%d%d%d%d",&a0,&a1,&p,&q,&k) != EOF)
{
if (k==0) a = a0;
else if (k==1) a = a1;
else
{
m[0][0] = p%MOD; m[0][1] = q%MOD;
m[1][0] = 1; m[1][1] = 0;
MatrixN(m,k-1);
a = m[0][0]*a1+m[0][1]*a0;
}
printf ("%d\n", a%MOD);
}
return 0;
}
实现很简单，和上面的公式是对应的，就不多说了，从这里我们也可以看出数学工具对思维的巨大帮助，有了矩阵这一工具，可以很大程度上减少思维上的困难，其实用矩阵也是作乘法加法运算，但是如果不使用矩阵，就不容易想像到这样的计算过程。当初学习线性代数的时候，并没有意识到矩阵的妙用，所以需要使用时也不会用。这给我提了一个醒，学习理论，一定要搞明白这种理论有什么用处，不然不算学明白了。而遇到实际的问题想不出来时，一定需要及时补充理论知识。