51nod--1113 矩阵快速幂

1113 矩阵快速幂

基准时间限制：3 秒 空间限制：131072 KB 分值: 40 难度：4级算法题 收藏 关注
给出一个N * N的矩阵，其中的元素均为正整数。求这个矩阵的M次方。由于M次方的计算结果太大，只需要输出每个元素Mod (10^9 + 7）的结果。
Input
第1行：2个数N和M，中间用空格分隔。N为矩阵的大小，M为M次方。(2 <= N <= 100, 1 <= M <= 10^9)
第2 - N + 1行：每行N个数，对应N * N矩阵中的1行。(0 <= N[i] <= 10^9)
Output
共N行，每行N个数，对应M次方Mod (10^9 + 7)的结果。
Input示例
2 3
1 1
1 1
Output示例
4 4
4 4

/* 解题思路：快速幂的思想，如果不懂，先去百度把快速幂搞懂， 这题自然就很简单 */
code：
import java.util.Scanner;
public class Main{
    //之前这里的p写成(10e9+7)，结果不对，没有搞清是为啥，
    //有大神知道，请您给楼主留个言。
    static final long p = 1000000007;
    //e是单元矩阵
    static long[][] e = null; 
    //a是输入的矩阵
    static long[][] a = null;
    static int n = 0;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int m = sc.nextInt();
        a = new long[n][n];
        //init matrix
        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j)
                a[i][j] = sc.nextLong();
        //quickMatrix(m) is process
        long[][] result = quickMatrix(m);
        //output matrix
        for(int i=0; i<n; ++i){
            for(int j=0; j<n; ++j)
                System.out.print(result[i][j]+" ");
            System.out.println();
        }

    }
    //类似快速幂
    public static long[][] quickMatrix(int m){
        e = new long[n][n];
        //初始化为单位矩阵
        for(int i=0; i<n; ++i)
            e[i][i] = 1;
        while(m>0){
            if((m&1)==1)
                e = matrixMul(e,a);
            m >>= 1;
            a = matrixMul(a,a);
        }
        return e;
    }
    //this is 矩阵乘法
    public static long[][] matrixMul(long[][] a, long[][] b ){
        long[][] tem = new long[n][n];
        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j)
                for(int k=0; k<n; ++k){
                    tem[i][j] += (a[i][k]*b[k][j])%p;
                    tem[i][j] %=p;
                }
        return tem;
    }
}