Matrix Square Exponentiation

我们需要先了解一下矩阵是一个什么东西。

矩阵

在数学中,矩阵(Matrix)是一个按照长方阵列排列的复数或实数集合。
我们来了解一下矩阵乘法:

如果矩阵A是m×n的,矩阵B是n×p,那么他们的乘积C是m×p的,它的元素:
快速幂

矩阵快速幂

这是一篇大水文,我们只需要把快速幂的乘法换成矩阵乘法就好了。

/**
* This function is used to initialize the matrix.
* Make the value of the positive diagonal 1, others 0.
**/
ll **matrixInit(int n) {
ll **ans = (ll**) malloc(sizeof(ll*) * n);
for (int i = 0; i < n; ++i)
ans[i] = (ll*) malloc(sizeof(ll) * n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
ans[i][j] = 0;
ans[i][i] = 1;
}
return ans;
}

ll **matrixMult(ll **x, ll **y, int n) {
ll **ans = (ll**) malloc(sizeof(ll*) * n);
for (int i = 0; i < n; ++i)
ans[i] = (ll*) malloc(sizeof(ll) * n);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
ans[i][j] = 0;
for(int i=0; i < n; ++i)
for(int k = 0; k < n; ++k)
for(int j = 0; j < n; ++j)
ans[i][j] = (ans[i][j] + x[i][k] * y[k][j] % MOD) % MOD;
return ans;
}

/**
* The method of calculating the nth power of matrix x.
* The row and column length of matrix X is required to be equal.
* The incoming parameter is x[ROW][ROW].
* The result is ans[ROW][ROW].
**/
ll **matrixPow(ll **x, ll n, int ROW) {
ll **ans = matrixInit(ROW);
for (; n; n >>= 1) {
if(n & 1)
ans = matrixMult(ans, x, ROW);
x = matrixMult(x, x, ROW);
}
return ans;
}
© 版权声明
THE END
喜欢就支持以下吧
点赞0
分享
评论 抢沙发

请登录后发表评论