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开始
            }
        }
    }
}
    }