)
{
int n,x,y,ans;
Matrix p;
while(scanf("%d%d%d" ,&n ,&x ,&y)!=EOF)
{
x = x%MOD;
y = y%MOD ;
if (n==2)
printf("%d\n" ,(x*x%MOD+y*y%MOD+2*x*y%MOD+2)%MOD) ;
else
{
memset(p.mat,0,sizeof(p.mat));
p.mat[1][1]=p.mat[3][2]=1;
p.mat[1][2]=p.mat[2][2]=(x*x)%MOD;
p.mat[1][3]=p.mat[2][3]=(y*y)%MOD;
p.mat[1][4]=p.mat[2][4]=(2*x*y)%MOD;
p.mat[4][2]=x;
p.mat[4][4]=y;
p = quickMatPow(p,4,n-1);
ans=(p.mat[1][1]*2%MOD+p.mat[1][2]+p.mat[1][3]+p.mat[1][4])%MOD;
printf("%d\n" ,ans);
}
}
return 0;
}
将此源程序提交给 HDU 3306 “Another kind of Fibonacci”，可以Accepted。
【例3】又一个非线性递推数列。
设有数列F的定义如下：f[1] =a，f[2]=b， f(n)=f(n-1)+f(n-2)*2+n^4 （n>=3）。
输入a、b和n的值， 求f[n] mod 2147493647的结果。
（1）编程思路。
通过本题可以更进一步思考用于递推的矩阵的构造方法。
因为 f(n)=f(n-1)+f(n-2)*2+n^4
f(n-1)=f(n-2)+f(n-3)*2+(n-1)^4
因此，构造矩阵时的关键是找到怎样由(n-1)^4到n^4的递推。
又由于 n^4=(n-1+1)^4=(n-1)^4 + 4 (n-1)^3 + 6 (n-1)^2 + 4 (n-1)^1 +1，因此，需要通过构造
矩阵维护好f(n-1)、f(n-2)、(n-1)^4、(n-1)^3、(n-1)^2、(n-1)^1和(n-1)^0这7个值。
可以构造P矩阵如下：
为什么这样构造呢？是因为 （好好体会哟！）
构造好矩阵P后，就可以采用矩阵快速幂运算求f(n)了。
（2）源程序。
#include <stdio.h>
#include <string.h>
#define MOD 2147493647
struct Matrix
{
__int64 mat[8][8]; // 存储矩阵中各元素
};
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次幂
{