Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- typedef vector<vector<ll>> matrix;
- matrix matrixProduct(matrix a, matrix b) {
- if (!a.size() || !b.size()) return {};
- if (a[0].size() != b.size()) return {};
- ll n = a.size();
- ll m = b[0].size();
- matrix res(n, vector<ll>(m, 0));
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- for (int k = 0; k < a[0].size(); k++) {
- res[i][j] += a[i][k] * b[k][j];
- res[i][j] %= mod;
- }
- }
- }
- return res;
- }
- matrix operator*(const matrix &a, matrix &b) {
- return matrixProduct(a, b);
- }
- matrix binpow(matrix a, ll k) {
- int n = a.size();
- int m = a[0].size();
- matrix res(n, vector<ll>(m));
- if (k == 0) {
- for (int i = 0; i < n; i++) {
- res[i][i] = 1;
- }
- return res;
- }
- res = a;
- k--;
- while (k) {
- if (k & 1) res = res * a;
- a = a * a;
- k >>= 1;
- }
- return res;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement