NYOJ——301递推求值（矩阵快速幂）
递推求值
时间限制：1000 ms | 内存限制：65535 KB
难度：4
描述
给你一个递推公式：
f(x)=a*f(x-2)+b*f(x-1)+c
并给你f(1),f(2)的值，请求出f(n)的值，由于f(n)的值可能过大，求出f(n)对1000007取模后的值。
注意:-1对3取模后等于2
输入
第一行是一个整数T,表示测试数据的组数(T<=10000)
随后每行有六个整数，分别表示f(1),f(2),a,b,c,n的值。
其中0<=f(1),f(2)<100,-100<=a,b,c<=100,1<=n<=100000000 (10^9)
输出
输出f(n)对1000007取模后的值
样例输入
2
1 1 1 1 0 5
1 1 -1 -10 -100 3
样例输出
5
999896
之前一直玩二维的，发现三维的矩阵也蛮容易构造的。新编辑器蛮好用。
代码：
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const LL mod=1000007;
struct mat
{
LL pos[3][3];
mat(){memset(pos,0,sizeof(pos));}
};
inline mat operator*(const mat &a,const mat &b)
{
int i,j,k;
mat c;
for (i=0; i<3; i++)
{
for (j=0; j<3; j++)
{
for (k=0; k<3; k++)
{
c.pos[i][j]+=(((a.pos[i][k])%mod)*(b.pos[k][j])%mod+mod)%mod;
}
}
}
return c;
}
inline mat matpow(mat a,LL b)
{
mat r,bas;
r.pos[0][0]=r.pos[1][1]=r.pos[2][2]=1;
bas=a;
while (b!=0)
{
if(b&1)
r=r*bas;
bas=bas*bas;
b>>=1;
}
return r;
}
int main(void)
{
ios::sync_with_stdio(false);
LL a,b,c,n,f1,f2;
int tcase;
while (cin>>tcase)
{
while (tcase--)
{
cin>>f1>>f2>>a>>b>>c>>n;
if(n==1)
cout<<f1<<endl;
else if(n==2)
cout<<f2<<endl;
else
{
mat t,one;
t.pos[0][0]=b,t.pos[0][1]=a,t.pos[0][2]=c;
t.pos[1][0]=t.pos[2][2]=1;
one.pos[0][0]=f2,one.pos[1][0]=f1,one.pos[2][0]=1;
t=matpow(t,n-2);
one=t*one;
cout<<one.pos[0][0]%mod<<endl;
}
}
}
return 0;
}