想必大家都会二进制快速幂， 普通的快速幂中， 将指数拆为二进制数，基数为 2 的次方。
十进制快速幂仅仅是将基数变为了10的次方，只要对普通快速幂的思想了解， 这个就很简单了
例如求 =
ll t_pow(ll a, ll b) { ll res = 1; while (b > 0) { ll now = a; for (int i = 1; i <= b % 10; i++) // 当前位数字为几， 即乘几次 res = (res * a) % mod; for (int i = 2; i <= 10; i++) // a = a ^ 10 a = a * now % mod; b /= 10; } return res; }显然每次我们都要有个乘9次的操作， 可以用快速幂的思想倍增求， 这样就可以优化到3次
ll t_pow(ll a, ll b) { ll res = 1; while (b > 0) { for (int i = 1; i <= b % 10; i++) res = (res * a) % mod; ll x = a * a % mod; // a ^ 2 ll y = x * x % mod; // a ^ 4 ll z = y * y % mod; // a ^ 8 a = z * x % mod; // a ^ 10 b /= 10; } return res % mod; }至于矩阵快速幂的话， 跟普通的矩阵快速幂差别也就仅仅在这里
例如牛客多校第五场 B: generator 1
https://ac.nowcoder.com/acm/contest/885/B
这题给出 满足
求第n项
显然直接用二进制快速幂求会超时。
对做一次矩阵乘法， 得到的即是与
所以乘n次后， 取m[1][0]即是答案
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6 + 10; ll A, B, x0, x1; ll m; char s[N]; struct M{ ll m[2][2]; M() { memset(m, 0, sizeof m); } }; M mul(M a, M b) { M ans; for (ll i = 0; i < 2; i++) for (ll j = 0; j < 2; j++) { for (ll k = 0; k < 2; k++) ans.m[i][j] = (ans.m[i][j] + a.m[i][k] * b.m[k][j] % m) % m; } return ans; } void fpow(ll n) { M a, b; a.m[0][0] = A; a.m[0][1] = B; a.m[1][0] = 1; b.m[0][0] = b.m[1][1] = 1; while (n >= 0) { ll cnt = s[n] - '0'; M now = a; for (int i = 1; i <= cnt; i++) b = mul(b, a); M c[2]; a = mul(a, a); // 2 c[0] = mul(a, a); // 4 c[1] = mul(c[0], c[0]); // 8 a = mul(a, c[1]); n--; } M ans; ans.m[0][0] = x1; ans.m[1][0] = x0; ans = mul(b, ans); cout << ans.m[1][0] << endl; } int main(){ cin >> x0 >> x1 >> A >> B; scanf("%s", s); cin >> m; ll len = strlen(s); fpow(len - 1); return 0; }
