f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
Sample Input
1 1 3 //a b n
1 2 10
0 0 0
Sample Output
2
5
矩阵A * 矩阵B = 矩阵C
a b f(n-1) f(n)
1 0 f(n-2) f(n-1)
# include <iostream>
# include <cstdio>
# include <algorithm>
# include <map>
# include <cmath>
# define LL long long
using namespace std ; const int MOD = ; struct Matrix
{
int mat[][];
}; Matrix mul(Matrix a,Matrix b) //矩阵乘法
{
Matrix c;
for(int i=;i<;i++)
for(int j=;j<;j++)
{
c.mat[i][j]=;
for(int k=;k<;k++)
{
c.mat[i][j]=(c.mat[i][j] + a.mat[i][k]*b.mat[k][j])%(MOD);
}
}
return c;
}
Matrix pow_M(Matrix a,int k) //矩阵快速幂
{
Matrix ans;
memset(ans.mat,,sizeof(ans.mat));
for (int i=;i<;i++)
ans.mat[i][i]=;
Matrix temp=a;
while(k)
{
if(k&)ans=mul(ans,temp);
temp=mul(temp,temp);
k>>=;
}
return ans;
} int main ()
{
// freopen("in.txt","r",stdin) ;
int a,b,n;
while(scanf("%d%d%d" , &a,&b,&n) != EOF)
{
if (a== && b== && n==)
break ;
if (n <= )
{
printf("1\n") ;
continue ;
}
Matrix t ;
t.mat[][] = a ;
t.mat[][] = b ;
t.mat[][] = ;
t.mat[][] = ;
Matrix ans = pow_M(t,n-) ;
printf("%d\n" , (ans.mat[][] + ans.mat[][])%MOD) ; } return ;
}