6470.count --快速矩阵幂

大佬再看看那里可以优化没有
https://www.jianshu.com/p/25eba927d9da
题目转化为：F(n+1) = F(n) + 2F(n-1) + n4 + 4n3 + 6n2 + 4n + n0
状态转移矩阵
辣鸡6470 java写答案正确就是超时 怪不得没人用java写~~ 果然写算法还是建议用c++写 迅速快~~

import java.util.Scanner;
public class Main {
	public static long quick_pow(long a[][], long b) {
		long temp[][] = {{1,0,0,0,0,0},{0,1,0,0,0,0},{0,0,1,0,0,0},{0,0,0,1,0,0},{0,0,0,0,1,0},{0,0,0,0,0,1}};
		while (b > 0) {
			if (b % 2 == 1)
				temp = mul(a, temp);
			a = mul(a, a);
			b = b >> 1;
		}
		long z[][] = { { 1 }, { 2 }, { 8 }, { 4 }, { 2 }, { 1 } };
		long res[][] = mul(temp,z);
		return res[1][0];
	}
	public static long[][] mul(long a[][],long b[][]) {
		long res[][] = new long[a[0].length][b.length];
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < b[0].length; j++) {
				res[i][j] = 0;
				for (int k = 0; k < a[0].length; k++) {
					res[i][j] += (a[i][k] % 123456789) * (b[k][j] % 123456789);
				}
                res[i][j]%=123456789;
			}
		}
		return res;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int i = sc.nextInt();
			while(i-->0) {
			long n = sc.nextLong();
			if (n == 1 || n == 2) {
				System.out.println(n);
			} else {
				long a[][] = { 
						{ 0, 1, 0, 0, 0, 0 },
						{ 2, 1, 1, 3, 3, 1 }, 
						{ 0, 0, 1, 3, 3, 1 }, 
						{ 0, 0, 0, 1, 2, 1 },
						{ 0, 0, 0, 0, 1, 1 },
						{ 0, 0, 0, 0, 0, 1 } };
				System.out.println(quick_pow(a, n - 2));
				// 这里要减2 因为从F2开始
			}
		}
	}
}
	}