矩阵乘法，特别是矩阵快速幂运算在实际中的应用非常广泛。例如，利用矩阵乘法可以方便快速地求解线性递推关系。
例如，我们知道斐波拉契数列具有如下线性递推关系：
F(0)=0 F(1)=1
F(n)= F(n-1) + F(n-2) (n>=2)
构造一个矩阵，可以利用矩阵乘法完成递推。如下所示。
【例1】斐波拉契数列第n项。
输入整数n (0 ≤ n ≤ 1,000,000,000)，求斐波拉契数列第n项的值。由于F(n)值很大，要求只输出其模10000的结果。
例如，输入 9 ，输出 34 ； 输入 999999999 ，输出 626 ；
输入 1000000000，输出 6875。
（1）编程思路。
利用矩阵的快速幂运算完成F(n)的计算。
（2）源程序1。
#include <stdio.h>
#include <string.h>
#define MODNUM 10000
struct Matrix
{
__int64 mat[3][3]; // 存储矩阵中各元素
};
Matrix matMul(Matrix a ,Matrix b,int n)
{
Matrix c;
memset(c.mat,0,sizeof(c.mat));
int i,j,k;
for (i = 1; i<=n ; i++)
for (j=1 ;j<=n ; j++)
for (k = 1 ;k<=n ;k++)
{
c.mat[i][j]=(c.mat[i][j]+a.mat[i][k] * b.mat[k][j]) % MODNUM;
}
return c;
}
Matrix quickMatPow(Matrix a ,int n,int b) // n阶矩阵a快速b次幂
{
Matrix c;
memset(c.mat ,0 ,sizeof(c.mat));
int i;
for (i = 1 ;i <= n ;i++)
c.mat[i][i] = 1;
while (b!=0)
{
if (b & 1)
c = matMul(c ,a ,n); // c=c*a;
a = matMul(a ,a ,n); // a=a*a
b /= 2;
}
return c;
}
int main()
{
int n ;
Matrix p ;
while(scanf("%d", &n) && n != -1)
{
if (n==0 )
printf("0\n");
else
{
p.mat[1][1]=1; p.mat[1][2]=1;
p.mat[2][1]=1; p.mat[2][2]=0;
p = quickMatPow(p,2,n);
printf("%d\n", p.mat[2][1]);
}
}
return 0;
}
源程序1直接采用本博客上一篇文章中的快速幂运算函数实现的。由于本题中构造矩阵为2*2，因此可以编写一个简洁的程序。
（3）源程序2。
#include <stdio.h>
struct matrix {
__int64 s11 , s12 , s21 , s22 ;
};
matrix f(matrix a,matrix b)
{
matrix p ;
p.s11 = (a.s11*b.s11 + a.s12*b.s21)%10000;
p.s12 = (a.s11*b.s12 + a.s12*b.s22)%10000;
p.s21 = (a.s21*b.s11 + a.s22*b.s21)%10000;
&nbs