矩阵快速幂（运算符重载）

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

https://www.luogu.com.cn/problem/P3390

• 把*重载成矩阵的乘法
• 再用普通的快速幂就行
• （AC代码是copy的，实在debug不出了）

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#define ll long long
#define gc() getchar()
#define maxn 105
#define mo 1000000007
using namespace std;

inline ll read()
{
    ll a = 0;
    int f = 0;
    char p = gc();
    while (!isdigit(p))
    {
        f |= p == '-';
        p = gc();
    }
    while (isdigit(p))
    {
        a = (a << 3) + (a << 1) + (p ^ 48);
        p = gc();
    }
    return f ? -a : a;
}
int n;

struct ahaha
{
    ll a[maxn][maxn]; 
    ahaha()
    {
        memset(a, 0, sizeof a);
    }
    inline void build()
    { //建造单位矩阵
        for (int i = 1; i <= n; ++i)
            a[i][i] = 1;
    }
} a;
ahaha operator*(const ahaha &x, const ahaha &y)
{
    ahaha z;
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j] % mo) % mo;
    return z;
}

ll k;
inline void init()
{
    n = read();
    k = read();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            a.a[i][j] = read();
}

int main()
{
    init();
    ahaha ans;
    ans.build();
    do
    {
        if (k & 1)
            ans = ans * a;
        a = a * a;
        k >>= 1;
    } while (k);
    for (int i = 1; i <= n; putchar('\n'), ++i)
        for (int j = 1; j <= n; ++j)
            printf("%d ", ans.a[i][j]);
    return 0;
}

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