- 浏览: 118388 次
- 性别:
- 来自: 北京
最新评论
typedef LL matrix[55][55]; void ident(int size, matrix x) { for (int i = 0; i < size; ++i) for (int j = 0; j < size; ++j) x[i][j] = (i == j ? 1 : 0); } void copy(int size, matrix x, matrix y) { for (int i = 0; i < size; ++i) for (int j = 0; j < size; ++j) y[i][j] = x[i][j]; } void mutiply(int size, matrix _x, matrix _y, matrix z) { matrix x, y; copy(size, _x, x); copy(size, _y, y); for (int i = 0; i < size; ++i) for (int j = 0; j < size; ++j) { z[i][j] = 0; for (int k = 0; k < size; ++k) z[i][j] = (z[i][j] + (int64)x[i][k] * y[k][j]) % M; } } void power(int size, matrix _x, LL n, matrix y) { matrix x, r; copy(size, _x, x); ident(size, r); while (n) { if (n & 1) mutiply(size, r, x, r); n >>= 1; if (n == 0) break; mutiply(size, x, x, x); } copy(size, r, y); }
发表评论
-
lower_bound and upper_bound
2012-02-09 00:36 1151/** * @brief Finds the ... -
HDU 3954
2012-02-05 10:43 839线段树变种,也是在2logn段上面做文章 /* * ... -
HDU 4027
2012-02-04 22:09 849线段树变种 在2logn段上面做文章,swap(x, y)太阴 ... -
ICPC编码建议
2011-10-28 09:52 887写代码最重要的是清晰,包括思路的清晰和代码结构的清晰。我们无法 ... -
[转载]TopCoder插件
2011-09-08 22:13 970转载自:http://acm.cugb.edu.cn/blog ... -
UVALive 5112 - Sales Prediction
2011-01-06 10:19 1188封装了矩阵类 比赛做得很郁闷,为什么别人写得很长、很罗嗦的代码 ... -
hdu 3236
2010-12-12 14:10 797终于能过这道题了,算是背包必做题之一吧 /* * Au ... -
pku 1018
2010-12-11 15:18 602写了两三个版本,最后这个效率最高 #include < ... -
布斯(Booth)乘法
2010-10-07 19:59 1137源自http://watashi.ws/blog/1515/z ... -
高斯消元
2010-10-07 14:18 803import java.util.*; import j ... -
整数划分
2010-10-07 10:38 839#include <cstdio> #inc ... -
Treap
2010-09-18 22:19 979// Treap // Tested: bjtu1057 ... -
maximum clique 最大团
2010-09-02 18:12 1134最大团模板 #include <cstdio> ... -
计算Jacobi符号
2010-08-31 13:15 1291Quadratic reciprocity The Jacob ... -
Java 高效I/O
2010-08-19 16:54 774static BufferedReader cin = ... -
DLX pku 3076
2010-08-11 23:45 877标准数独,精确覆盖 // pku3076.cpp #in ... -
DLX hust 1017
2010-08-11 16:50 848“精确覆盖”问题 #include <cstdio& ... -
DLX hdu 3498
2010-08-11 16:48 1039“多重覆盖”或“重复覆盖”问题 #include < ... -
hdu 3509
2010-08-09 11:22 1004推导公式的题目,矩阵幂关键就在于构造系数矩阵 备忘: S(n, ... -
RMQ模板
2010-07-28 11:04 1185/* * Author: rush * Creat ...
相关推荐
yxy版c++教程 浅谈矩阵快速幂
矩阵快速幂的模板,需要自己根据实际题目更改矩阵大小和数据类型,以免WA和TLE。经过矩阵乘法上的稀疏矩阵优化和int64的乘法取模幂优化,效率应该比较高。视情况使用mult()函数或直接使用乘法。代码中每个函数有注释...
斐波那契矩阵快速幂模版
c++ 矩阵快速幂封装支持矩阵乘法取模等
快速幂和矩阵快速幂1
一文彻底搞懂快速幂(原理实现、矩阵快速幂) 结合实际,详细讲解,非常实用,值得收藏
矩阵快速幂 幂又称乘方。表示一个数字乘若干次的形式,如n个a相乘的幂为a^n ,或称a^n为a的n次幂。a称为幂的底数,n称为幂的指数。 快速幂的思路就是:设A为矩阵,求A的N次方,N很大。例如:A的9次方 A^9 = A*A*A...
矩阵快速幂套路模板.cpp
线性代数- 矩阵快速幂.rar
2. 从侧边栏的类别目录找到「矩阵快速幂」 3. 按照「推荐指数」从大到小进行刷题,「推荐指数」相同,则按照「难度」从易到 4. 拿到题号之后,回到本合集进行检
快速幂
技术文档分享,免费获取请私信博主。
喝了负负负负负负负 喝了负负负负负负负 喝了负负负负负负负 喝了负负负负负负负 喝了负负负负负负负
矩阵乘法必用算法快速幂基础程序pascal
在讲解快速幂之前,让我们先来思考一个问题:7的10次方,怎样算比较快?...这次的讲解就到这里了,希望大家对快速幂能有所了解,快速幂还包涵矩阵快速幂,快速幂的代码是需要背的,如果要熟练的话就只能多背!
Codeforces 185A - Plant 全测试点49个
利用了矩阵结合律,先算出构造递推矩阵自乘的结果,再与初始矩阵相乘。 #include using namespace std; typedef long long ll; #define ls (o<<1) #define rs (o<<1|1) #define pb push_back //#define...
经典算法 高效计算快速幂 使用矩阵方式进行计算
Java矩阵类,用于ACM矩阵快速幂运算的模板,可以用log(N)【以二为底】的时间复杂度求出递推式子的第N项