题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1005
题意：
数列{f(n)}: f(1) = 1, f(2) = 1, f(n) = ( A*f(n-1) + B*f(n-2) ) MOD 7
给定A、B、n，求f(n)。 (1<=n<=100,000,000)
题解：
大水题~ (*/ω＼*)
矩阵快速幂。
初始矩阵start：
特殊矩阵special：
所求矩阵ans：
ans = start * special^(n-1)
ans的第一项即为f(n)。
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_L 5
#define MOD 7 using namespace std; struct Mat
{
int n;
int m;
int val[MAX_L][MAX_L];
Mat()
{
n=;
m=;
memset(val,,sizeof(val));
}
}; int a,b,n; Mat make_unit(int n)
{
Mat mat;
mat.n=n;
mat.m=n;
for(int i=;i<n;i++)
{
mat.val[i][i]=;
}
return mat;
} Mat make_start()
{
Mat mat;
mat.n=;
mat.m=;
mat.val[][]=;
mat.val[][]=;
return mat;
} Mat make_special()
{
Mat mat;
mat.n=;
mat.m=;
mat.val[][]=;
mat.val[][]=b;
mat.val[][]=;
mat.val[][]=a;
return mat;
} Mat mul_mat(const Mat &a,const Mat &b)
{
Mat c;
if(a.m!=b.n)
{
cout<<"Error: mat_mul"<<endl;
return c;
}
c.n=a.n;
c.m=a.m;
for(int i=;i<a.n;i++)
{
for(int j=;j<b.m;j++)
{
for(int k=;k<a.m;k++)
{
c.val[i][j]+=a.val[i][k]*b.val[k][j];
c.val[i][j]%=MOD;
}
}
}
return c;
} Mat quick_pow_mat(Mat mat,long long k)
{
Mat ans;
if(mat.n!=mat.m)
{
cout<<"Error: quick_pow_mat"<<endl;
return ans;
}
ans=make_unit(mat.n);
while(k)
{
if(k&)
{
ans=mul_mat(ans,mat);
}
mat=mul_mat(mat,mat);
k>>=;
}
return ans;
} int main()
{
while(cin>>a>>b>>n)
{
if(a== && b== && n==) break;
Mat start=make_start();
Mat special=make_special();
Mat ans=mul_mat(start,quick_pow_mat(special,n-));
cout<<ans.val[][]<<endl;
}
}