15
2016-05
2016-05
乘法逆元模板
乘法逆元的定义
对a∈Zm,存在b∈Zm,使得a×b ≡1 (mod m),则称b为a的乘法逆元。
条件
对于乘法逆元:在mod m的操作下(即Zm中),a存在乘法逆元当且仅当a与m互质。不定方程ab+mx=1的任意一组整数解(b,x),b就是a的乘法逆元。具体计算可以使用扩展欧几里德算法(Extended-GCD)。
//*****************...
05月15日
2,761
14
2016-05
2016-05
字典树模板
const int MAXN=100100;
char s[MAXN],q[MAXN];
struct Trie
{
int next[3000100][26],end[3000100];
int root,L;
int newnode()
{
for(int i=0; i<26; i...
05月14日
2,166
14
2016-05
2016-05
二分图匹配 匈牙利算法与HK算法
二分图匹配
1.一个二分图中的最大匹配数等于这个图中的最小点覆盖数
König 定理是一个二分图中很重要的定理,它的意思是,一个二分图中的最大匹配数等于这个图中的最小 点覆盖数。如果你还不知道什么是最小点覆盖,我也在这里说一下:假如选了一个点就相当于覆盖了以它 为端点的所有边,你需要选择最少的点来覆盖所有的边。
2.最小路径覆盖=|G|-最大匹配数
在一...
05月14日
4,242
18
2016-03
2016-03
Java输入输出模板
常规输入输出绝壁有毒~
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java....
03月18日
2,487
16
2016-03
2016-03
最长上升子序列 模板
int a[M],b[M];
int search(int num,int low,int high)
{
int mid;
while(low<=high)
{
mid=(low+high)/2;
if(num>=b[mid])
low=mid+1;...
03月16日
2,210
16
2016-03
2016-03
RMQ 一维模板
void intRMQ(int n,int b[])
{
mm[0]=-1;
for(int i=1; i<=n; ++i)
{
mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
//计算长度 n为2的倍数 n&n-1==...
03月16日
2,199
16
2016-03
2016-03
最短路模板合集~(Dij+Floyd+Spfa)
自己整理的最短路模板,,对于最短路问题主要就是难在构图方面~~
//Dijstra O(n^2)
//Dijkstra对于有负边权的最短路径不支持
void Dijstra()
{
int i,j;
for(i=0; i<n; ++i)
{
dis[i]=INF;
vis[...
03月16日
2,646
16
2016-03
2016-03
【模板】有向图的强连通分量
const int MAXN = 10010; //点数
const int MAXM = 100100; //边数
struct edge
{
int to,next;
} edge[MAXM];
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN];
int B...
03月16日
2,135