快速幂
乘法快速幂
int fpow(int a, int n) { int res = 1; for(; n; n>>=1, a*=a) if(n&1) res*=a; return res; }
矩阵快速幂
struct matrix { int m[10][10], n; matrix(int n, int k = 0): n(n){ for(int i = 1; i <= n; ++ i) { for(int j = 1; j <= n; ++ j) { if (i == j) m[i][j] = k; else m[i][j] = 0; } } } matrix operator* (matrix m2) { matrix res(n); for(int i = 1; i <= n; ++ i) { for(int j = 1; j <= n; ++ j) { for(int k = 1; k <= n; ++ k) { res.m[i][j] += m[i][k] * m2.m[k][j]; } } } return res; } }; matrix fastpow(matrix a, int n) { // 矩阵快速幂 matrix res(3,1); while(n) { if (n&1) res = res * a; n >>= 1; a = a * a; } return res; }
数学 文章被收录于专栏
关于acm竞赛数论的个人笔记