- 博客(27)
- 收藏
- 关注
RSS订阅原创 网络流详解
文章目录网络流定义最大流最大流建模残量网络增广引理证明求流量增广路结论割割的流量割的容量最小割引理2推论最小割最大流定理证明网络流算法Ford-FulkersonEdmonds-Karp引理DinicLCT优化当前弧优化单位容量网络单位网络例题最大权闭合子图海拔后记网络流定义网络流图定义每条边有两个权值，容量和流量流量不超过每条边的容量流量守恒，每个点流进来和流出去的容量一样源点...
2019-08-01 21:03:38
846
2
原创 分治专题
toc普通分治通过将区间分成两个区间，来将问题分成两个⼦问题求解来康一些经典问题：求所有区间的最⼤大值之和计算mid，然后对于每个区间分成两个区间递归，边界显然是1对于每个区间，设第一次计算固定左端点 l1l_1l1 ,考虑O(1)O(1)O(1)求出所有的以l1l_1l1为左端点跨越mid的最大值只需要先On处理出l1−midl_1 - midl1−mid 的最大值ma...
2019-07-29 22:06:53
352
原创 期望与概率
期望线性性E(x+y)=E(x)+E(y)E(x+y)=E(x)+E(y)E(x+y)=E(x)+E(y) 任意x,yE(x+y)=∑i∑jP(x=i,y=j)(i+j)E(x+y)=\sum_i \sum_j P(x=i,y=j)(i+j)E(x+y)=i∑j∑P(x=i,y=j)(i+j)∑i∑jP(x=i,y=j)i\sum_i \sum_j P(x=i,y=j) ii∑j∑P...
2019-07-29 02:24:56
3495
原创 ZROI contest350
ZROI contest350CBACF[L][R]枚举最后被删的数k转移B克鲁斯卡尔重构树A并茶几暴跳LCA 稳定O（n）
2019-07-26 15:23:04
127
原创 原根简介
一个数m如果有原根，则其原根个数为phi(phi(m))。特别地，对素数有phi§=p-1。假设g是奇素数p的一个原根，则g1,g2,...,g(p−1)g^1,g^2,...,g^{(p-1)}g1,g2,...,g(p−1)在模p意义下两两不同，且结果恰好为1 p−11~p-11 p−1，由此可以定义“离散对数”，与连续数学中的对数有异曲同工之妙。离散对数又叫做“指标”...
2019-07-24 22:45:20
892
原创 BSGS
BSGSbsgs用于求指数方程ax≡b(modm)a^x \equiv b \pmod max≡b(modm)的解然后令x=q∗t−rx = q * t - rx=q∗t−r，得到b∗ar=aq∗tb*a^r = a^{q*t}b∗ar=aq∗t然后就枚举 ：q∈(0,m/t+1),r∈(0,t−1)q \in {(0,m/t+1)} , r \in (0,t-1)q∈(0,m/t+1),r...
2019-07-24 22:05:06
143
原创 卢卡斯定理&扩展卢卡斯
卢卡斯定理&扩展卢卡斯LucasEXlucas例题Lucas卢卡斯定理：(mn)=(mpnp)∗(m(modp)n(modp))(modp)(^n_m)=(^{\frac{n}{p}}_{\frac{m}{p}}) * (^{n \pmod p}_{m \pmod {p}})\pmod p(mn)=(pmpn)∗(m(modp)n(modp))(modp)后面部分可以递归...
2019-07-24 21:52:10
206
原创 Miller-rabin
Miller-rabin米勒罗宾，素数探测小费马定理，本质是欧拉定理的特殊情况即p为质数是a(p−1)≡1(modp)a^{(p-1)} \equiv 1 \pmod pa(p−1)≡1(modp)d的充分条件x2≡1(modp)x^2 \equiv 1 \pmod px2≡1(modp)即x≡1or−1(modp)x \equiv 1or-1 \pmod px≡1or−1(modp)...
2019-07-19 18:22:08
372
原创 扩展欧拉定理
扩展欧拉定理结论证明扩展欧拉定理无需 a,ma,ma,m互质。结论b≥φ(m)时,ab≡a(bmod  φ(m))+φ(m)mod  mb\ge\varphi(m)\text{时},a^b\equiv a^{\left(b\mod\varphi(m)\right)+\varphi(...
2019-07-18 23:46:14
126
原创 中国剩余定理
中国剩余定理中国剩余定理中国剩余定理中国剩余定理，CRT是用来求多组同余方程的解，前提是模数mim_imi两两互质f(x)={x≡a1(modm1)x≡a2(modm2)x≡a3(modm3)...x≡ak(modmk)f(x)=\left\{\begin{aligned}x \equiv a_1 \pmod {m_1}\\x \equiv a_2 \pmod{m_2}\\x \...
2019-07-18 15:37:32
1074
原创 高精度算法进阶
填之前的坑。。高精度算法进阶前言思路代码前言其实也没啥写的，提高组的进阶高精也就高精除高精了（若是想到其他的以后再补）。至于高精开根这些以后省选再写（退役flag高高立起）思路采用二分，mid*高精小数与高精大数做 ≤\leq≤ 的比较时间O(nlogn)O(n\log n)O(nlogn)，答案int范围内log\loglog是30多一点，常数写好就不怕（至少比一个一个减要好...
2019-06-21 23:39:13
158
原创 线段树合并
线段树合并思路代码实现例题今天写DSU on tree 的时候发现不会写线段树合并，于是滚来写线段树合并博客思路对于值域相同的两个权值线段树xxx和yyy（假设把yyy合并到xxx上），每个节点有两种情况：其中至少有一个节点没有权值(!x∣∣!y)(!x||!y)(!x∣∣!y)直接x=x+yx=x+yx=x+y (x==0?y:x)(x==0?y:x)(x==0?y:x)两个点都有...
2019-06-17 21:24:10
141
原创 斯特林数
组合数学——斯特林数第一类斯特林数定义递推式应用问题说明分析第二类斯特林数定义递推式应用分析例题最近看的数数题比较多。。于是滚来写组合数学的博客第一类斯特林数定义把n个不同数划分为m个圆排列的方案数递推式如果第nnn个数自成一个圆，那么S1n,m=S1n−1,m−1S1_{n,m}=S1_{n-1,m-1}S1n,m=S1n−1,m−1否则第nnn个数在n−1n-1n−1...
2019-06-11 12:09:24
285
原创 卡特兰数
卡特兰数卡特兰数定义计算方式卡特兰数性质线性递推：卡特兰数定义fn=f0fn−1+f1fn−2+...+fn−1f0f_n=f_0f_{n-1}+f_1f_{n-2}+...+f_{n-1}f_0fn=f0fn−1+f1fn−2+...+fn−1f0也即fn=∑i=0n−1fifn−1−if_n=\sum\limits_{i=0}^{n-1} f_i f_{n-1-i}fn...
2019-06-10 12:38:25
435
原创 高精度算法初步
高精度 vol.1高精构造结构体char数组转高精：高精加高精高精乘单精高精除单精在做一道斯特林数的时候被卡高精。。。于是滚来写一些简单的高精高精构造这里使用结构体封装，方便使用尽量避免直接赋等，会加上个On复杂度所有函数如add(a,b)add(a,b)add(a,b)是在a上加b，a使用地址，速度较快结构体struct bigint{ int length,num[maxn...
2019-06-10 10:58:06
146
原创 区间k大——树套树
树套树定义实现方法问题实现代码定义这里的树套树是用线段树套平衡树线段树用来维护区间位置信息，把这个区间中的所有数插进一颗平衡树中利用线段树信息可加的性质来维护区间k大实现方法问题区间k大问题需要进行几个操作：查询k在区间内的排名查询区间内排名为k的值修改某一位值上的数值查询k在区间内的前驱 (前驱定义为严格小于x，且最大的数)查询k在区间内的后继 (...
2019-05-21 17:03:36
202
原创 最短路算法
最短路Dijkstra堆优化最短路计数SPFA判负环Dijkstra堆优化dijkstra的原理/流程?dijkstradijkstra本质上的思想是贪心,它只适用于不含负权边的图.我们把点分成两类,一类是已经确定最短路径的点,称为"白点",另一类是未确定最短路径的点,称为"蓝点"dijkstradijkstra的流程如下::1.1. 初始化dis[start] = 0,dis[sta...
2019-05-21 11:32:43
151
原创 tarjan复习笔记
tarjanTarjan 求 LCA做法tarjan求强连通分量Tarjan 求 LCA做法总体思想：遍历每一个结点并使用并查集记录父子关系。Tarjan 是一种 DFS 的思想。我们需要从根结点去遍历这棵树。当遍历到某一个结点(称之为 xxx) 时，你有以下几点需要做的。将当前结点标记为已经访问。递归遍历所有它的子节点(称之为 yyy)，并在递归执行完后用并查集合并 xxx...
2019-05-20 13:58:24
111
原创 二分模板
二分模板rt，区间左闭右开注意右端点初值为max+1（右边开区间小于等于这个数（或刚好满足或差一点满足check）while(l<r){ int mid=(l+r)>>1; if(check(mid)){ l=mid; }else r=mid;}return l;...
2019-05-14 20:18:06
101
原创 Prim堆优化
Prim堆优化跟djiktsrad^i_jk^s_tr^adjiktsra一样啦。。。#include<cstdio>#include<iostream>#include<queue>using namespace std;int read(){ int x=0,pos=1;char ch=getchar(); for(;!isdigit(c...
2019-05-14 16:17:28
920
原创 ST表复习笔记
因为线段树套SA求lcp写炸了，于是跑来学ST表ST表是一种高效的查询静态最值的数据结构，在询问次数多的时候具有优势（O(1)查询）ST表构成：OlogN建立，O(1)查询建表：可以先预处理处log和bin(1(1(1<<i)i)i)log：log值向下取整 bin[0]=1;log[1]=0; for(int i=2;i<=22;i++){ //log向...
2019-05-09 17:22:32
159
原创 AC自动机+DP P3041 视频游戏的连击 题解
题意：贝西在玩一款游戏，该游戏只有三个技能键 “A”“B”“C”可用，但这些键可用形成N种(1 <= N<= 20)特定的组合技。第i个组合技用一个长度为1到15的字符串S_i表示。当贝西输入的一个字符序列和一个组合技匹配的时候，他将获得1分。特殊的，他输入的一个字符序列有可能同时和若干个组合技匹配，比如N=3时，3种组合技分别为"ABA", “CB”, 和"ABACB",若贝西...
2019-05-09 13:07:40
157
原创 SPLAY① 入门
splay详解引入splay的构建基础操作建树getrotatesplayinsertkthdeletefindpresuc注意事项splay应用引入splay是一种BST，可以维护静态区间k小也可以当作区间树，维护区间信息（ 求和，最大子段和，翻转区间，等等）时间一般O(nlogn)（均摊），splay操作满足其稳定性但是常数巨大，接近100，慎用splay的构建一个完整的spla...
2019-05-08 13:43:15
309
原创 线段树
线段树总结1、线段树实现方式1、线段树实现方式总之就是二分区间，分为左右儿子存空间n*4，时间mlogn模板：#include<iostream>#include<cstdio>using namespace std;const long long maxn=1e6+5;long long a[maxn],d[maxn<<2],tag[ma...
2019-05-08 11:18:08
101
原创 强势无图详解AC自动机
AC自动机AC自动机_引入AC自动机的构建AC自动机的框架如何建立AC自动机AC自动机查找模板代码注意事项例题后记个人总结向博客注意。。。AC自动机_引入对于k个模式串，我们要匹配一个文本串。如果采用建立k个next数组的方法(kmp)，时间复杂度显然为O((mi+n)*k)，不可接受。那我们就需要一种更简便的数据结构（误），来实现在可控时间范围内(O(n))内的匹配。除此之外...
2019-05-05 20:13:50
169
原创 SA后缀数组详解与运用
SA后缀数组1、后缀数组作用2、后缀数组的构造3、 SA算法的用途4、例题：poj 3261 : Milk Patterns5、后记1、后缀数组作用主要用于解决最长公共前缀（lcp）问题，大多数时候此类问题都可以用sam（后缀自动机）来解决。不过应为sa算法相对更加优秀的时空复杂度，在大数据集上可以防止TMLE。2、后缀数组的构造首先声明几个变量。1、Str ：需要处理的字符串(长度...
2019-05-01 12:27:01
739
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人