矩阵快速幂基础模板

绝地灬酷狼 2022-06-16 00:54 264阅读 0赞

Think:  
1注意记录数组初始化  
2思想->大数取模

#include <bits/stdc++.h>
    
    using namespace std;
    
    struct node
    {
        int v[14][14];
    };
    
    int n;
    
    struct node multiply(struct node x, struct node y)///矩阵相乘
    {
        struct node z;
        memset(z.v, 0, sizeof(z.v));
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                for(int k = 0; k < n; k++)
                {
                    z.v[i][j] += x.v[i][k] * y.v[k][j];
                }
            }
        }
        return z;
    }
    
    struct node Ans(struct node a, int k)///矩阵快速幂
    {
        struct node b;
        for(int i = 0; i < n; i++)///记录数组初始化
        {
            for(int j = 0; j < n; j++)
            {
                if(i == j)
                    b.v[i][j] = 1;
                else
                    b.v[i][j] = 0;
            }
        }
        while(k)
        {
            if(k & 1)
                b = multiply(b, a);
            a = multiply(a, a);
            k >>= 1;
        }
        return b;
    }
    
    int main()
    {
        int i, j, k;
        struct node c;
        while(scanf("%d %d", &n, &k) != EOF)
        {
            for(i = 0; i < n; i++)
            {
                for(j = 0; j < n; j++)
                {
                    scanf("%d", &c.v[i][j]);
                }
            }
            c = Ans(c, k);
            for(i = 0; i < n; i++)
            {
                for(j = 0; j < n; j++)
                {
                    printf("%d%c", c.v[i][j], j == n-1? '\n': ' ');
                }
            }
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，264人围观）

还没有评论，来说两句吧...

相关阅读

相关数论5——矩阵快速幂（模板）

include<bits/stdc++.h> define ll long long using namespace std; c...

布满荆棘的人生/ 2024年04月17日 20:11/ 0 赞/ 109 阅读

相关矩阵快速幂模板+例题（快速入门）

矩阵快速幂模板+例题（快速入门）本来早在一个月前就应该把这给掌握的，硬是得等到卡题了，才想到来补知识文章目录矩阵快速幂模板+例题（快速入门）

￡神魔★判官ぃ/ 2023年07月18日 02:38/ 0 赞/ 53 阅读

相关矩阵快速幂的模板（C++）

顾名思义，快速幂就是快速计算某个数的n次幂。其时间复杂度为 O(log₂N)，与朴素的O(N)相比效率有了极大的提高。前面学习了整数的快速幂：比如我们要求12^

迷南。/ 2023年03月06日 03:50/ 0 赞/ 50 阅读

相关矩阵快速幂（快速幂）模板题目Decoding Genome

这类题目的难点在于，数据量大，需要用到高精度，也就是快速幂矩阵的乘法与快速幂模板一： const int mod = 1e9+7; struct Matr

今天药忘吃喽~/ 2022年10月14日 13:51/ 0 赞/ 202 阅读

相关矩阵快速幂模板

int mod; const int NUM;//定义矩阵能表示的最大维数 int N;//N表示矩阵的维数，以下的矩阵加法、乘法、快速幂都是按N维矩阵

曾经终败给现在/ 2022年07月03日 15:26/ 0 赞/ 235 阅读

相关矩阵快速幂基础模板

Think: 1注意记录数组初始化 2思想->大数取模 include <bits/stdc++.h> using namespace st

绝地灬酷狼/ 2022年06月16日 00:54/ 0 赞/ 265 阅读

相关矩阵运算，矩阵快速幂，模板

include<cstdio> include<algorithm> include<cstring> include<iostream>

以你之姓@/ 2022年06月11日 05:41/ 0 赞/ 261 阅读

相关快速幂，矩阵快速幂（模板）

1，整数快速幂： C++ Code <table style="width:100%;font-family:Consolas, 'Courier New';font-

左手的ㄟ右手/ 2022年06月11日 03:57/ 0 赞/ 338 阅读

相关 poj-3982(矩阵快速幂+大数模板)

问题描述: 数列A满足An = An-1 + An-2 + An-3, n >= 3 ,编写程序，给定A0, A1 和 A2, 计算A99 Input 输入包

待我称王封你为后i/ 2022年06月09日 04:25/ 0 赞/ 330 阅读

相关矩阵快速幂模板

const int maxn = 2; struct Matrix{ ll a[maxn][maxn]; void

小鱼儿/ 2021年09月19日 05:44/ 0 赞/ 428 阅读