周娟老师讲授的快速幂：整数快速幂、矩阵快速幂。
链接：https://www.bilibili.com/video/BV1nS4y1F7BU/
吴永辉解题策略-第一章利用快速幂（亚洲训练联盟2022冬令营）
https://vjudge.csgrandeur.cn/contest/480285#overview
数值快速幂
快速幂原理
思路1：分奇偶
typedef long long ll; ll fastPower(ll base, ll power) { ll result = 1; while (power > 0) { //指数为奇数 if (power % 2 == 1) { power -= 1; result * = base; } else { power /= 2; base * = base; } } return result; }
代码优化
ll fastPower(ll base, ll power) { ll result = 1; while (power) { if (power & 1) result *= base; power >>= 1; // 等价于除2 base *= base; } return result; }
思路2：二进制拆分
反复平方法（23：45s）
#define ll long long int qpow(ll a, ll b, ll p) { int res = 1; while (b) { if (b & 1) res = res * a % p; b >> 1; a = a * a % p; } return res; }
方阵相乘
int a[N][N], b[N][N], c[N][N] int main() { int n; while (~scanf("%d", &n)) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &a[i][j]); c[i][j] = 0; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &b[i][j]); } } for (int i = 0; i < n; i++) { for (int j = 0; i < n; j++) { for (int k = 0; k < n; k++) { c[i][j] = c[i][j] + a[i][k] * b[k][j]; } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j == n - 1) printf("%d\n", c[i][j]); else printf("%d", c[i][j]); } } } return 0; }
方阵乘法
#define LL long long const LL MOD = 1e9 + 7; int n; struct Matrix { LL a[N][N]; Matrix { memset(a, 0, sizeof(a)); } void init() { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) a[i][j] = (i == j); } Matrix *(const Matrix &B) const { Matrix C; for (int i = 0; i < n; i++) for (int k = 0; k < n; k++) for (int j = 0; j < n; j++) C.a[i][j] = (C.a[i][j] + 1LL * a[i][k] * B.a[k][j]) % MOD; } return C: }
矩阵快速幂
Matrix operator ^(const LL &t) const//矩阵快速幂 { Matrix A = (*this),res; res.init(); LL p = t; while (p) { if (p & 1) res = res * A; A = A * A: p >> 1; } return res; } .a[i] int main() { Matriz = base; LL m; scanf("%d%lld", &n ,&m); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) printf("%lld%c",base.a[i][j]); base = base^m; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) printf("%lld%c",base.a[i][j], (j == n - 1 ?'\n') : ' '); }
