前几天看到Neal_Wu的youtube视频中用的一个求INV11(对11的乘法逆元)在mod一个大数M下的方法. 视频链接: https://www.youtube.com/watch?v=8ukwV6rCvPg&t=367s 假设, 我们在11*i ≡ 1 mod 31中求i, 那么相当于我们在求一个x使得11 * ((x*31+1) / 11) ≡ 1 mod 31 where x∈[1,2,3,….]. 然后, 我们从1开始, 逐个试(x*31+1) % 11 ?= 0中的这个x是多少, 因为只有整除的x才是我们想要的. 这里我们从1一直试到6, 然后发现(6*31+1) % 11 = 0, 所以这里的(6*31+1) / 11 = 17的17就是INV11在模31下. 我们直接记录这个INV11可以减少运算时间. 这里的31是很小的数字, 有很多别的方法也可以求, 比如费马小定理, 但是如果是很大的数字就用这个比较省时间.

这个算法又叫matrix tree theorem. 是一种计算一个无向图上生成树的个数的矩阵运算方法. 给一个图G, 这个图可连续也可不连续, 啥样子都可以. 设G的拉普拉斯矩阵(又名: 调和矩阵)为Q. 则我们可以通过计算Q11(删除第一行和第一列)的行列式, 得知G的生成树个数.

今天了大神的youtube https://www.youtube.com/watch?v=-OPohCQqi_E 加法 (a+b) % mod 这个是错的啊, 因为a+b已经overflow了, 所以要写成 ((a % mod) + (b % mod)) % mod 乘法 (a*b) % mod 这个也是错的啊, 因为a*b已经overflow了, 所以要写成 ((a % mod) * (b % mod)) % mod 减法 (a-b) % mod 这个是错的啊, 因为a-b不是如果是负的, 那么就是负数mod了, 但是a-b本身不存在overflow问题, 所以可以写成 ((a – b) % mod) + mod) % mod 这里的+ mod可以分两种情况考虑: 如果(a-b)是正数, […]

这个就是姚院和Jon Bentley的搜索, 先用exponential的方法找到最近的搜索区域, 然后再用二叉搜索.

TimSort其实就是插入排序和合并排序的综合体. 首先切分数组, 然后利用插入排序对小数组的优势, 先sort小数组, 然后再merge几个小数组. code我是直接抄github的

Combosort是一个基于swap的排序, 和冒泡排序一样, 它改良了冒泡排序中只对相邻元素做比较然后swap的特点, 通过使用gap 表示两个数时间的index位置, 然后用gap除以一个经验定值1.3,获得当前比较的两个数的位置. gap从n一直减小到1, 然后完成排序.

就是两边的冒泡排序, 和普通的冒泡排序一样通过不停的swap从队列中选择最值(最大or最小)的元素放到两侧. 一直持续这个操作直到最后.

这个排序的名字很好玩, Bi是双的意思 tonic是音乐的元音. 所以叫双调, 就是两个调性(递增 递减). 具体的操作可以看 https://en.wikipedia.org/wiki/Bitonic_sorter 我主要讲讲下面这个例子: [5,2,1,7,3,8,6,4], len = 8 第一步先临近的两个元素比大小, 比如[5,2]变成[2,5], [1,7]变成[7,1], 数组变为 [2,5], [7,1], [3,8], [6,4] 此时序列为[2,5,7,1,3,8,6,4] 这样就是递增, 递减, 递增 递减的两对儿双调.然后就是合并两个双调. 合并的方法是用的wiki中的batcher理论. 显示四个为一组合并, 然后是两个为一组合并. 四个为一组: [2,1,7,5] ([2,5]和[7,1]合并的结果) [6,8,3,4] ([3,8]和[6,4]合并的结果) 此时的序列为[2,1,7,5,6,8,3,4] 此时, 并不是双调序列, 还需要进行两个为一组的合并. [2,1,7,5] 变成 [1,2,5,7] 递增 [6,8,3,4] 变成 [8,6,4,3] 递减, 此时序列为[1,2,5,7,8,6,4,3] 最后要进行八个一组的合并, 然后是四个一组, 然后是两个一组. 八个一组后: [1,2,4,3,8,6,5,7] 四个一组后: [1,2,4,3,5,6,8,7] 两个一组后: […]

最近在看好玩的算法, 重力排序是一个根据重力(Gravity)原理的自动排序, 这个排序是自然排序的一种, 非人为操作便可实现. 这种排序非常适合给小孩子解释排序的原理和自然需求. 上面这个图就是重力排序, 首先找出最大的数, 上图中是4, 然后设为m, 就是有m个pole(杆子), 这图就是4个杆子. 然后横着看, 每个row就是当前数字有几便有几个球. 比如row 1 (ary[0] = 2) 是2, 就是两个珠子. 然后让数字随着重力下落即可排序, 具体证明和复杂度wiki有. https://en.wikipedia.org/wiki/Bead_sort 可以看出这种排序用机械实现还可以, 用算法实现效率并不好. 上面是一个实现, 具体来说, 最难的地方在于如何实现珠子下落 代码首先计算一个pole上有几个珠子, 然后计算有几个空位, 把空位补上珠子,就是下落后的个数. 最后这个算法的弱点是只能sort正整数, 而且如果数字很离散, 那么效率就太低了

https://arxiv.org/abs/1407.1121 其实就是一个用step来表示抽签个数的概率counting算法.