;=2*n;j++)
printf("%d ",(p.mat[i][j]+m)%m);
printf("\n");
}
return 0;
}
由于构造的P矩阵中含有大量的0元素，因此可以考虑在矩阵相乘时进行优化，优化的方法是如果是0元素就不进行对应元素运算。优化后的矩阵相乘函数如下：
Matrix matMul(Matrix a ,Matrix b,int n,int m)
{
Matrix c;
memset(c.mat,0,sizeof(c.mat));
int i,j,k;
for (k = 1; k<=n ; k++)
for (i=1 ;i<=n ; i++)
if (a.mat[i][k]!=0)
for (j = 1 ;j<=n ;j++)
c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % m;
return c;
}
【例2】另类斐波那契数列。
已知斐波那契数列为：F(0) = 1，F(1) = 1，F(N) = F(N - 1) + F(N - 2) (N >= 2)。现定义一个新的类斐波那契数列： A(0) = 1，A(1) = 1，A(N) = X * A(N - 1) + Y * A(N - 2) (N >= 2)。
输入x、y和n，求新定义数列的前n项的平方和，即S(n)=A(0)^2+A(1)^2+....+A(n)^2。
（1）编程思路。
根据数列递推式不能直观地得到用于递推的矩阵，需要进行分析、构造。
因为 S[ n ] = S[ n -1 ] + A[n]^2
A[n]=X*A[n-1]+Y*A[n-2]
所以 S[n]=S[n-1]+X^2*A[n-1]^2+Y^2*A[n-2]^2+2XYA[n-1]*A[n-2]
等式的右边有四项，有变化的是S[ n-1]，A[n-1]^2，A[n-2]^2，A[n-1]*A[n-2]，各自的系数1，x^2，Y^2，2XY一经输入就确定了，不会再变化。
而有变化的四项S[ n-1]，A[n-1]^2，A[n-2]^2，A[n-1]*A[n-2]向前推进一步应该为
S[ n]，A[n]^2，A[n-1]^2，A[n]*A[n-1]。
这样，可以构造一个4*4的矩阵P。
为什么这样构造呢？是因为 （仔细体会一下哟!）
构造好矩阵P后，就可以采用矩阵快速幂运算求S(n)了。
（2）源程序。
#include <stdio.h>
#include <string.h>
#define MOD 10007
struct Matrix
{
int mat[5][5]; // 存储矩阵中各元素
};
Matrix matMul(Matrix a ,Matrix b,int n)
{
Matrix c;
memset(c.mat,0,sizeof(c.mat));
int i,j,k;
for (k = 1; k<=n ; k++)
for (i=1 ;i<=n ; i++)
if (a.mat[i][k]!=0)
for (j = 1 ;j<=n ;j++)
c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;
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(