学步园

1，http://www.matrix67.com/blog/archives/276比较好的矩阵二分幂文章

2，对于递推辅助矩阵的计算，参考http://wenku.baidu.com/view/42f0080c4a7302768e99390d.html

递推求值

描述

给你一个递推公式：

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

import java.util.Arrays;
import java.util.Scanner;
class Matrix
{
	long f1,f2,a,b,c,n;
	int size=3,mod=1000007;
	long matarray[][]=new long[size][size];
	long finalarray[][]=new long[size][size];
	long midarray[][]=new long[size][size];
	public Matrix(Long f1,long f2,long a,long b,long c,long n)
	{
		for(int i=0;i<size;i++)
		{
			Arrays.fill(matarray[i], 0);
			Arrays.fill(finalarray[i], 0);
			Arrays.fill(midarray[i], 0);
		}
		this.f1=f1;this.f2=f2;this.a=a;this.b=b;this.c=c;this.n=n;
		matarray[0][1]=a;matarray[1][0]=1;matarray[1][1]=b;matarray[2][1]=1;matarray[2][2]=1;
		finalarray[0][0]=f1;finalarray[0][1]=f2;finalarray[0][2]=c;
		copyarray(midarray,matarray);
	}
	public void copyarray(long a[][],long b[][])
	{
		for(int i=0;i<size;i++)
		{
			for(int j=0;j<size;j++)
				a[i][j]=b[i][j];
		}
	}
	public void multiply(long mata[][],long matb[][])
	{
		long temp[][]=new long[size][size],sum;
		for(int i=0;i<size;i++)
		{
			for(int j=0;j<size;j++)
			{
				sum=0;
				for(int k=0;k<size;k++)
				{
					sum+=mata[i][k]*matb[k][j]%mod;
				}
				temp[i][j]=(sum+mod)%mod;
			}
		}
		copyarray(mata, temp);
	}
	public void binary(long n)
	{
		if(n==1)return;
		binary(n>>1);
		multiply(matarray,matarray);
		if(n%2==1)
			multiply(matarray, midarray);
	}
	public long result()
	{
		if(n>1)
		{
			binary(n-1);
			multiply(finalarray, matarray);
		}
		return (finalarray[0][0]%mod+mod)%mod;
	}
}

public class Main {
	public static void main(String[] args) {
	Scanner scanner=new Scanner(System.in);
	int cases=scanner.nextInt();
	while(cases--!=0)
	{
		long f1,f2,a,b,c,n;
		f1=scanner.nextLong();
		f2=scanner.nextLong();
		a=scanner.nextLong();
		b=scanner.nextLong();
		c=scanner.nextLong();
		n=scanner.nextLong();
		Matrix matrix=new Matrix(f1, f2, a, b, c, n);
		System.out.println(matrix.result()%1000007);
	}

	}

}