更新日志
2019.2.16
- 修复珂朵莉树代码中的错误
- FFT板子更新为预处理单位复根的版本(多项式基本操作请移步多项式算法总结qwq)
2019.2.17
- 新增NTT板子
2019.2.25
- 新增替罪羊树板子
2019.3.6
- 新增K-D Tree(2-D Tree) -> [简单题AC代码]
- 更新高消板子
- 更新LCT板子
2019.3.31
- 新增Miller-Rabin素数判断
- 新增Pollard-Rho大数分解
2019.4.4
- 新增SAM板子
2019.4.22
- 新增二维凸包
- 新增笛卡尔树
- 新增Manacher
2019.4.26
- 新增毒瘤圆方树
2019.4.27
- 新增广义圆方树
2019.7.18
咕咕咕新增Johnson费用流- 预告:将有(?)封装的多项式全家桶
数学
线性筛
1 | inline void sieve(int n) |
高斯消元
模板题【SDOI2006】异或方程组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
using std::fabs;
using std::swap;
const int maxn=1e3+10;
const double eps=1e-6;
inline int Gauss_Elimination(double (*A)[maxn],double* f,int n)
{
for (int i=1,c=1,j;i<=n;++i)
{
for (j=c;j<=n && fabs(A[j][i])<eps;++j);
if (j==n+1) continue;
for (int k=1;k<=n+1;++k) swap(A[c][k],A[j][k]);
for (int j=c+1;j<=n;++j)
if (fabs(A[j][i])>eps)
{
double t=A[j][i]/A[c][i];
for (int k=i;k<=n+1;++k)
A[j][k]-=t*A[c][k];
}
++c;
}
bool NoAnswer=false,InfAnswer=false;
for (int i=n;i;--i)
{
bool NoVariables=true;
for (int j=i;j<=n;++j)
if (fabs(A[i][j])>eps) NoVariables=false;
if (NoVariables)
if (fabs(A[i][n+1])>eps) NoAnswer=true; // 0=C,C!=0,无解
else InfAnswer=true; // 0=0,无穷多组解
else
{
for (int j=i+1;j<=n;++j) A[i][n+1]-=A[i][j]*f[j];
f[i]=A[i][n+1]/A[i][i];
}
}
if (NoAnswer) return -1; // 无解返回-1..
return !InfAnswer; //无穷多解返回0,有唯一解返回1.
}
int main()
{
static double A[maxn][maxn],f[maxn];
int n;
scanf("%d",&n);
for (int i=1;i<=n;++i)
for (int j=1;j<=n+1;++j)
scanf("%lf",&A[i][j]);
int result=Gauss_Elimination(A,f,n);
if (result^1) return printf("%d\n",result)&0;
for (int i=1;i<=n;++i) printf("x%d=%.2lf\n",i,f[i]);
}
三分
1 | inline double F(double x) |
矩阵快速幂
1 | Matrix operator^ (ll k) |
乘法逆元
线性递推
1 | inv[1]=1; |
阶乘逆元
$\text{inv}(i)=\text{inv}(i+1) \times(i+1)$
有理数取模
1 | inline ll pow(int a,int b,int mod) |
Miller-Rabin
1 | int pr[]={2,3,5,7,11,13,17,19,23,29,31,37}; |
Pollard-Rho
1 |
|
FFT
1 |
|
NTT
1 | inline int qpow(int a,int b,int p) |
计算几何
二维凸包
1 |
|
字符串
Manacher
1 |
|
制胡窜哈希
1 | inline void hs1(char* s) |
KMP
1 | inline void getfail(int n) |
AC自动机
1 | void add(const char* s) |
SA
1 | inline void build_sa(int n,int m) |
SAM
1 |
|
图论
广义圆方树(APIO2018 铁人两项)
1 |
|
静态仙人掌(圆方树)
1 |
|
Kruskal
1 | struct Edge |
LCA
树剖
1 | void dfs(int u,int f,int dep) |
倍增
1 | inline void dfs(int u,int fa,int dep) |
DFS序转RMQ
1 | inline int Min(int x,int y){return depth[x]<depth[y]?x:y;} |
Tarjan
1 | inline int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]);} |
单源最短路径
Dijkstra
1 | void Dijkstra(int s) |
SPFA
1 | void spfa() |
网络流
Dinic最大流
1 | bool bfs() |
Johnson费用流(Dijkstra)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
using std::priority_queue;
const int maxn=5e4+1000;
const int INF=0x3f3f3f3f;
struct Edge
{
int to,next,flow,cost;
}edge[maxn];
struct Node
{
int u,dis;
Node(int u,int dis):u(u),dis(dis){}
bool operator< (const Node& nd){return dis>nd.dis;}
};
int head[maxn],cnt=-1;
inline void _add(int u,int v,int w,int c)
{
edge[++cnt].next=head[u];
edge[cnt].to=v;
edge[cnt].flow=w;
edge[cnt].cost=c;
head[u]=cnt;
}
inline void add(int u,int v,int w,int c){_add(u,v,w,c);_add(v,u,0,-c);}
template<class T>inline T min(T a,T b){return a<b?a:b;}
template<class T>inline T max(T a,T b){return a<b?b:a;}
int dis[maxn],minflow[maxn],pre[maxn],h[maxn];
inline bool Dijkstra(int S,int T,int &mc,int &mf,int n)
{
memset(dis,0x3f,sizeof(dis));
dis[S]=0;pre[S]=-1;minflow[S]=INF;
priority_queue<Node> q;
q.push(Node(S,0));
while (!q.empty())
{
int u=q.top().u,d=q.top().dis;q.pop();
if (dis[u]<d) continue;
for (int i=head[u];~i;i=edge[i].next)
{
if (edge[i].flow==0) continue;
int v=edge[i].to,w=edge[i].cost+h[u]-h[v];
if (dis[v]>d+w)
{
dis[v]=d+w,q.push(Node(v,dis[v]));
pre[v]=i;minflow[v]=min(minflow[u],edge[i].flow);
}
}
}
if (dis[T]==INF) return 0;
for (int i=1;i<=n;++i)
if (dis[i]<INF) h[i]+=dis[i];
int c=minflow[T];
mf+=c;mc+=c*h[T];
for (int u=T;~pre[u];u=edge[pre[u]^1].to)
edge[pre[u]].flow-=c,edge[pre[u]^1].flow+=c;
// printf("%d %d\n",mc,mf);
return 1;
}
inline void mcmf(int S,int T,int n)
{
int mc=0,mf=0;
while (Dijkstra(S,T,mc,mf,n));
printf("%d %d\n",mf,mc);
}
int main()
{
int n,m,S,T;
scanf("%d%d%d%d",&n,&m,&S,&T);
memset(head,-1,sizeof(int)*(n+1));
for (int i=1,u,v,w,f;i<=m;++i)
scanf("%d%d%d%d",&u,&v,&w,&f),add(u,v,w,f);
mcmf(S,T,n);
}
Edmonds-Karp费用流
1 | inline bool spfa() |
割点
1 | inline void tarjan(int u,int rt) |
Tarjan缩点
1 | struct Graph |
2-SAT
1 | inline void tarjan(int u) |
数据结构
ST表
1 | inline void prework(int n) |
线段树2
1 | void build(int l,int r,int o) |
左偏树
1 | inline int merge(int x,int y) |
主席树
1 | inline void insert(int x,int &rt,int oldrt,int l,int r) |
CDQ分治(三维偏序)
1 |
|
点分治
1 | void getroot(int u,int fa) |
笛卡尔树(Luogu P3793)
1 |
|
树链剖分(LOJ模板题,带换根)
1 |
|
LCT
1 |
|
K-D Tree
1 |
|
平衡树
Treap
1 | struct Treap |
替罪羊树
1 |
|
Splay
1 | struct Splay |
权值线段树
1 | void insert(int x,int l=1,int r=n,int o=1) |
树套树
1 | struct Node |
DSU ON TREE(CF600E)
1 |
|
珂朵莉树
1 | struct Node |