搜索
简帛阁>技术文章>AcWing 算法基础课 高斯消元、组合数

AcWing 算法基础课 高斯消元、组合数

一、高斯消元

对矩阵n*n*x=列向量n

枚举每一列(c+,r)

  1、找到当前列绝对值最大的行(如果为0则下一列)

  2、将当前行与1、中的行的元素交换

  3、将当前行的当前列元素化为1

  4、利用当前行的元素,将后面行的当前列的元素化为0(先枚举后面的行,后面的行的当前列元素不为0,则每个列都消)

  5、r++

r<n

  若出现0=非0的行,无解

  否则,无穷多解

消去上三角的其他部分(从后往前遍历行,每次遍历用后面的行减)

r==n

  唯一解

 

二、组合数

  1、利用递推式,预处理出所有可能的组合数,适用于数值比较小但查询次数多。(a<2000),O(n^2)

    C(a,b)=C(a-1,b)+C(a-1,b-1)(从实际意义出发可得公式)

    边界情况(j==0)时,C(i,j)为1

    共计预处理出a*a个数

  2、C(a,b)=a!/(b!(a-b)!),可以预处理出全部a!的值,适用于数值适中且查询次数多。(a<10^5),O(nlogn),logn在求逆元时出现

    共计预处理出a个数

    注意,除法计算后取模,不等于同时将上下取模,需要利用求逆元的方式,转换成乘法。

  3、卢卡斯定理,适用于询问少但是数据范围很大题目,O(p*logn*logp),p为结果取余的除数,需要a或b>p

    C(a,b)=C(a%p,b%p)*C(a/p,b/p) (mod p)

  4、一次询问,不取模,结果会很大,需要用高精度算法

    对C(a,b)=a!/(b!(a-b)!)进行分解质因数。

    a!中质因子p的个数为[a/p]+[a/p^2]+[a/p^3]+...

    得到a!/(b!(a-b)!)的质因子后,利用高精度乘法求解

一、高斯消元对矩阵n*n*x列向量n枚举每一列(c+,r)1、找到当前列绝对值最大的行(如果为0则下一列)2、将当前行与1、中的行的元素交换3、将当前行的当前列元素化为14、利用当前行的元素,将后面行
Trie树可以用来存储前缀字符串/数组。可以用数组进行模拟son[N][26]记录节点的soncnt[N]记录以当前节点为最后字符的字符串出现的次数idx当前用到的节点例题143最大异或对includ
MP用于o(n)的字符串匹配。使用next数组记录以当前阶段为后缀的,和以开始位置为前缀匹配的最长长度,即匹配过程中进行后移后保留的长度。next数组的计算和匹配过程类似。推荐数组从1开始计数AcW
链表一般不用结构体创建(new的使用很慢)而是用邻接表进行表示两个数组分别e[]和ne[]分别记录节点的值和下一个节点的编号head记录头结点指向的位置,idx表示当前可以使用的节点用数组模拟链表时,
一、质数质数是大于1的自然数,只包含1和本身两个约数。1、质数的判定,O(sqrt(n))试除法,推荐循环i<n/i(防止溢出和sqrt计算)2、分解质因子,O(logn~sqrt(n))1fo
堆可以用二叉树存储。当前节点比左右子节点的值都小或等于(小根堆)。对于完全二叉树,根节点编号为1,则,对于编号为n的节点,左子节点编号为2n,右子节点标号为2n+1。完全二叉树可以用一维数组存储(编号
最短路问题一、单源最短路(一个点到所有点的最短距离)1、所有边的权重都为正n个点,m个边(1)朴素dijkstraO(n^2)适合稠密图,O(n^2)O(m)算法步骤:①初始化距离dis[1]0,di
图可以用邻接表存储,邻接表为n个链表,链表可以用数组模拟(比vector速度快)。constintN;inth[N],e[N],ne[N],idx;//分别表示,h[i]:图中编号i的头结点,e[i]
知识点基础算法——代码模板链接常用代码模板1——基础算法排序二分高精度前缀和与差分双指针算法位运算离散化区间合并数据结构——代码模板链接常用代码模板2——数据结构链表与邻接表:树与图的存储栈与队列:
基础算法排序快速排序归并排序二分整数二分浮点二分高精度前缀和与差分双指针算法位运算离散化区间合并仅个人记录方便复习排序快速排序思想——分治1、确定分界点以为分界点,这与归并排序不同,归并排序以中