标签:位运算,gcd,exgcd,欧拉筛,快速乘,矩阵快速幂,中国剩余定理,欧拉函数,逆元,高斯消元,母函数,斯特林数,卡特兰数,莫比乌斯反演,SG函数与Nim博弈,奇异函数与Wythoff博弈,并查集,线段树,主席树,树状数组,ST表,LCA,BM算法,KMP,Trie树,AC自动机,匈牙利算法,KM算法,Floyd,dijkstra,dijkstra+heap优化,SPFA及LLL与SLF优化,Dinic,MCMF,Kruscal,Prim等等。
数据结构
基础
并查集
1 | int fa[maxn]; |
并查集路径压缩按雉合并
1 | #include<bits/stdc++.h> |
加权并查集
1 | #include<iostream> |
单调队列
1 | #include<iostream> |
链式前向星
1 | int head[maxn], cnt; |
树结构
树状数组
1 | #include<iostream> |
线段树
1 | #include<bits/stdc++.h> |
主席树
1 | // luogu-judger-enable-o2 |
划分树
1 | /** 划分树(查询区间第 k 大)*/ |
Trie树
1 | #include<cstdio> |
伸展树
1 | /* |
LCA(Tarjan)
1 | #include<iostream> |
RMQ
ST表
1 | #include<bits/stdc++.h> |
普通莫队
1 | /* 解释: |
莫队
1 | #include<cstdio> |
动态规划
背包
1 | int nValue,nKind; |
最长上升子序列
1 | const int MAXN=500010; |
最长公共子序列
1 | #include<iostream> |
概率dp
1 | POJ 2096 |
轮廓线dp
1 | /* |
图论
最短路
Dijkstra(邻接矩阵)
1 | #include<iostream> |
Dijkstra
1 | #include<iostream> |
Dijkstra+heap
1 | #include<iostream> |
SPFA
1 | #include<iostream> |
SPFA+SLF优化
1 | #include<bits/stdc++.h> |
Floyd
1 | for(k=1; k<=n; k++) |
K短路
1 | /** |
生成树
Kruskal
1 | #include <iostream> |
Prim
1 | #include <iostream> |
次小生成树
1 | #include <iostream> |
拓扑排序
1 | /*hdu1285--采用二维数组记录两者之间的关系*/ |
网络流
FF
1 | #include<bits/stdc++.h> |
EK
1 | #include <bits/stdc++.h> |
DINIC
1 | #include<iostream> |
DINIC优化
1 | #include<iostream> |
DINIC(邻接矩阵)
1 | #include<iostream> |
ISAP
1 | #include<cstdio> |
MCMF
1 | #include<iostream> |
匹配
匈牙利算法(邻接矩阵)
1 | #include<cstdio> |
匈牙利算法
1 | #include<bits/stdc++.h> |
KM算法
1 | #include<cstdio> |
KM算法最小权匹配
1 | #include<cstdio> |
KM算法最小权匹配优化版
1 | #include<cstdio> |
强连通
Tarjan
1 | #include<bits/stdc++.h> |
Tarjan缩点
1 | #include <iostream> |
2-SAT
1 | HDU 3622 |
数学
数论
gcd
1 | int gcd(int a, int b){ |
exgcd
1 | int exgcd(int a,int b,int &x,int &y){ |
中国剩余定理
1 | #include <iostream> |
欧拉函数
1 | int oula(int n) |
欧拉筛
1 | int prime[maxn]; |
卡特兰数
卡特兰数打表
1 | #include <stdio.h> |
卡特兰数表
1 | #include<stdio.h> |
斯特林数
第一类斯特林数
1 | #include<bits/stdc++.h> |
第二类斯特林数
1 | #include<bits/stdc++.h> |
逆元
逆元(Inverse element)就是在mod意义下,不能直接除以一个数,而要乘以它的逆元。
比如a∗b≡1(modp)a∗b≡1(modp),那么a,b互为模n意义下的逆元,比如你要算x/a,就可以改成x*b%p
观察a∗b≡1(modp)a∗b≡1(modp),变形为a∗b+k∗p=1a∗b+k∗p=1,就可以用扩展欧几里得算法求a了,同时这里也说明了a和p只有在互素的情况下才存在逆元。
注意
在下面所有的算法中,最好先把除数取个模再运算。
扩展欧几里得算法
原理
a∗b≡1(modp)a∗b≡1(modp)
a∗b+k∗p=1a∗b+k∗p=1
然后a就是我们要求的逆元,最终得到一个正数a的话就要对a mod p,因为a加上mp的时侯k减少mb可以使得等式依然成立。
如果你不想让逆元为正数,那么直接返回x也是可以正确的逆元
代码
1 | LL exgcd(LL a,LL b,LL &x,LL &y)//扩展欧几里得算法 |
注意:返回的时候可以改成(x+mod)%mod,因为扩展欧几里得算法算出来的x应该不会太大.
性能分析:
时间复杂度:O(logn)(实际是斐波那契数列)
适用范围:只要存在逆元即可求,适用于个数不多但是mod很大的时候,也是最常见的一种求逆元的方法。
费马小定理/欧拉定理
原理
费马小定理:若p为素数,则有ap−1≡1(modp)ap−1≡1(modp)
ap−2∗a≡1(modp)ap−2∗a≡1(modp)
ap−2ap−2就是a在mod p意义下的逆元啦。
欧拉定理:若a、p互素,则有aφ(p)≡1(modp)aφ(p)≡1(modp)(费马小定理的一般形式)
aφ(p)∗a≡1(modp)aφ(p)∗a≡1(modp)
aφ(p)−1aφ(p)−1就是a在mod p意义下的逆元啦。
代码
1 | LL qkpow(LL a,LL p,LL mod) |
性能分析:
O(logmod)
适用范围:一般在mod是个素数的时候用,比扩欧快一点而且好写。
但是如果是合数,相信一般没人无聊到去算个欧拉函数。
递推求逆元
原理
p是模数,i是待求的逆元,我们求的是i−1i−1在mod p意义下的值
p=k∗i+rp=k∗i+r令 r < i,则k=p/i,r=p%i
k∗i+r≡0(modp)k∗i+r≡0(modp)
k∗r−1+i−1≡0(modp)k∗r−1+i−1≡0(modp)
i−1≡−k∗r−1(modp)i−1≡−k∗r−1(modp)
i−1≡−p/i∗inv[pmodi]i−1≡−p/i∗inv[pmodi]
嗯。。好难看的公式
说白了就是:inv[i]=-(mod/i)*inv[i%mod]
然后边界是inv[1]=1
这不仅为我们提供了一个线性求逆元的方法,也提供了一种O(logmod)求逆元的方法
代码
线性求逆元
1 | LL inv[mod+5]; |
注意:
调用前要先预处理
调用的时候要先对除数取mod
性能分析:
时间复杂度O(n)
适用范围:mod数是不大的素数而且多次调用,比如卢卡斯定理。
递归求逆元
1 | LL inv(LL i) |
性能分析
时间复杂度:O(logmod)
好像找到了最简单的算法了!!
适用范围: mod数是素数,所以并不好用,比如中国剩余定理中就不好使,因为很多时候可能会忘记考虑mod数是不是素数。
miller-rabin,Pollard_rho算法
大素数判断和素因子分解
1 | #include<stdio.h> |
组合数学
Lucas定理
费马小定理实现
1 | #include <iostream> |
exgcd实现
1 | #include <iostream> |
全排列全组合
1 | /**** **** **** **** **** **** |
母函数
1 | #include <iostream> |
容斥原理
1 | #include <stdio.h> |
莫比乌斯反演
1 | const int MAXN = 1000000; |
莫比乌斯Euler打表
1 | #include<bits/stdc++.h> |
离散对数
1 | #include <stdio.h> |
自适应 simpson 积分
1 | double simpson(double a,double b) |
线性代数
快速幂
1 | #include<bits/stdc++.h> |
矩阵快速幂
1 | const int N=10; |
快速乘
如果要求模的常数是一个64bit整数,那么在做乘法时,就没有扩展类型使用,必须手写一个高精度整数运算。
O(logn)快速乘
1 | inline LL quick_mul(LL a,LL n,LL m){ |
O(1)快速乘
1 | typedef long long ll; |
首先,使用浮点数计算 ab/MOL 的值,关键在于第二句,显然 ab - d*MOL 两个乘法都可能溢出,不过没关系,因为可以预见,其差是一个64bit可以容纳的正整数,那么溢出部分的差仅可能是0或者1。最后一句符号的特判用来处理溢出部分差为1的情况。
考虑到计算 a*b/MOL 使用了浮点数计算,误差是不可避免的,故建议不要用太大的MOL使用这个方法。
模板
1 | inline ll ksc(ll x,ll y,ll mod){ |
因为x,y都是mod意义下的,保证了x*y/mod不会爆long long。
高斯消元
1 | /**** **** **** **** **** **** |
字符串
字符串hash
1 | const int HASH = 10007; |
字符串和数值hash
1 | // 整数hash |
BM
1 | int* CreateBC(char* pattern, int len) |
KMP
1 | /**** **** **** **** **** **** |
AC自动机
1 | //该程序不能判别相同模式串,因此若模式串重复,答案会将相同模式串当做不同的处理,因此若需要可以用map去重或修改insert |
后缀自动机
1 | const int CHAR = 26; |
计算几何
基础计算几何
几何公式
三角形
1 | \1. 半周长 P=(a+b+c)/2 |
四边形
1 | D1,D2为对角线,M对角线中点连线,A为对角线夹角 |
正n边形
1 | R为外接圆半径,r为内切圆半径 |
圆
1 | \1. 弧长 l=rA |
棱柱
1 | \1. 体积 V=Ah,A为底面积,h为高 |
棱锥
1 | \1. 体积 V=Ah/3,A为底面积,h为高 |
棱台
1 | \1. 体积 V=(A1+A2+sqrt(A1A2))h/3,A1.A2为上下底面积,h为高 |
圆柱
1 | \1. 侧面积 S=2PIrh |
圆锥
1 | \1. 母线 l=sqrt(h^2+r^2) |
圆台
1 | \1. 母线 l=sqrt(h^2+(r1-r2)^2) |
球
1 | \1. 全面积 T=4PIr^2 |
球台
1 | \1. 侧面积 S=2PIrh |
球扇形
1 | \1. 全面积 T=PIr(2h+r0),h为球冠高,r0为球冠底面半径 |
直线与线段
预备函数
1 | **//结构定义与宏定义** |
判三点是否共线
1 | int dots_inline(point p1,point p2,point p3) |
判点是否在线段上
1 | **//判点是否在线段上,包括端点(下面为两种接口模式)** |
判断两点在线段的同一侧
1 | **//判两点在线段同侧,点在线段上返回0** |
判断两点是否在线段的异侧
1 | **//判两点在线段异侧,点在线段上返回0** |
求点关于直线的对称点
1 | **// 点关于直线的对称点 // by lyt** |
判断两线段是否相交
常用版
1 | //定义点 |
不常用版
1 | **//判两线段相交,包括端点和部分重合** |
求两条直线的交点
1 | **//计算两直线交点,注意事先判断直线是否平行!** |
点到直线的最近距离
1 | point ptoline(point p,point l1,point l2) |
点到线段的最近距离
1 | point ptoseg(point p,point l1,point l2) |
多边形
预备浮点函数
1 | \#include <stdlib.h> |
判定是否是凸多边形
1 | **//判定凸多边形,顶点按顺时针或逆时针给出,允许相邻边共线,是凸多边形返回1,否则返回0** |
判定点是否在多边形内
1 | **//判点在凸多边形内或多边形边上时返回1,严格在凸多边形外返回0** |
判定一条线段是否在一个任意多边形内
1 | **//预备函数** |
三角形
预备函数
1 | \#include <math.h> |
求三角形的外心
1 | point circumcenter(point a,point b,point c) |
求三角形内心
1 | point incenter(point a,point b,point c) |
求三角形垂心
1 | point perpencenter(point a,point b,point c) |
圆
预备函数
1 | \#include <math.h> |
判定直线是否与圆相交
1 | //判直线和圆相交,包括相切 |
判定线段与圆相交
1 | int intersect_seg_circle(point c,double r, point l1,point l2) |
判圆和圆相交
1 | int intersect_circle_circle(point c1,double r1,point c2,double r2) |
计算圆上到点p最近点
1 | **//当p为圆心时,返回圆心本身** |
计算直线与圆的交点
1 | **//计算直线与圆的交点,保证直线与圆有交点** |
计算两个圆的交点
1 | **//计算圆与圆的交点,保证圆与圆有交点,圆心不重合** |
球面
给出地球经度纬度,计算圆心角
1 | \#include <math.h> |
已知经纬度,计算地球上两点直线距离
1 | **//计算距离,r为球半径** |
已知经纬度,计算地球上两点球面距离
1 | **//计算球面距离,r为球半径** |
三维几何的若干模板
预备函数
1 | **//三维几何函数库** |
判定三点是否共线
//判三点共线
1 | int dots_inline(point3 p1,point3 p2,point3 p3){ |
判定四点是否共面
1 | **//判四点共面** |
判定点是否在线段上
1 | **//判点是否在线段上,包括端点和共线** |
判断点是否在空间三角形上
1 | **//判点是否在空间三角形上,包括边界,三点共线无意义** |
判断两点是否在线段同侧
1 | **//判两点在线段同侧,点在线段上返回0,不共面无意义** |
判断两点是否在线段异侧
1 | **//判两点在线段异侧,点在线段上返回0,不共面无意义** |
判断两点是否在平面同侧
1 | **//判两点在平面同侧,点在平面上返回0** |
判断两点是否在平面异侧
1 | **//判两点在平面异侧,点在平面上返回0** |
判断两空间直线是否平行
1 | **//判两直线平行** |
判断两平面是否平行
1 | **//判两平面平行** |
判断直线是否与平面平行
1 | **//判直线与平面平行** |
判断两直线是否垂直
1 | **//判两直线垂直** |
判断两平面是否垂直
1 | //判两平面垂直 |
判断两条空间线段是否相交
1 | **//判两线段相交,包括端点和部分重合** |
判断线段是否与空间三角形相交
1 | **//判线段与空间三角形相交,包括交于边界和(部分)包含** |
计算两条直线的交点
1 | **//计算两直线交点,注意事先判断直线是否共面和平行!** |
计算直线与平面的交点
1 | **//计算直线与平面交点,注意事先判断是否平行,并保证三点不共线!** |
计算两平面的交线
1 | **//计算两平面交线,注意事先判断是否平行,并保证三点不共线!** |
点到直线的距离
1 | **//点到直线距离** |
计算点到平面的距离
1 | **//点到平面距离** |
计算直线到直线的距离
1 | **//直线到直线距离** |
空间两直线夹角的cos值
1 | **//两直线夹角cos值** |
两平面夹角的cos值
1 | **//两平面夹角cos值** |
直线与平面夹角sin值
1 | //直线平面夹角sin值 |
高级计算几何
最远曼哈顿距离
1 | \#include <stdio.h> |
最近点对
1 | \#include <stdio.h> |
最小包围圆
1 | \#include<stdio.h> |
求两个圆的交点
1 | \#include<stdio.h> |
求三角形外接圆圆心
1 | struct Point |
求凸包
1 | \#include <stdio.h> |
凸包卡壳旋转求出所有对踵点、最远点对
1 | \#include <stdio.h> |
凸包+旋转卡壳求平面面积最大三角
1 | \#include <stdio.h> |
Pick定理
1 | **// Pick定理求整点多边形内部整点数目** |
求多边形面积和重心
1 | \#include <stdio.h> |
判断一个简单多边形是否有核
1 | \#include <stdio.h> |
模拟退火
1 | \#include <stdio.h> |
六边形坐标系
1 | **//第一种六边形坐标系** |
用一个给定半径的圆覆盖最多的点
1 | **//同半径圆的圆弧表示** |
不等大的圆的圆弧表示
1 | intersection_circle_circle(circle[i].center, circle[i].r, circle[j].center, circle[j].r, p1, p2); |
矩形面积并
1 | \#include<stdio.h> |
矩形的周长并
1 | \#include <stdio.h> |
最近圆对
1 | \#include<iostream> |
求两个圆的面积交
1 | double area_of_overlap(point c1, double r1, point c2, double r2) |
博弈论
Nim博弈
1 | #include <iostream> |
威佐夫博弈
1 | #include<iostream> |
其他
整数划分
1 | #include<iostream> |
区间K大数
1 | #include <iostream> |
离散化
1 | int getid(int x){ |
位运算
统计1的个数
1 | int NumberOfOne(int n) { |
strtok 和 sscanf 结合输入
空格作为分隔输入,读取一行的整数:
1 | gets(buf); |
输入输出挂
1 | //适用于正负整数 |