行列

目的

行列の基本的な演算をするための関数群。

使い方

long[][] add(long[][] a, long[][] b)
行列$a$と行列$b$の和$a+b$をreturn。計算量は$O(n^2)$。
long[][] mul(long[][] a, long[] b)
行列$a$と行列$b$の積$ab$をreturn。計算量は$O(n^3)$。
long[][] pow(long[][] a, long n)
行列$a$の$n$乗を繰り返し二乗法により計算しその計算結果をreturn。計算量は$O(n^3\log(n))$。

ソースコード

public class Main {
    
    long[][] add(long[][] a, long[][] b) {
	long[][] ret = new long[a.length][a[0].length];
	for (int i = 0; i < a.length; ++i) {
	    for (int j = 0; j < a[i].length; ++j) {
		ret[i][j] = a[i][j] + b[i][j];
	    }
	}
	return ret;
    }



    long[][] mul(long[][] a, long[][] b) {
	long[][] ret = new long[a.length][b[0].length];
	for (int i = 0; i < a.length; ++i) {
	    for (int j = 0; j < b[i].length; ++j) {
		for (int k = 0; k < a[i].length; ++k) {
		    ret[i][j] += a[i][k] * b[k][j];
		}
	    }
	}
	return ret;
    }

    long[][] pow(long[][] a, long n) {
	long[][] ret = new long[a.length][a.length];
	for (int i = 0; i < ret.length; ++i)
	    ret[i][i] = 1;
	for (; n > 0; n >>= 1, a = mul(a, a)) {
	    if (n % 2 == 1) {
		ret = mul(ret, a);
	    }
	}
	return ret;
    }
    
}