[SoFan] 矩阵快速幂模版

科技前沿 • 2025-01-17 08:11 • 阅读 55

[SoFan] 矩阵快速幂模版规定矩阵都从下标 1 开始 define maxn 1000 创建的矩阵大小 maxn maxn const int mod 1e9 7 模数 int mlen 矩阵大小一般为方阵 long long k k 次幂 struct mat 用结构体存矩阵方便二维数组传址 long

大家好，我是讯享网，很高兴认识大家。

// 规定矩阵都从下标1开始 #define maxn 1000 // 创建的矩阵大小maxn*maxn const int mod = 1e9 + 7;// 模数 int mlen;// 矩阵大小（一般为方阵） long long k;// k次幂 struct mat{// 用结构体存矩阵，方便二维数组传址 long long s[maxn][maxn]; mat(){ memset(s, 0, sizeof(s)); }// 初始化为0 inline void unit(int mlen) {// 初始化为单位矩阵（对角线为1） for (int i = 1; i <= mlen; i++){ s[i][i] = 1; } } }; mat matmul(mat a, mat b) {// 矩阵乘法 mat c; for (int i = 1; i <= mlen; i++){ for (int j = 1; j <= mlen; j++){ for (int k = 1; k <= mlen; k++){ c.s[i][j] = (c.s[i][j] + a.s[i][k] * b.s[k][j]) % mod; } } } return c; } mat matpow(mat a, long long k){// 快速幂 mat temp; temp.unit(mlen); while (k){ if (k&1){ temp = matmul(temp, a); } a = matmul(a, a); k >>= 1; } return temp; }

讯享网