zzuli 1605 数字序列 （矩阵快速幂取模）
题目描述
一个数列的定义如下：
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
给出A和B，你要求出f(n).
输入
输入包含多个测试案例。每个测试用例包含3个整数A，B和n在一行（1＜＝A，B≤1000，1≤n≤100000000）。
当输入三个0表示结束
输出
对于每个测试案例，输出f(n)，单独占一行。
样例输入
1 1 3
1 2 10
0 0 0 样例输出
2
5 分析：斐波那契数列的变种题目，很容易可以推出系数矩阵
那么这个矩阵的n-3次方乘以初始矩阵A0(A0[1][1]=f(2)，A0[2][1]=f(1)，其余均为0)，得到的矩阵C的第1行第1列的数字就是答案。
注意：矩阵乘法不满***换律！
代码：
#include<stdio.h>
const long long int maxn=20,mod=7;
struct matrix
{
long long int s[maxn][maxn];
};
long long int a,b;
matrix res,ans;
matrix mul(matrix A,matrix B,long long int n)
{
matrix C;
for(long long int i = 1 ; i<=n ; i++)
for(long long int j= 1 ; j<=n ; j++)
C.s[i][j]=0;
for(long long int i= 1 ; i<=n ; i++)
for(long long int j=1 ; j<= n ; j++)
for(long long int k = 1 ; k<= n; k++)
C.s[i][j]+=A.s[i][k]*B.s[k][j];
return C;
}
void quick(long long int y,long long int n)
{
ans.s[1][1]=a;
ans.s[1][2]=b;
ans.s[2][1]=1;
ans.s[2][2]=0;
res=ans;
while(y)
{
if(y&1)
ans=mul(ans,res,n);
res = mul(res,res,n);
for(int i =1 ; i<=2 ; i++)
{
for(int j =1 ; j<=2 ; j++)
{
ans.s[i][j]%=mod;
res.s[i][j]%=mod;
}
}
y=y>>1;
}
}
int main()
{
long long int n=2,y;
while(scanf("%lld%lld%lld",&a,&b,&y),y||a||b)
{
if(y<=2)
{
printf("1\n");
continue;
}
y-=3;
quick(y,n);
matrix ans0;
for(int i=1 ;i<=n;i++)
for(int j=1 ;j<=n ;j++)
ans0.s[i][j]=0;
ans0.s[1][1]=1;
ans0.s[2][1]=1;
ans0=mul(ans,ans0,n);
/* for(int i=1 ;i<3 ;i++)
{
for(int j=1 ;j<3 ;j++)
printf("%lld ",ans0.s[i][j]);
puts("");
}*/
printf("%lld\n",ans0.s[1][1]%mod);
}
return 0;
}
