矩阵快速幂,模板

矩阵快速幂,模板 篇一:ACM算法竞赛模板个人总结 数 学 ................................................................................................................................................ 4 最大公约数、最小公倍 数 ....................................................................................................... 4 最大公约数——欧几里得算法 O(n) ...................................................................................... 4 Stein算法 O( log(max(a,b)) ) ........................................................................................... 4 最小公倍 数: ........................................................................................................................... 4 素数相 关 ................................................................................................................................... 5 1 普通素数判 断 ................................................................................................................... 5 筛法求素数[1， N] ........................................................................................................... 5 二次筛法求素数[L， R] ................................................................................................... 6 Miller-Rabbin素数测试方 法 ........................................................................................ 7 算术基本定理的定义和性 质: ............................................................................................... 8 同余方程[组] 乘法模逆元 中国剩余定 理 ........................................................................... 9 扩展欧几里得，求一组解x，y，使得gcd(a,b) = d = a * x + b * y ................. 9 扩展欧几里得，求所有解x，y，使得c = a * x + b * y ..................................... 10 扩展欧几里得，求a关于n的逆元a1，使得a * a1 ? 1(mod n) ............... 10 2 扩展欧几里得，求解x，满足同余方程组x ? Ri(mod Ai) ................................... 10 扩展欧几里得，求解x，满足高次同余方程A ? B(mod C) ............................... 11 中国剩余定 理: ..................................................................................................................... 13 中国剩余定理最小非负数解的算 法: ................................................................................. 14 求解a*x + b*y = c的其中一组解，使得|x| + |y|尽可能小， 若相等，则a|x| + b|y|尽可能 小。 ............................................................................................................. 15 整数快速 幂 ............................................................................................................................. 16 矩阵快速 幂 ............................................................................................................................. 16 整数分 解 ................................................................................................. 3 ................................ 18 试除法整数分 解 ............................................................................................................. 18 筛法整数分 解 ................................................................................................................. 18 PollardRho大整数分 解 ................................................................................................ 19 欧拉函 数 ................................................................................................................................. 22 直接欧拉函 数 ................................................................................................................. 22 递推快速求欧拉函 数 ..................................................................................................... 23 容斥原 理 ................................................................................................................................. 23 4 母函 数..................................................................................................................................... 24 普通母函 数 ..................................................................................................................... 24 指数型母函 数 ................................................................................................................. 25 其他相 关 ................................................................................................................................. 27 九余数定理:一个数N各位数字的和，对9取余等于这 个数对9取余 ................. 27 给你一个奇数N，求1~N的奇数平方和: S = N*(N+1)*(N+2)/6 .......................... 27 约瑟夫问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 :有N个人， 编号为1~N，按顺时针围成一个圈，每数k个人，就将这 个人从圈中消除，问:最终只留下一个人的编 号。 ................................................. 27 给你整数x和y的和 以及x和y的积，是否能找到满足这两个式子的整数x和整 数 5 y。 ................................................................................................................................... 29 Fibonacci数列大于40前四位数 字 ............................................................................ 29 小于N的素数个数为π(N),π(N)的位数是多 少, ................................................... 29 Stirling公式:当N足够大时，N! = (N/e) * N * sqrt(2*pi*N)。 .................. 29 有N张卡，将N张卡分成若干不同的集合，集合不能为空。 问:总共有多少种分法。 ......................................................................................................................................... 29 字符 串 ............................................................................................................................................ 29 KMP........................................................................................................................................... 29 1. 既能做前缀又能做后缀的子串长 度 ....................................................................... 30 2.求最短子串长 度 ................................................................................................. 6 ........ 30 3.求模式串pat在主串str中匹配次 数 ..................................................................... 30 4.求N行M列的字符矩阵，最小的字符子矩阵的面 积 ............................................. 30 5.求字符串s的循环前缀的长度和循环的次 数 ......................................................... 30 字典 树..................................................................................................................................... 31 数据结 构......................................................................................................................................... 33 并查 集..................................................................................................................................... 33 树状数 组 ................................................................................................................................. 33 单点更新，区间求值:树状数组代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 区间的 和。 ..................................................... 33 区间更新，单点求值:树状数组代表单个元素的变 7 化 ............................................. 34 求逆序数: 数组Tree[i] 表示数字i是否(转 载 于:wWW.xlTkWJ.Com 小 龙文 档 网:矩阵快速幂,模板)在序列中出现过，如果数字i已经存在 于序列中，Tree[i] = 1，否则Tree[i] = 0。按序列从左到右将 值为a的元素当作下标为a，赋值为1插入树状数组里，这 时，比a的数个数就是i - Query(a)。 将全部结果累加起来就是逆序数 了。 ......................................................................... 35 二维树状数 组: ............................................................................................................. 36 线段 树..................................................................................................................................... 36 单点更 新 ......................................................................................................................... 37 成段更 新 ......................................................................................................................... 43 区间合 并 ................................................................................................. 8 ........................ 52 扫描 线 ............................................................................................................................. 54 图 论 .............................................................................................................................................. 58 图的五种种存储方 式 ............................................................................................................. 58 方式1:邻接矩 阵 .......................................................................................................... 58 方式2:前向 星 .............................................................................................................. 58 方式3:邻接表——动态建 表 ...................................................................................... 59 方式4:邻接表——vector模拟链表实 现 ................................................................. 60 方式5:邻接表——链式前向星 ? .............................................................................. 61 9 拓扑排 序 ................................................................................................................................. 62 最小生成 树 ............................................................................................................................. 63 Kruskal算 法: .............................................................................................................. 63 Prim算 法: .................................................................................................................... 64 次小生成 树 ............................................................................................................................. 66 最小树形 图 ............................................................................................................................. 68 最近公共祖先LCA—Tarjan-LCA算 法: ............................................................................. 72 树的最小支配集、最小点覆盖、最大独立 集 ..................................................................... 74 10 最小支配集:指从所有顶点中取尽量少的点组成一个集 合，使得剩下的所有点都与取出来的点有边相连。顶点个数 最小的支配集被称为最小支配集。这里用贪心法来 求。 ................................................................................................................................. 74 最小点覆盖:指从所有顶点中取尽 量少的点组成一个集合，使得集合中所有的边都 与取出来的点有边相连。顶点个数最小的覆盖集被称为最 小点覆盖。 ................. 76 最大独立集:指从所有顶点中取 尽量多的点组成一个集合，使得这些点之间没有边 相连。顶点个数最多的独立集被称为最大独立 集。 ................................................. 77 单源最短路径Dijkstra、BellmanFord、 SPFA .................................................................. 77 Dijkstra算 法: ............................................................................................................ 77 BellmanFord算 法: ...................................................................................................... 79 SPFA算 法: ............................................................................................. 11 ....................... 81 多源最短路径Floyd、Floyd求最小 环 ............................................................................... 84 Floyd算法:用来找出每对点之间的最短距离。图可以是 无向图，也可以是有向图， 边权可为正，也可以为负，唯一要求是不能有负 环。 ............................................. 84 Floyd求最小 环 .............................................................................................................. 85 K短路—A*+SPFA算 法: ....................................................................................................... 86 差分约束系 统 ......................................................................................................................... 89 强连通分量Kosaraju、 Tarjan ............................................................................................ 92 Kosaraju算 法: ............................................................................................................ 92 12 Tarjan算 法: ................................................................................................................ 94 2-SAT....................................................................................................................................... 97 二分 图................................................................................................................................... 100 二分图最大匹配——匈牙利算法DFS 版: ............................................................... 100 二分图多重 匹 配: ....................................................................................................... 101 二分图最佳匹配——KM算 法: .................................................................................. 102 网 络流最大流EdmondKarp、 SAP ........................................................................................ 104 EdmondKarp算 法: ...................................................................................................... 104 SAP算 法: .................................................................................................................... 106 输入输出外挂—仅适合纯数字输 入 ................................................................................... 109 13 数 学 最大公约数、最小公倍数 最大公约数、最小公倍数性质: 1.若a | m，b | m，则lcm(a，b) | m。 2.若d | a，d | b，则d | gcd(a，b)。 3.lcm(a，b) = a * b / gcd(a，b)。 4.设m，a，b是正整数，则lcm(m*a，m*b) = m * gcd(a，b) 5.若m是非零整数a1，a2，…，an的公倍数，则lcm(a1，a2，…，an) | m用素因子分解法求a和b的最大公约数和最小公倍数: a = p1 1 * p2 2 * … * pk k b = p1 1 * p2*s2 * … * pk k gcd(a，b) = p1 14 in(r1,s1) * p2 15 in(r2,s2) * … * pk 16 in(rk,sk) lcm(a，b) = p1 17 ax(r1,s1) * p2 18 ax(r2,s2) * … * pk 19 ax(rk,sk) 最大公约数——欧几里得算法O(n) int GCD(int a,int b) { if(a < b) int temp = a, a = b, b = temp; if(b == 0) return a; return GCD(b,a%b); } Stein算法O( log(max(a,b)) ) int KGCD(int a,int b) { if(a == 0) return b; if(b == 0) return a; if(~a & 1) { if(b & 1) return KGCD(a1, b); else return KGCD(a1, b1) << 1; } if(~b & 1) return KGCD(a, b1); if(a b) return KGCD((a-b)1, b); return KGCD((b-a)1, a); } 20 最小公倍数: int LCM(int a,int b) { return a/KGCD(a,b)*b; 。 } 素数相关 素数和合数共同的性质: 1.a 1是合数，当且仅当a = b * c，其中1 < b < a，1 < c < a。 2.合数必有素数因子。 3.如果d 1，p是素数，且d | q，则d = p。 4.设p是素数且p | a*b，则必有p | a或者p | b。 素数的性质: 1.存在无穷多个素数。 2.每个大于1的正整数都有一个素因子。 素数的分布: 素数定理:用π(x)估计小于正整数x的素数有多少个。随着x的增长，π(x) / (x/ln x) = 1。 推论:令pn是第n个素数，其中n是正整数，那么pn ~ n*ln n。 素数的猜想: 1.波特兰猜想:对于任意给定的正整数n，其中n 1，存 21 在一个素数p，使得n < p < 2*n。 2.孪生素数猜想:存在无穷多的形如p和p+2的素数对。 3.哥德巴赫猜想:每个大于2的正偶数可以写成两个素数的和。可推出任一大于7的奇数都可写成三个质数之和的猜想。 普通素数判断 int IsPrime(int N)//注意#include<cmath { if(N <= 1) return 0; int i; for(i = 2; i <= sqrt(N*1.0); ++i) if(N%i == 0) return 0; return 1; } 筛法求素数[1，N] const int MAXN = 1000000; bool Prime[MAXN+100];//Prime[i] == true表示i为素数 void IsPrime() { for(int i = 2; i <= MAXN; ++i) Prime[i] = true; for(int i = 2; i <= MAXN; ++i) 22 if(Prime[i]) for(int j = i+i; j <= MAXN; j+=i) Prime[j] = false; } 篇二:2015届蓝桥杯 第1题:统计不含4的数字 题目大意 统计10000至99999中，不包含4的数值个数。 解题 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 : 第一种解法: 数学 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ，这种是在网上看到的一种解法: 最高位除了0、4不能使用，其余8个数字(1,2,3,5,6,7,8,9)均能使用，剩下的四位(千位、百位、十位、个位) 可以使用除了4以外的所有数字，所以共有 8*9*9*9*9 种解，计算得答案为:52488。 第二种解法: 暴力搜索方法，这个数字的位数共有5位因此，可以设置a, b, c, d, e,分别代表这5位。 代码: #include <iostream #include <cstdio using namespace std; 23 int main() { int a, b, c, d, e; int count = 0; for(a = 1; a <= 9; a++) { for(b = 0; b <= 9; b++) { for(c = 0; c <= 9; c++) { for(d = 0; d <= 9; d++) { for(e = 0; e <= 9; e++) { if(a != 4 && b != 4 && c != 4 && d != 4 && e !=4) { count++; } } } } 24 } } cout<<count<<endl; return 0; } 输出为: 52488 第2题:计算1千天后的日期 题目大意 2014-11-09再过1000天是哪一日, 解题分析: 我想这里题目，对于大家来说分析的时候难点就在于那年 是闰年，那年是平年 那么从2014到2017年之间2016年是闰年，因此这一年 就是365天， 这道题，我是手算的。 答案是: 2017-08-05 重点是要按照 格式 pdf格式笔记格式下载页码格式下载公文格式下载简报格式下载 提交。 第3题:竖式加法 题目大意 祥 瑞 生 辉 三 羊 献 瑞 ???????? 25 三 羊 生 瑞 气 题目用了8个不同的汉字，表示0~9里八种不同的数字。组成两个数值相加，等于第三个数值。 求三羊献瑞”对应到数字是多少, 解题分析: 第一种暴力搜索: 我假设结果中进位的是1，那么三对应的就是数字1. 接下来定义变量。 a b c d + 1 e f b ------------------ 1 e c b g 代码: 这段代码输三个结果，把每个结果带进去试一下就知道那个是了。 #include <iostream #include <cstdio using namespace std; int main() { int a, b, c, d, e, f, g; for(a = 1; a <= 9; a++) 26 { for(b = 0; b <= 9; b++) 篇三:算法模板【最后更新2014-05】 算法模板 网络122 王硕 目录 1.数学 1.1 矩阵 ………………………2 1.2 一次方程组的解 ……………3 1.3 矩阵的逆 …………………4 1.4 最大公约数 …………………6 1.5 欧几里得扩展 ……………6 1.6 素数表 ………………………7 1.7 判断素数 …………………8 1.8 分解质因数 …………………9 1.9 欧拉函数 …………………10 1.10 欧拉函数表 …………………11 1.11 mobius函数 …………………12 1.12 数值积分 …………………12 1.13 数值积分(精确) ………13 1.14 快速幂求余 …………………14 1.15 进制转换 …………………15 1.16 格雷码 ………………………16 1.17 高精度类 …………………16 1.18 Fibonacci数列 ……………22 1.19 FFT ………………………23 2.图论 2.1 拓扑排序 …………………24 2.2 dijkstra …………………25 2.3 floyd-warshall ……………26 2.4 27 kruskal …………………26 3.序列 3.1 快速排序 …………………28 3.2 逆序对 ………………………28 3.3 最长不降子序列长度 ………30 3.4 最长公共子序列长度 ………31 3.5 最长公共上升子序列长度 …31 3.6 最长公共上升子序列 ………32 4.字符串 4.1 Sunday ………………………34 4.2 子串清除 …………………34 4.3 KMP ………………………37 5. 数据结构 5.1 并查集 ………………………38 5.2 树状数组 …………………39 5.3 左偏树 ………………………40 5.4 哈希 ………………………41 5.5 RMQ线段树 …………………41 6.其他 6.1 多边形面积 …………………43 6.2 幻方构造 …………………43 6.3 奇数阶次幻方 ……………45 1.1矩阵 #include <iostream #include <cstring using namespace std; const int MAXN=100; const int MAXM=100; struct Matrix { int n,m; int a[MAXN][MAXM]; 28 void clear() { m=n=0; memset(a,0,sizeof(a)); } Matrix operator +(const Matrix &b) const { Matrix tmp; tmp.n=n; tmp.m=m;for(int i=0;i<n;i++) for(int j=0;j<m;j++) tmp.a[i][j]=a[i][j]+b.a[i][j];return tmp; } Matrix operator *(const Matrix &b) const { Matrix tmp;tmp.clear(); tmp.n=n; tmp.m=m;for(int i=0;i<n;i++) for(int j=0;j<b.m;j++) for(int k=0;k<m;k++) tmp.a[i][j]+=a[i][k]*b.a[k][j];return tmp; } }; 1.2一次方程组的解 #include <iostream #include <cstring #include <cmath #include <algorithm #define MAX 10 #define EPS 1e-8 using namespace std; double a[MAX][MAX+1]; bool l[MAX]; double ans[MAX]; void swap(double &x,double &y) { double t; t=x; x=y; y=t; } inline int solve(double a[MAX][MAX+1],bool l[],double ans[],const int &n) { 29 int res=0,r=0; int i,j,k; memset(ans,0,sizeof(a)); memset(l,false,n); for(i=0;i<n;i++) { for(j=r;j<n;j++) if(fabs(a[i][j])EPS){ for(k=i;k<=n;k++) swap(a[j][k],a[r][k]); break;} if(fabs(a[r][i])<EPS) { res++; continue; } for(j=0;j<n;j++) if(j!=r&&fabs(a[j][i])EPS){ double tmp=a[j][i]/a[r][i]; for(k=i;k<=n;k++) a[j][k]-=tmp*a[r][k];} l[i]=true; r++; } for(i=0;i<n;i++) if(l[i]) for(j=0;j<n;j++) if(fabs(a[j][i])EPS) ans[i]=a[j][n]/a[j][i];for(i=0;i<n;i++) if(fabs(ans[i])<EPS) ans[i]=0;return res; } int main() { int n; int i,j,res;cinn; for(i=0;i<n;i++) for(j=0;j<n+1;j++)cina[i][j]; 30 res=solve(a,l,ans,n);for(i=0;i<n;i++) cout<<ans[i]<< ;return 0; } 1.3矩阵的逆 #include <iostream #include <vector #include <cmath #include <algorithm #define MAX 10 using namespace std; vector<double a[MAX]; vector<double c[MAX]; inline vector<double operator *(vector<double a,double b) { int i; int n=a.size(); vector<double res(n,0); 相关热词搜索:矩阵 模板 快速 矩阵乘法快速幂 矩阵快 速幂算法 31