51nod1113 矩阵快速幂

51nod1113：矩阵快速幂
先修知识：矩阵乘法、快速幂。最终还是要面对矩阵快速幂。

矩阵快速幂总结：

计算矩阵乘法的前提条件是：矩阵A的列==矩阵B的行。
但矩阵快速幂只会用到方阵，因而也就避免了矩阵相乘的先决条件。
另外，用java的类来模拟c++的结构体，简化代码量。
最后，矩阵的实质是线性代数，emmm…好好学线代吧。

import java.util.Scanner;

class S {// i行j列的矩阵数组
	int i, j;
	long[][] sz;

	public S(int i, int j) {
		this.i = i;
		this.j = j;
		sz = new long[i][j];
	}
}

public class Main {
	static long mod = (long) (Math.pow(10, 9) + 7);

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = n;// 方阵
		S a = new S(n, m);// 实例化矩阵类
		S c = new S(n, m);// 结果矩阵
		long b = in.nextLong();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				a.sz[i][j] = in.nextLong();
			}
		}
		c = pow2(a, b);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				System.out.print(c.sz[i][j] + " ");
			}
			System.out.println();
		}
	}

	private static S pow2(S a, long b) // 求矩阵a(方阵)的b次幂
	{
		S c = new S(a.i, a.j);
		for (int x = 0; x < a.i; x++)
			// 建立一个对角线均为1的矩阵
			c.sz[x][x] = 1;
		while (b != 0) {
			if ((b & 1) == 1) {
				c = mul(c, a);
			}
			a = mul(a, a);
			b >>= 1;
		}
		return c;
	}

	private static S mul(S A, S B) // 矩阵乘法，AB必须可相乘
	{
		S C = new S(A.i, B.j);//
		for (int i = 0; i < A.i; i++) {// 枚举矩阵A的行
			for (int j = 0; j < B.j; j++) {// 枚举矩阵B的列
				for (int k = 0; k < A.j; k++) {// k代表矩阵A的列的同时代表举着B的行
					C.sz[i][j] += (A.sz[i][k] * B.sz[k][j]) % mod;
					C.sz[i][j] %= mod;
				}
			}
		}
		return C;
	}
}