[综合] 等比数列二分求和取模

Sn=a+a2+...+an 要求Snmodp如果用公式算，可能溢出，因此用二分法求1)若n是偶数Sn=a+...+a^(n/2)+a^(n/2+1)+a^(n/2+2)+...+a^(n/2+n/2) =(a+...+a^(n/2))+a^(n/2)*(a+...+a^(n/2))=Sn/2+a^...

[综合] 欧几里得算法及其应用

1）求最大公约数 intgcd(inta,intb) {if(b==0)returna;returngcd(b,a%b); } 2）求最小公倍数 intlcm(inta,intb) {returna*b/gcd(a,b); } 3）扩展欧几里得算法 求ax+by=c的方程的解： 先求出ax+...

[综合] POJ 2115 C Looooops (扩展欧几里得算法)

#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<algorithm> usingnamespacestd; typedeflon...

[综合] 欧拉函数和欧拉定理

1）对于素数p，φ(p)=p-1;2）两个不同的素数p，q，n=p*q φ(n)=φ(p)*φ(q)=(p-1)*(q-1) 3）互质的正整数a和n，有a^φ(n)≡1modn费马小定理：若正整数a与素数p互质，则有a^(p–1)≡1modp。 因为φ(p)=p-1 4）当b是素数，a%b=0，...

[综合] POJ 1006 Biorhythms .

裸的中国剩余定理 求三个数的周期就是求他们的最小倍数 而且这三个数正好互素，所以肯定是中国剩余定理 #include<iostream> usingnamespacestd; intgcdEx(inta,intb,int&x,int&y) {//求ax+by=gcd(a...

[综合] 中国剩余定理一般情况

给定正整数n1,n2,...,nk(未必两两互质),要求找到x,满 足x≡ai(modni)(i=1,2...k) x≡a1(modn1) x≡a2(modn2) ........... 即n1，....nk之间不一定互质 那便是解k个线性方程，如下 x+u*n1=a1 x-v*n2=a2 .....

[综合] Polya定理模板

暴力版 #include<iostream> #include<cstdio> #include<cmath> usingnamespacestd; typedeflonglongLL; intgcd(inta,intb) {if(b==0)returna;re...

[综合] 最小生成树算法(Prim+Kruskal)

Prim算法： 首先任取一个点u加入最小生成树 1)更新从其他点v出发到u的距离储存在dist中 2)然后选一个dist值最小的点u(1)再收入到最小生成树中，再重复1) 当点全部收录最小生成树时，算法结束 代码如下： #include<iostream> #include<c...

[综合] Bellman_Ford 模板

可以解决有负权边的图，但不能解决有负权回路的图(有负权回路的最短路本来就不存在嘛) 思路： 假设一共有n个点 那么从u~v最多经过n-1个点便肯定能找出最短边(因为最多把其他的点全走一遍就知道最短路径了) 所以算法就是： 从u(起点)出发，经过1个点到v点试试，如果更加小，就更新一下dist 再经过...

[综合] SPFA 模板

SPFA就是Bellman_Ford的优化版 思路：任选一点u开始更新连接的v点的dist值，若能更新v点的dist，就将v点放入队列，更新从v点出发的 因为v被更新了，那么v出发的都可能被更新 直到没有一点可被更新时，算法结束 判断有无负环： 和Bellma_Ford一样，判断每个点只能最多被更...

[综合] Floyd 模板

求每一对顶点之间的最短路径。有向图，无向图均可，也可以有负权边，但不能存在负环 u~v的最短路径可以通过dist[u][k1]+dist[k1][k2]+.....+dist[kn-2][kn-1]+dist[kn-1][v]来确定(k最多为n-1个，且这样计算的前提是存在边) #include&...

[综合] 次小生成树 模板

次小生成树可由最小生成树换一条边得到次小生成树，关键是求MaxVal数组：MaxVal[u][v]保存uv点之间在mst中的边最长的边的长度1）先求一棵MST，利用Prim算法(只能Prim,因为Prim是一个一个收录点的)，且在求的时候求出MaxVal数组，更新MaxVal方法如下：prim算法中...

[综合] 最小费用网络流

思路： 反复用spfa算法做源到汇的最短路进行增广，边权值为边上单位费用。反向边上的单位费用是负的。直到无法增广，即为找到最小费用最大流。 成立原因：每次增广时，每增加1个流量，所增加的费用都是最小的。因为有负权边（取消流的时候产生的），所以不能用迪杰斯特拉算法求最短路。 因为增广的时候要知道上个...

[综合] Korasaju

procedureStrongly_Connected_Components(G); begin 1.深度优先遍历G，算出每个结点u的结束时间f[u],起点如何选择无所谓。 2.深度优先遍历G的转置图GT，选择遍历的起点时，按照结点的结束时间从大到小进行。遍历的过程中，一边遍历，一边给结点做分类...

[综合] Tarjan求强连通(缩点)

#include<iostream> #include<cstdio> #include<vector> #include<stack> #include<cstring> #include<algorithm> usingna...

[综合] 求桥和割点的Tarjan算法

low[u]定义为u或者u的子树中能够通过非父子边追溯到的最早的节点的DFS开始时间 dfn[u]表示dfs下u的开始时间 割点：无向连通图中，如果删除某点后，图变成不连通，则称该点为割点。 桥：无向连通图中，如果删除某边后，图变成不连通，则称该边为桥。 判断割点方法： (1)u为树根，且u有多...

[综合] 求无向图连通图点双连通分支

点双连通分支：不包含割点的极大连通子图 算法思路： 建立一个栈，存储当前双连通分支，在搜索图时，每找到一条树枝边或反向边(连到树中祖先的边），就把这条边加入栈中。如果遇到某树枝边（u,v)满足dfn(u)<=low(v)，说明u是一个割点，此时把边从栈顶一个个取出，直到遇到了边(u,v)，取...

[综合] 求无向连通图边双连通分支

边双连通分支：不包含桥的极大连通子图 算法思路： 只需在求出所有的桥以后，把桥边删除，原图变成了多个连通块，则每个连通块就是一个边双连通分支。桥不属于任何一个边双连通分支，其余的边和每个顶点都属于且只属于一个边双连通分支。 #include<iostream> #include&l...

[综合] POJ 2449 Remmarguts' Date A* -

求第s~t第k短的路 先求出所有点到t的最短路径，这可以通过保存逆邻接表来求 这是求出h(u)的精确值dist[u]，g()就是离s(起点)点经过多少距离 从优先队列里取出f最小的点，该点扩展数加1，扩展他连接的点，放入优先队列 原理类似Dijkstra，扩展到的点就是s出发最短路径，第i次扩展到u...

[综合] POJ 2286 UVA 1343 The Rotation Game IDA*

以前看刘汝佳的方法写过，现在再写一遍 以下是自己意淫的IDA* g()是旋转的次数； h()的求法：每次移动最多只会使得中央区域包含的数字种类减少1种。求出中央区域个数最多的那个数字的个数n，要达到中央区域数字都相同，至少需要8-n次操作，此即估价函数值 //12 //34 //567891011...