生成函数给定一个无穷序列 $a_0,a_1,a_2,\cdots,a_n,\cdots$ 定义一个函数 $g(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n+\cdots ,-1<x<1$ ，则 $g(x)$ ...

浮点数二分1234567891011double l=0,r=n;while(r-l>1e-6){//若要求n位小数，最好为1e-(n+2) double mid=(l+r)/2; if(check(mid)){...

欧拉路径和欧拉回路欧拉路径即每条边只走一次且能遍历所有边的路径（一笔画） 欧拉回路即起点和终点为同一点的欧拉路径 对于无向图，所有边都是连通的。 存在欧拉路径的充分必要条件：度数为奇数的点只能有0或2个。 存在欧拉回路的充分必要条件：度数为奇数的点...

欧拉函数定义： $1∼N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\phi(N)$。若在算数基本定理中，$N=p^{a_1}_1p^{a_2}_2…p^{a_m}_m$，则：$\phi(N) = N×\frac {...

概率与数学期望性质： $E(aX+bY)=aE(x)+bE(y)$

树与图的搜索有向图存储： 邻接矩阵：$g[a][b]=x$表示从$a$到$b$的一条长度为$x$的边 邻接表：在每个节点上开一个单链表表示当前点到链表中的点有一条边 对于无向图，每一条边$(u,v)$可以看作有向图中的$(u,v),(v...

有向图的强连通分量一个强连通分量中的点都可以互相到达 作用：有向图$\xRightarrow{缩点}$ 有向无环图(DAG) Tarjan算法求强连通分量(SCC) 那么如何判断一个点是否在一个SCC中？ 情况1：存在一条后向边指向祖先节点 情况2：...

最近公共祖先（LCA）最近公共祖先就是多叉树上根节点到两点路径重复部分的深度最低的点 朴素先让两点深度相同，然后同时向上找知道两点相同 123456int lca(int x,int y){ if(d[x]<d[y])swap(...

最短路 单源最短路一个点到其他所有点的长度 Dijkstra稠密图 存储：邻接矩阵 做法： 初始化：$dis[1]=0,dis[i]=+\infty$ 循环$n$次，每次选取没有被确定的距离最近的点$t$，则$t$的值被确定，用...

最小生成树 Prim朴素版Prim稠密图 存储：邻接矩阵 做法： 初始化距离 循环$n$次，每次找到距离集合最近的点，加入集合，用这个点更新其他点到集合的距离 123456789101112131415161718192021222324252...