递推求值
时间限制：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<stdio.h>
#include<string.h>
using namespace std;
long long m,n,a,b,c,k;
long long mol=1000007;
long long x1,x2,x3;
long long y1,y2,y3;
long long z1,z2,z3;
void fun()
{
long long h=k;
if(h==1){printf("%d\n",m);return;}
if(h==2){printf("%d\n",n);return;}
long long r1=1,r2=0,r3=0;
long long s1=0,s2=1,s3=0;
long long t1=0,t2=0,t3=1;h-=2;
while(h>=1)
{
int o1,o2,o3,p1,p2,p3,q1,q2,q3;
if(h%2==1)
{
o1=(r1*x1+s1*x2+t1*x3)%mol;p1=(r1*y1+s1*y2+t1*y3)%mol;q1=(r1*z1+s1*z2+t1*z3)%mol;
o2=(r2*x1+s2*x2+t2*x3)%mol;p2=(r2*y1+s2*y2+t2*y3)%mol;q2=(r2*z1+s2*z2+t2*z3)%mol;
o3=(r3*x1+s3*x2+t3*x3)%mol;p3=(r3*y1+s3*y2+t3*y3)%mol;q3=(r3*z1+s3*z2+t3*z3)%mol;
r1=o1;r2=o2;r3=o3;s1=p1;s2=p2;s3=p3;t1=q1;t2=q2;t3=q3;
}
o1=(x1*x1+y1*x2+z1*x3)%mol;p1=(x1*y1+y1*y2+z1*y3)%mol;q1=(x1*z1+y1*z2+z1*z3)%mol;
o2=(x2*x1+y2*x2+z2*x3)%mol;p2=(x2*y1+y2*y2+z2*y3)%mol;q2=(x2*z1+y2*z2+z2*z3)%mol;
o3=(x3*x1+y3*x2+z3*x3)%mol;p3=(x3*y1+y3*y2+z3*y3)%mol;q3=(x3*z1+y3*z2+z3*z3)%mol;
x1=o1;x2=o2;x3=o3;y1=p1;y2=p2;y3=p3;z1=q1;z2=q2;z3=q3;
h/=2;
}
n=(m*r2+n*s2+t2)%mol;
n=(n+mol)%mol;
printf ("%d\n",n);
}
int main()
{
int N;
cin>>N;
while(N--)
{
// scanf("%d%d%d%d%d%d",&m,&n,&a,&b,&c,&k);
cin>>m>>n>>a>>b>>c>>k;
x1=0;y1=1;z1=0;
x2=a;y2=b;z2=c;
x3=0;y3=0;z3=1;
fun();
}
}