矩阵快速幂的问题

ゝ一纸荒年。 2022-05-14 01:10 136阅读 0赞

# 前言 #

这个问题，本科ACM时期做过专门的总结，但是，由于后来也没有使用过相关的知识，就忘得差不多了最近回顾了一下

# 之前的博客链接 #

[快速幂取模算法][Link 1]  
[快速幂算法模板][Link 2]  
[矩阵乘法快速幂模板][Link 3]  
[相关的地址][Link 4]

# 矩阵快速幂的写法 #

while(N)
        {
            if(N&1)
                res=res*A;
            n>>=1;
            A=A*A;
        }
    
        //改进版（取模）a^b mod n ：
        int modexp(int a, int b, int n)
        {
            int t = a, ret = 1;
            while(b != 0)
            {
                if(b % 2 == 1) ret *= t % n;
                t = t * t % n;
                b /= 2;
            } 
            return ret;
        }
    
        long long modexp(long long a, long long b, int mod)
        {
            long long res=1;
            while(b>0)
            {
                //a=a%mod;(有时候n的值太大了会超出long long的储存，所以要先取余)
                if(b&1)//&位运算：判断二进制最后一位是0还是1，&的运算规则为前后都是1的时候才是1；
                    res=res*a%mod;
                b=b>>1;//相当于除以2；
                a=a*a%mod;
            }
            return res;
        }

[Link 1]: https://blog.csdn.net/u014265347/article/details/43226733
[Link 2]: https://blog.csdn.net/u014265347/article/details/43646997
[Link 3]: https://blog.csdn.net/u014265347/article/details/43647151
[Link 4]: https://so.csdn.net/so/search/s.do?q=%E5%BF%AB%E9%80%9F%E5%B9%82&t=blog&u=u014265347

发表评论取消回复

表情：

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

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

相关阅读

相关矩阵的快速幂

> 通常用在递归表达式中，将递归表达式（动态规划问题的通式）转化为矩阵 > 参考：[https://zhuanlan.zhihu.com/p/95902286][https

清疚/ 2022年10月22日 09:25/ 0 赞/ 18 阅读

相关矩阵快速幂

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

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

相关矩阵快速幂

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

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

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

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

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

相关矩阵快速幂

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

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

相关快速幂和矩阵快速幂

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

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

相关矩阵快速幂的问题

前言这个问题，本科ACM时期做过专门的总结，但是，由于后来也没有使用过相关的知识，就忘得差不多了最近回顾了一下之前的博客链接 [快速幂取模算法][Link 1

ゝ一纸荒年。/ 2022年05月14日 01:10/ 0 赞/ 137 阅读

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

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

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

相关矩阵快速幂

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

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

相关矩阵快速幂

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

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