矩阵快速幂

本文主要是介绍矩阵快速幂，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

矩阵快速幂其实就是运算的时候将幂优化了，可以近似看为快速幂

快速幂

求\(x^{n}\)，当n为奇数时，n的二进制最后一位必定是1,可以将其与1来判断是否为奇数，与结果相乘
n为偶数时，\(x^{2}\) = x * x,然后与结果相乘，最后在除2即可，默认向下取整

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = a; i >= b; i--)
const int N = 110;
typedef long long ll;
const ll mod = 1e9 + 7;
struct Matrix
{
    ll m[N][N];
};
ll n, q;
/*inline int read()
{
    char c = getchar(); int x = 0, s = 1;
    while(c < '0' || c > '9'){if(c == '-') s = -1; c = getchar();}
    while(c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}
    return x * s;
}*/
inline Matrix mul(Matrix a, Matrix b)
{
    Matrix res;
    memset(res.m, 0, sizeof res.m);
    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] += a.m[i][k] * b.m[k][j] % mod;
                res.m[i][j] %= mod;
            }
        }
    }
    return res;
}
inline Matrix fast(Matrix a, long long p)
{
    Matrix res;
    for(int i = 1; i <= n; i++)
    res.m[i][i] = 1;//单位矩阵
    while(p)
    {
        if(p&1) res = mul(res, a);
        p >>= 1;
        a = mul(a, a);
    }
    return res;
}

int main()
{
    scanf("%lld %lld", &n, &q);
    Matrix c;
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
    scanf("%lld", &c.m[i][j]);
    Matrix d = fast(c, q);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(j != n)
            printf("%lld ", d.m[i][j]);
            else
            printf("%lld", d.m[i][j]);
        }
        printf("\n");
    }
    return 0;
}

这篇关于矩阵快速幂的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！