Java | Leetcode Java题解之第552题学生出勤记录II

题目：

题解：

class Solution {static final int MOD = 1000000007;public int checkRecord(int n) {long[][] mat = {{1, 1, 0, 1, 0, 0},{1, 0, 1, 1, 0, 0},{1, 0, 0, 1, 0, 0},{0, 0, 0, 1, 1, 0},{0, 0, 0, 1, 0, 1},{0, 0, 0, 1, 0, 0}};long[][] res = pow(mat, n);long sum = Arrays.stream(res[0]).sum();return (int) (sum % MOD);}public long[][] pow(long[][] mat, int n) {long[][] ret = {{1, 0, 0, 0, 0, 0}};while (n > 0) {if ((n & 1) == 1) {ret = multiply(ret, mat);}n >>= 1;mat = multiply(mat, mat);}return ret;}public long[][] multiply(long[][] a, long[][] b) {int rows = a.length, columns = b[0].length, temp = b.length;long[][] c = new long[rows][columns];for (int i = 0; i < rows; i++) {for (int j = 0; j < columns; j++) {for (int k = 0; k < temp; k++) {c[i][j] += a[i][k] * b[k][j];c[i][j] %= MOD;}}}return c;}
}