【矩阵快速幂】

悠悠 2022-06-08 01:43 223阅读 0赞

1.21矩阵快速幂模板

typedef long long LL;
    
    const int mod =  ;
    
    struct Matrix{
        LL v[4][4];
    };
    
    Matrix multiply(Matrix x, Matrix y, int Matrix_len);/*矩阵乘法*/
    Matrix matrix_pow(Matrix a, int k, int Matrix_len);/*矩阵快速幂*/
    
    Matrix multiply(Matrix x, Matrix y, int Matrix_len){
        Matrix z;
        memset(z.v, 0, sizeof(z.v));
        for(int i = 0; i < Matrix_len; i++){
            for(int j = 0; j < Matrix_len; j++){
                for(int k = 0; k < Matrix_len; k++){
                    z.v[i][j] += x.v[i][k] * y.v[k][j];
                    z.v[i][j] %= mod;
                }
            }
        }
        return z;
    }
    Matrix matrix_pow(Matrix a, int k, int Matrix_len){
        Matrix b;
        for(int i = 0; i < Matrix_len; i++){
            for(int j = 0; j < Matrix_len; j++){
                i == j? b.v[i][j] = 1: b.v[i][j] = 0;
            }
        }
        while(k){
            if(k & 1)
                b = multiply(b, a, 2);
            a = multiply(a, a, 2);
            k >>= 1;
        }
        return b;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关矩阵快速幂

昨天晚上矩阵小王子给我们讲了一下矩阵快速幂，学习了一下，写了一个模板。 1：思想矩阵快速幂的思想就是跟数的快速幂一样，假如我们要求2^11，次方，我们可以把 11 写成

Love The Way You Lie/ 2022年08月12日 18:30/ 0 赞/ 217 阅读

相关矩阵快速幂

include<cstdio> include<iostream> include<cmath> include<vector> inc

朴灿烈づ我的快乐病毒、/ 2022年06月18日 12:29/ 0 赞/ 252 阅读

相关矩阵快速幂

/ 假设 A 是 mp 的矩阵 , B 是 pn 的矩阵记 C = AB (C 是矩阵 A与B的乘积) 那么 C 是 mn 的矩阵

Dear 丶/ 2022年06月17日 04:24/ 0 赞/ 218 阅读

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

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

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

相关矩阵快速幂

A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。 Input 数据的第一行是一个T，表示有T组数据。每组数据的

谁践踏了优雅/ 2022年06月09日 02:09/ 0 赞/ 229 阅读

相关【矩阵快速幂】

1.21矩阵快速幂模板 typedef long long LL; const int mod = ; struct Matri

悠悠/ 2022年06月08日 01:43/ 0 赞/ 224 阅读

相关快速幂和矩阵快速幂

前言新年第一篇技术类的文章，应该算是算法方面的文章的。看标题：快速幂和矩阵快速幂，好像挺高大上。其实并不是很难，快速幂就是快速求一个数的幂（一个数的 n 次方）。

╰+攻爆jí腚メ/ 2022年06月01日 08:10/ 0 赞/ 288 阅读

相关矩阵快速幂+整数快速幂

嗯~ 今天总结一下快速幂的知识点 1.首先讲一下矩阵相乘矩阵A与矩阵B相乘的前提条件：A矩阵的列必须和矩阵B的行相等。若A矩阵是m\p的矩阵，那么B矩阵必定是p\n的

缺乏、安全感/ 2022年05月11日 13:22/ 0 赞/ 324 阅读

相关矩阵快速幂

矩阵快速幂源代码参考博客源代码 include <bits/stdc++.h> using namespace std;

港控/mmm°/ 2021年11月13日 21:18/ 0 赞/ 416 阅读

相关矩阵快速幂

通常我们使用的快速幂是以二为底的，这次就遇到了一道以10为底的快速幂题目；先说下快速幂 long long power(long long a,long long

桃扇骨/ 2021年11月10日 14:31/ 0 赞/ 353 阅读