矩阵模板

class Matrix {
	int[][] element;
	int r, c;
	public static Matrix getUnitMatrix(int r) {
		Matrix ret = new Matrix(r, r);
		for (int i = 0; i < r; ++i) {
			for (int j = 0; j < r; ++j) {
				ret.element[i][j] = (i == j ? 1 : 0);
			}
		}
		return ret;
	}
	public Matrix(int r, int c) {
		this.r = r;
		this.c = c;
		this.element = new int[this.r][this.c];
	};
	public Matrix(int[][] tmp, int r, int c) {
		this.r = r;
		this.c = c;
		this.element = new int[this.r][this.c];
		for (int i = 0; i < this.r; ++i) {
			for (int j = 0; j < this.c; ++j) {
				this.element[i][j] = tmp[i][j];
			}
		}
	}
	public Matrix multiply(Matrix m) {
		Matrix ret = new Matrix(this.r, m.c);
		for (int i = 0; i < this.r; ++i) {
			for (int j = 0; j < m.c; ++j) {
				int sum = 0;
				for (int k = 0; k < this.c; ++k)
					sum += this.element[i][k] * m.element[k][j];
				ret.element[i][j] = sum;
			}
		}
		return ret;
	}
	public Matrix multiply(Matrix m, int mod) {
		Matrix ret = new Matrix(this.r, m.c);
		for (int i = 0; i < this.r; ++i) {
			for (int j = 0; j < m.c; ++j) {
				int sum = 0;
				for (int k = 0; k < this.c; ++k)
					sum += this.element[i][k] * m.element[k][j] % mod;
				ret.element[i][j] = sum % mod;
			}
		}
		return ret;
	}
	public Matrix pow(int n, int mod) {
		Matrix ret = Matrix.getUnitMatrix(this.c);
		for(; n!=0; n>>=1) {
			if((n&1) ==1)
				ret = this.multiply(ret, mod);
			this.element = this.multiply(this,mod).element;
		}
		return ret;
	}
	public int Tr(int mod) {
		int ret =0;
		for(int i=0; i<this.r; ++i) {
			for(int j=0; j<this.c; ++j) {
				if(i==j) {
					ret += this.element[i][j];
					if(ret>=mod)
						ret = ret%mod;
				}
			}
		}
		return ret;
	}
	@Override
	public String toString() {
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < this.r; ++i) {
			sb.append(Arrays.toString(this.element[i]) + "/n");
		}
		return sb.toString();
	}
}