实现源码在线查看 如果对于类的设计已经非常清楚，只是进来想看看我的这个泛型模板源代码，那么直接点到下面这个链接进行查看： 源码链接什么是矩阵快速幂？关于快速幂，就是利用二进制进行求解某个数的幂的快速方法。 后面会对快速幂的原理进行简单讲解，如果还是不懂，请自行百度。 相信有很多小伙伴是初入大学的世界，可能还没学过线性代数（比如我），于是乎不知道矩阵是什么，我推荐一个网站去看看矩阵的乘法是怎么运算的，下面是网站链接：（话说how to这个网站还真是牛批，什么东西都有教程，而且质量还贼高！😂） 矩阵乘法的计算方式 那么如何用代码表示矩阵以及他的乘法呢？ 其实很简单，就是三层循环进行控制即可。 如：我这里是C++的重载运算符 Matrix 是我定义的一个类。Matrix& operator*(Matrix& b){ assert(b.date!=NULL && date!=NULL && m==b.n); ll tmp[n][b.m]; for(int i=0;i<n;i++){ for(int j=0;j<b.m;j++){ ll sum = 0; for(int k=0;k<m;k++){ sum = (sum + date[i][k]*b.date[k][j])%MOD; } tmp[i][j] = sum; } } this->m = b.m; for(int i=0;i<n;i++){ for (int j = 0; j < m; ++j) { date[i][j] = tmp[i][j]; } } return *this; } 怎么进行矩阵快速幂的运算？ 关于如何矩阵快速幂，我们先了解一下简单的快速幂。 说是快速幂就是通过位运算实现快速的同数累乘。 简述一下快速幂的原理： 原理就是，如果要求x的3次幂，那么可以转化为求 x*x 的 2 次幂，而求一个数的 2^n 幂是很简单的，比如进行一次 x *= x 便得到 x 的二次方。而再进行一次 x *= x 就得到了 4 次方，继续便可得到 8/16... 总之是 log2N 的时间。 代码如下：int QuickPow(int x,int n){ int c = n; int res = 1; while(c!=0){ if(c&1!=0){ res *= x; } c >>= 1; x *= x; } return res; } 那么矩阵的快速幂如何进行？ 把上述的 int 类型换成自己定义的矩阵就是矩阵的快速幂了。 我直接贴上C++实现的重载运算符后的类的快速幂写法： 这里的quickPow表示的是一个类的成员函数，所以可以直接用到这个矩阵里的数据进行运算。this表示指向这个对象的指针。init() 成员函数表示初始化为单位矩阵。 void quickPow(ll c){ if(c==1||c<0)return; if(c==0){ init(); return; } Matrix tmp(*this); init(); while (c){ if(c&1){ *this = *this * tmp; } c >>= 1; tmp = tmp*tmp; } } 为什么突然想写这个模板？ 主要是因为最近做了几道快速幂的题目，被坑的很惨，然后就突然想设计一个模板了，主要是 my_tiny_stl 这个仓库也好久没更新了😂题目 OJ网站我是如何被坑的首先拿到这道题，我便马上开始简单的O(n)递推法实现，然后提交，然后。。超时。。 定眼一看，数据量原来这么大！ 后面一想，肯定是矩阵快速幂了，先想出以下矩阵的递推式子： 进而题目便可得到求解。 然后我就利用 C++ 的类简单的封装了一个矩阵类，里面重载了乘法和 quickpow 方法，然后比较悠闲的准备提交，还没提交前就遇到C++的语法陷阱、、语法陷阱（建议非C++党绕道） 由于类用的都是堆内存，所以我写了析构函数，我遇到的问题出在重载乘法时我返回的是左值，而且我也没有对 '=' 进行重载，所以 ‘=’ 就是直接的成员变量拷贝，这导致一个结果就是两个对象的 date 指向同一片内存空间，而之前的那片内存空间泄露了，且最后这两个对象肯定都会调用析构函数，这又导致了析构函数调用了两次！如何解决这个问题？如果是 C++98 ，那么这个问题很大，基本上就是两种方法解决：逃避问题，乘法的左操作数必须是当前赋值对象，这样就避免了最后赋值语句将原本对象内的指针直接改变。解决问题，解决这类问题无论是 C++11 还是 C++98 最直接的方式就是重载 ‘=’ 号，重载 '=' 号的实现根据具体的情况进行，而具体实现赋值的重载，我们需要考虑两件事：第一，需尽可能的减少内存的申请和使用（具体而言就是判断两个对象的指针所指向的是否为同一片空间，即便…