1、ACM算法模板集ACM算法模板集Contents一.常用函数与STL二.重要公式与定理1.FibonacciNumber2.LucasNumber3.CatalanNumber4.StirlingNumber（SecondKind）5.BellNumber6.StirlingsApproximation7.SumofReciprocalApproximation8.YoungTableau9.整数划分10.错排公式11.三角形内切圆半径公式12.三角形外接圆半径公式13.圆內接四边形面积公式14.基础数论公式三.大数模板，字
2、符读入四.数论算法1.GreatestCommonDivisor最大公约数2.Prime素数判断3.SievePrime素数筛法4.ModuleInverse模逆元5.ExtendedEuclid扩展欧几里德算法6.ModularLinearEquation模线性方程（同余方程）7.ChineseRemainderTheorem中国余数定理（互素于非互素）8.EulerFunction欧拉函数9.Farey总数9.Farey序列构造10.Miller_Rabbin素数测试，Pollard_rho因式分解五.图论算法1.最小生成树
3、（Kruscal算法）2.最小生成树（Prim算法）3.单源最短路径（Bellman-ford算法）4.单源最短路径（Dijkstra算法）.5.16.17.六..七...1.22.全源最短路径（Folyd算法）拓扑排序网络预流和最大流网络最小费用最大流网络最大流（高度标号预流推进）最大团二分图最大匹配（匈牙利算法）带权二分图最优匹配（KM算法）强连通分量（Kosau算法）强连通分量（Gabow算法）无向图割边割
4、点和双连通分量最小树形图O（NW）最小树形图O（VE）几何算法几何模板球面上两点最短距离三点求圆心坐标三角形几个重要的点专题讨论树状数组字典树后缀树线段树并查集二叉堆逆序数（归并排序）树状DP欧拉路八数码高斯消元法字符串匹配（KMP算法）全排列,全组合二维线段树稳定婚姻匹配后缀数组左偏树标准RMQ-ST度限制最小生成树最优比率生成树（0/1分数规划）最小花费置换区间K大数23.LCA-RMQ-ST24.LCA-Tarjan25.指数型母函数26.指数型母函数（大数据）27.单词前缀树（字典树+KMP）28.FFT（大数乘法）29.二分图网络最大流最小割3
5、0.混合图欧拉回路31.无源汇上下界网络流32.二分图最小点权覆盖33.带约束的轨道计数（Burnside引理）34.三分法求函数波峰35.单词计数，矩阵乘法36.字符串和数值hash37.滚动队列，前向星表示法38.最小点基，最小权点基第一章常用函数和STL常用函数#includeintgetchar(void);char*gets(char*str);#include/读取一个字符，一般用来去掉无用字符/读取一行字符串/动态内存分配，开辟大小为size的空间voidqsort(void*buf,size_tnum,size_tsize,in
6、t(*compare)(constvoid*,constvoid*);/快速排序Sample:ints(constvoid*a,constvoid*b)int*argl=(int*)a;int*arg2=(int*)b;if(*arg1*arg2)return-1;elseif(*arg1=*arg2)return0;elsereturn1;intarray=-2,99,0,-743,2,3,4;intarray_size=7;qsort(array,arr
7、ay_size,sizeof(int),s);#include/求反正弦,arg-1,1,返回值-pi/2,+pi/2doubleasin(doublearg);/求正弦，arg为弧度，弧度=角度*Pi/180.0,返回值-1,1doublesin(doublearg);/求e的arg次方doubleexp(doublearg);void*malloc(size_tsize);/求num的对数,基数为edoublelog(doublenum);/求num的根doublesqrt(doublenum
8、);II求base的exp次方doublepow(doublebase,doubleexp);#ineludeII初始化内存，常用来初始化数组void*memset(void*buffer,intch,size_tcount);memset(the_array,0,sizeof(the_array);I/printf是它的变形，常用来将数据格式化为字符串intsprintf(char*buffer,constchar*format,.);sprintf(s,%d%d,123,4567);s=1234567IIscanf是它的
9、变形，常用来从字符串中提取数据intsscanf(constchar*buffer,constchar*format,.);Sample:charresult100=24hello,str100;intnum;sprintf(result,%d%s,num,str);num=24;str=hello;代表str1str2II字符串比较，返回值0代表str10intstrcmp(constchar*str1,constchar*str2);二.常用STL标准container概要vector大小可变的向量，类似数组的用法，list双
10、向链表queue队列，empty(),front(),pop(),push()stack栈,empty(),top(),pop(),push()priority_queue优先队列，empty(),top(),pop(),push()set集合map关联数组，常用来作hash映射标准algorithm摘录for_each()对每一个元素都唤起(调用)一个函数find()查找第一个能与引数匹配的兀素replace()用新的值替换兀素，O(N)copy()复制(拷贝)元素，O(N)remove()移除元素reverse()倒置元素sort()排序,O(Nlog(N)parti
11、al_sort()部分排序binary_search()二分查找merge()合并有序的序列，O(N)C+String摘录copy()从别的字符串拷贝empty()判断字符串是否为空容易实现删除erase()从字符串移除元素find()查找元素insert()插入元素length()字符串长度replace()替换元素substr()取子字符串swap()交换字符串第二章重要公式与定理1.FibonacciNumber0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610Formula:F(0二0;F1=
12、1;Fi=Fil*Fl-2;fFn(i+Vs)-(1-Vs)2亏1+-105-2.LucasNumber1,3,4,7,11,18,29,47,76,123Formula:1+価r1-V522!J3.CatalanNumber1,2,5,14,42,132,429,1430,4862,16796,58786,208012Formula:CnApplication:1）将n+2边形沿弦切割成n个三角形的不同切割数Sample:n=2;n=3;2)n+1个数相乘，给每两个元素加上括号的不同方法数Sample:n
13、=2;(1(23),(12)3)(1(23)4),n=3;(1(2(34),(1(23)4),(12)(34),(12)3)4)3)n个节点的不同形状的二叉树数(严数据结构P.155)4)从n*n方格的左上角移动到右下角不升路径数Sample:n=2;n=3;v*-*%V%4.StirlingNumber(SecondKind)S(n,m)表示含n个元素的集合划分为m个集合的情况数或者是n个有标号的球放到m个无标号的盒子中，要求无一为空，其不同的方案数Formula:S(n-I,Jn-1)+mtS(
14、n-ih)(liink1)*(m-i)SpecialCases:Snf0|=0S(nf1)=1Snt2)=2n11S(nf3j=(3It-3#2n+3)S(nrli-1)=Cpir2)5.BellNumbern个元素集合所有的划分数Formula:Bn=1)1=06.StirlingsApproximationn!二VI石(广7.SumofReciprocalApproximationEulerGamma=0.57721566490153286060651209;A1=lii(n)
15、+.(nco)i=l18.YoungTableauYoungTableau(杨式图表)是一个矩阵,它满足条件：如果格子i,j没有元素,则i+1,j也一定没有元素如果格子i,j有元素ai,j,则i+1,j要么没有元素,要么ai+1,jai,jYn代表n个数所组成的杨式图表的个数Formula:Yl=1；Y2=2；Yn=Yn-1+(n-1)*Y|n-2;(n2)Sample:n=3;9.整数划分将整数n分成k份，且每份不能为空，任意两种分法不能相同1)不考虑顺序for(intp=1;p=n;p+)for(int
16、i=p;i=1;j_)dpij+=dpi-pj-1;coutdpnk0;V/=Base)DataLen+=V%Base;xnum(charS);xnum&operator=(constxnum&V)Len=V.Len;memcpy(Data,V.Data,Len*sizeof*Data);return*this;int&operator(intIndex)returnDataIndex;intoperator(intIndex)constreturnDataIndex;voidprint()print
17、f(%d,Len=00:DataLen-1);for(inti=Len-2;i=0;i_)for(intj=Base/1O;jO;j/=1O)printf(%d,Datai/j%10);xnum:xnum(charS)intI,J;DataLen=0=0;J=1;for(I=strlen(S)-1;l=0;I-)DataLen+=(SI-O)*J;J*=10;if(J=Base)J=1,Data+Len=0;if(DataLen0)Len+;intcompare(constxnum&A,cons
18、txnum&B)intI;if(A.Len匸Bien)returnA丄enBien1:-1;for(I=A丄en-1;I=0&AI=BI;I-);if(IBI1:-1;xnumoperator+(constxnum&A,constxnum&B)xnumR;intI;intCarry=0;for(I=0;IA.Len|I0;I+)if(IA.Len)Carry+=AI;if(IB.Len)Carry+=BI;RI=Carry%Base;Carry
19、/=Base;R.Len=I;returnR;xnumoperator-(constxnum&A,constxnum&B)xnumR;intCarry=0;Rlen=A.Len;intI;for(I=0;IR.Len;I+)RI=AI-Carry;if(IB.Len)RI-=BI;if(RI0&RRlen-1=0)R丄en-;returnR;xnumoperator*(constxnum&A,constintB)intI;if(B=0)return0;xnumR;hu
20、geintCarry=0;for(I=0;I0;I+)if(IA.Len)Carry+=hugeint(AI)*B;RI=Carry%Base;Carry/=Base;R.Len=I;returnR;xnumoperator*(constxnum&A,constxnum&B)intI;if(B.Len=0)return0;xnumR;for(I=0;IA.Len;I+)hugeintCarry=0;for(intJ=0;J0;J+)if(JB.Len)Carry
21、+=hugeint(Al)*BJ;if(I+J=R.Len)RR.Len+=Carry%Base;R;elseRI+J=Carry%Base;Carry/=Base;returnxnumoperator/(constxnum&A,constintB)xnumR;intI;hugeintC=0;for(I=A.Len-1;I=0;I-)C=C*Base+AI;RI=C/B;C%=B;R丄en=A丄en;while(R.Len0&RR丄en-1=0)R丄
22、en-;returnR;/divxnumoperator/(constxnum&A,constxnum&B)intl;xnumR,Carry=0;intLeft,Right,Mid;for(I=A丄en-1;I=0;I-)Carry=Carry*Base+AI;Left=0;Right=Base-1;while(LeftRight)Mid=(Left+Right+1)/2;if(compare(B*Mid,Carry)0&RRlen-1=0)R丄en-;return
23、R;/modxnumoperator%(constxnum&A,constxnum&B)intl;xnumR,Carry=0;intLeft,Right,Mid;for(I=A丄en-1;I=0;I-)Carry=Carry*Base+AI;Left=0;Right=Base-1;while(LeftRight)Mid=(Left+Right+1)/2;if(compare(B*Mid,Carry)0&RRlen-1=0)R丄en-;returnCarry;ist
24、ream&operator(istream&In,xnum&V)charCh;for(V=0;InCh;)V=V*10+(Ch-0);if(cin.peek()=)break;returnIn;ostream&operator(ostream&Out,constxnum&V)intI;Out=0;I-)for(intJ=Base/10;J0;J/=10)OutVI/J%10;returnOut;xnumgcd(xnuma,xnumb)if(compare(b,0)=0)r
25、eturna;elsereturngcd(b,a%b);intdiv(char*A,intB)intI;intC=0;intAlen=strlen(A);for(I=0;I=n-m+1;i-)sum=sum*i;for(i=1;i(constBigNum&T)const;voidprint();BigNum:BigNum(constwhile(dMAXN)c=d-(d/(MAXN+alen+=d;intb)intc,d=b;len=0;memset(a,0,1)*(MA
26、XN+1);d=d/(MAXN+1);alen+=c;sizeof(a);BigNum:BigNum(constchar*s)intt,k,index,l,i;memset(a,0,sizeof(a);l=strlen(s);len=l/DLEN;if(l%DLEN)len+;index=0;for(i=l-1;i=0;i-=DLEN)t=0;k=i-DLEN+1;if(k0)k=0;for(intj=k;jv=i;j+)t=t*10+sj-0;aindex+=t;BigNum:BigNum(constBigNum&T):l
27、en(T.len)inti;memset(a,0,sizeof(a);for(i=0;ilen;i+)ai=T.ai;BigNum&BigNum:operator=(constBigNum&n)len=n.len;memset(a,0,sizeof(a);inti;for(i=0;ilenT.len:len;for(i=0;iMAXN)t.ai+1+;t.ai-=MAXN+1;if(t.abig!=0)t.len=big+1;elset.len=big;return
28、t;BigNumBigNum:operator-(constBigNum&T)constinti,j,big;boolflag;BigNumt1,t2;if(*thisT)t1=*this;t2=T;flag=0;elset1=T;t2=*this;flag=1;big=t1.len;for(i=0;ibig;i+)if(t1.aii)t1.aj-+=MAXN;t1.ai+=MAXN+1-t2.ai;elset1.ai-=t2.ai;tl.len=big;while(t1.alen-1=0&
29、tl.len1)tl.len-;big-;if(flag)t1.abig-1=0-t1.abig-1;returnt1;BigNumBigNum:operator*(constBigNum&T)constBigNumret;inti,j,up;inttemp,temp1;for(i=0;ilen;i+)up=0;for(j=0;jMAXN)temp1=temp-temp/(MAXN+1)*(MAXN+1);up=temp/(MAXN+1);ret.ai+j=temp1;elseu
30、p=0;ret.ai+j=temp;if(up!=0)ret.ai+j=up;ret.len=i+j;ret;while(ret.aret.len-1=0&ret.len1)ret.len-;returnBigNumBigNum:operator/(constint&b)constBigNumret;inti,down=0;for(i=len-1;i=0;i-)ret.ai=(ai+down*(MAXN+1)/b;down=ai+down*(MAXN+1
31、)-ret.ai*b;ret.len=len;while(ret.aret.len-1=0&ret.len1)ret.len-;returnret;intBigNum:operator%(constint&b)constinti,d=O;for(i=len-1;i=0;i-)d=(d*(MAXN+1)%b+ai)%b;returnd;BigNumBigNum:operatorA(constint&n)constBigNumt,ret(1);if(n1)t=*this;inti;f
32、or(i=1;i1=m;i(constBigNum&T)constintIn;if(lenT.len)returntrue;elseif(len=T.len)ln=len-1;while(aln=T.aln&ln=0)ln-;if(ln=0&alnT.aln)returntrue;elsereturnfalse;elsereturnfalse;voidBigNum:print()inti;cout=0;i-)cout.width(DLEN);cout.fill(0);coutdoret
33、=ret*10+ch-while(ch=getchar()charch;9|ch=0);charch;boolneg=false9|ch9|ch0);doret=ret*10+ch-0;while(ch=getchar()=0);ret=(neg-ret:ret);returnok;/读取整数,可判EOF和EOLconstinteof=-1;constinteol=-2;intget_val(int&ret)ret=0;charch;while(ch=getchar()
34、9|ch0)&ch!=EOF);if(ch=EOF)returneof;doret=ret*10+ch-0;while(ch=getchar()=0);if(ch=n)returneol;returnok;/读取浮点数intget_val(double&ret)ret=0;doublebase=0.1;charch;booldot=false,neg=false;while(ch=getchar()9|ch9|ch0)&ch!=.&ch!=-);doif(ch=
35、.)dot=true;continue;if(dot)ret+=(ch-0)*base;base*=0.1;elseret=ret*10+(ch-O);while(ch=getchar()=0)|ch=.);ret=(neg-ret:ret);returnok;第四章数论算法1.GreatestCommonDivisor最大公约数intGCD(intx,inty)intt;while(y0)t=x%y;x=y;y=t;returnx;2.Prime素数判断returnf
36、alse;returntrue;returnfalseboolis_prime(intu)if(u=0|u=1)if(u=2)if(u%2=0)for(inti=3;i=sqrt(u);i+=2)returntrue;if(u%i=0)returnfalse3.SievePrime素数筛法constintM=1000;/M:sizeboolmarkM;/true:primenumbervoidsieve_prime()memset(mark,true,sizeof(mark);mark0=
37、mark1=false;for(inti=2;i=sqrt(M);i+)if(marki)for(intj=i*i;j0/上式等价于二元一次方程ax-ny=bvoidmodular_linear_equation(inta,intb,intn)intd,x,y,x0,gcd;/可以减少扩展欧几里德溢岀的可能gcd=GCD(a,n);if(b%gcd!=0)coutnosolutionendl;return;a/=gcd;b/=gcd;n/=gcd;d=extended_euclid
38、(a,n,x,y);if(b%d=0)x0=(x*(b/d))%n;/x0:basicsolutionintans=n;for(inti=0;id;i+)ans=(x0+i*(n/d))%n;coutansendl;elsecoutnosolution0,且w中任意两个数互质intchinese_remainder(intb,intw,intlen)inti,d,x,y,m,n;ret=0;n=1;for(i=0;ilen;i+)n*=wi;for(i=
39、0;ilen;i+)m=n/wi;d=extended_euclid(wi,m,x,y);ret=(ret+y*m*bi)%n;return(n+ret%n)%n;/m=ri(modai)/ai可以不互素/-1表示无解/*Pku2891StrangeWaytoExpressIntegers假设C=A1(modB1),C=A2(modB2)。令C=A1+X1B，那么X1B1三A2-A1(modB2)。用扩展欧几里德算法求岀X1，也就求岀C。令B=lcm(B1,B2
40、)，那么上面两条方程就可以被C三C(modB)代替迭代直到只剩下一条方程。*/LLchinese_remainder2()inti,j;if(n=1)returnr0;LLm,x,apre;x=modularnear_equation(a0,r1-rO,a1);if(x=-1)return-1;m=x*a0+r0;apre=LCM(a0,a1);for(i=2;in;i+)x=modular_linear_equation(apre,ri-m,ai);if(x=-1)return-1;m=x*apre+m;apre=LCM(apre,ai);returnm;8.EulerFunctio