矩阵

1113 矩阵快速幂

链接??

3.0 秒 131,072.0 KB 20 分 3级题 给出一个N * N的矩阵，其中的元素均为正整数。求这个矩阵的M次方。由于M次方的计算结果太大，只需要输出每个元素Mod (10^9 + 7）的结果。

收起 输入 第1行：2个数N和M，中间用空格分隔。N为矩阵的大小，M为M次方。(2 <= N <= 100, 1 <= M <=
10^9) 第2 - N + 1行：每行N个数，对应N * N矩阵中的1行。(0 <= N[i] <= 10^9) 输出
共N行，每行N个数，对应M次方Mod (10^9 + 7)的结果。

输入样例
2 3
1 1
1 1
输出样例
4 4
4 4

代码

#include<iostream>
using namespace std;

#define ll long long 
const int mxn = 105;
const ll mod = 1e9 + 7;
ll n;
//快速乘法
ll quick_mul(ll a, ll b, ll c)
{
    ll res = 0;
    while(b)
    {
        if(b&1) res = (res + a) % c;
        a = (a + a) % c;
        b >>= 1;
    }
    return res;
}
//快速幂
ll quick_mod(ll a, ll b, ll c)
{
    ll ans = 1;
    while(b)
    {
        if(b&1) ans = ans * a % c; 
        a = a * a % c;
        b >>= 1;
    }
    return ans;
}
//优化快速幂
ll Quick_mod(ll a, ll b, ll c)
{
    ll ans = 1;
    while(b)
    {
        if(b&1) ans = quick_mul(ans, a, c);
        a = quick_mul(a, a, c);
        b >>= 1;
    }
    return ans;
}

//矩阵快速幂----------------------
//快速生成矩阵
struct Mat
{
    ll m[mxn][mxn];
} unit;
//重载 * 号
Mat operator * (Mat a, Mat b)
{
    Mat res;
    ll x;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
        {
            x = 0;
            for(int k = 0; k < n; k ++)
                x = (x + a.m[i][k] * b.m[k][j]) % mod;
            res.m[i][j] = x;
        }
    return res;
}

//初始化 产生 “幺元”（定义：类似于一个数乘以a，得到的值还是a，那么普通的乘法的的“幺元”就是1，把定义推倒矩阵：矩阵a乘以“幺元”矩阵 的得到矩阵，还是 a，这个”幺元矩阵“ 就是与普通乘法中的“幺元1” 类似功能）
void init_unit()
{
    for(int i = 0; i < mxn; i ++)
        unit.m[i][i] = 1;
}
//矩阵的快速幂的过程
Mat quick_mat(Mat a, ll n)
{
    Mat res = unit;
    while(n)
    {
        if(n&1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}
//---------------------

int main()
{
    /* freopen("A.txt","r",stdin); */
    init_unit();
    Mat a, aa;
    ll b;
    scanf("%lld %lld", &n, &b);
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            scanf("%lld", &a.m[i][j]);
    aa = quick_mat(a, b);
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < n; j ++)
            printf("%lld ", aa.m[i][j]);
        printf("\n");
    }

    return 0;
}

1113 矩阵快速幂（板子）

原文：https://www.cnblogs.com/lql-nyist/p/12635148.html