Created
January 23, 2026 08:24
-
-
Save Mjkim-Programming/847b14d506cf3b1720a0b792dc61bcab to your computer and use it in GitHub Desktop.
Matrix Power
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| using ll = long long; | |
| using i128 = __int128; | |
| using element = ll; | |
| using matrix = vector<vector<element>>; | |
| matrix modmatmul(const matrix& a, const matrix& b, ll m) { | |
| int n = a.size(); | |
| int k = a[0].size(); | |
| int p = b[0].size(); | |
| matrix c(n, vector<element>(p, 0)); | |
| for(int i = 0; i < n; i++) { | |
| for(int t = 0; t < k; t++) { | |
| for(int j = 0; j < p; j++) { | |
| c[i][j] = (c[i][j] + (i128)a[i][t]*b[t][j]) % m; | |
| } | |
| } | |
| } | |
| return c; | |
| } | |
| matrix modmatpow(const matrix& a, ll n, ll m) { | |
| if(n == 1) { | |
| return a; | |
| } | |
| matrix temp = modmatpow(a, n/2, m); | |
| if(n % 2 == 0) { | |
| return modmatmul(temp, temp, m); | |
| } else { | |
| return modmatmul(modmatmul(temp, temp, m), a, m); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment