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

题目：

题解：

class Solution {
public:static constexpr int MOD = 1'000'000'007;vector<vector<long>> pow(vector<vector<long>> mat, int n) {vector<vector<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;}vector<vector<long>> multiply(vector<vector<long>> a, vector<vector<long>> b) {int rows = a.size(), columns = b[0].size(), temp = b.size();vector<vector<long>> c(rows, vector<long>(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;}int checkRecord(int n) {vector<vector<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}};vector<vector<long>> res = pow(mat, n);long sum = accumulate(res[0].begin(), res[0].end(), 0ll);return (int)(sum % MOD);}
};