搜索
算法模板网络122王硕1目录1.数学1.1矩阵………………………21.2一次方程组的解……………31.3矩阵的逆…………………41.4最大公约数…………………61.5欧几里得扩展……………61.6素数表………………………71.7判断素数…………………81.8分解质因数…………………91.9欧拉函数…………………101.10欧拉函数表…………………111.11mobius函数…………………121.12数值积分…………………121.13数值积分（精确）………131.14快速幂求余…………………141.15进制转换…………………151.16格雷码………………………161.17高精度类…………………161.18Fibonacci数列……………221.19FFT………………………232.图论2.1拓扑排序…………………242.2dijkstra…………………252.3floyd-warshall……………262.4kruskal…………………263.序列3.1快速排序…………………283.2逆序对………………………283.3最长不降子序列长度………303.4最长公共子序列长度………313.5最长公共上升子序列长度…313.6最长公共上升子序列………324.字符串4.1Sunday………………………344.2子串清除…………………344.3KMP………………………375.数据结构5.1并查集………………………385.2树状数组…………………395.3左偏树………………………405.4哈希………………………415.5RMQ线段树…………………416.其他6.1多边形面积…………………436.2幻方构造…………………436.3奇数阶次幻方……………4521.1矩阵#includeiostream#includecstringusingnamespacestd;constintMAXN=100;constintMAXM=100;structMatrix{intn,m;inta[MAXN][MAXM];voidclear(){m=n=0;memset(a,0,sizeof(a));}Matrixoperator+(constMatrix&b)const{Matrixtmp;tmp.n=n;tmp.m=m;for(inti=0;in;i++)for(intj=0;jm;j++)tmp.a[i][j]=a[i][j]+b.a[i][j];returntmp;}Matrixoperator*(constMatrix&b)const{Matrixtmp;tmp.clear();tmp.n=n;tmp.m=m;for(inti=0;in;i++)for(intj=0;jb.m;j++)for(intk=0;km;k++)tmp.a[i][j]+=a[i][k]*b.a[k][j];returntmp;}};31.2一次方程组的解#includeiostream#includecstring#includecmath#includealgorithm#defineMAX10#defineEPS1e-8usingnamespacestd;doublea[MAX][MAX+1];booll[MAX];doubleans[MAX];voidswap(double&x,double&y){doublet;t=x;x=y;y=t;}inlineintsolve(doublea[MAX][MAX+1],booll[],doubleans[],constint&n){intres=0,r=0;inti,j,k;memset(ans,0,sizeof(a));memset(l,false,n);for(i=0;in;i++){for(j=r;jn;j++)if(fabs(a[i][j])EPS){for(k=i;k=n;k++)swap(a[j][k],a[r][k]);break;}if(fabs(a[r][i])EPS){res++;continue;}for(j=0;jn;j++)if(j!=r&&fabs(a[j][i])EPS){doubletmp=a[j][i]/a[r][i];for(k=i;k=n;k++)4a[j][k]-=tmp*a[r][k];}l[i]=true;r++;}for(i=0;in;i++)if(l[i])for(j=0;jn;j++)if(fabs(a[j][i])EPS)ans[i]=a[j][n]/a[j][i];for(i=0;in;i++)if(fabs(ans[i])EPS)ans[i]=0;returnres;}intmain(){intn;inti,j,res;cinn;for(i=0;in;i++)for(j=0;jn+1;j++)cina[i][j];res=solve(a,l,ans,n);for(i=0;in;i++)coutans[i];return0;}1.3矩阵的逆#includeiostream#includevector#includecmath#includealgorithm#defineMAX10usingnamespacestd;vectordoublea[MAX];vectordoublec[MAX];inlinevectordoubleoperator*(vectordoublea,doubleb){inti;intn=a.size();vectordoubleres(n,0);5for(i=0;in;i++)res[i]=a[i]*b;returnres;}inlinevectordoubleoperator-(vectordoublea,vectordoubleb){inti;intn=a.size();vectordoubleres(n,0);for(i=0;in;i++)res[i]=a[i]-b[i];returnres;}inlinevoidinverse(vectordoublea[],vectordoublec[],intn){inti,j;for(i=0;in;i++)c[i]=vectordouble(n,0);for(i=0;in;i++)c[i][i]=1;for(i=0;in;i++){for(j=i;jn;j++)if(fabs(a[j][i]0)){swap(a[i],a[j]);swap(c[i],c[j]);break;}c[i]=c[i]*(1/a[i][i]);a[i]=a[i]*(1/a[i][i]);for(j=0;jn;j++)if(j!=i&&fabs(a[j][i])0){c[j]=c[j]-c[i]*a[j][i];a[j]=a[j]-a[i]*a[j][i];}}}intmain(){intn,i,j;doublex;cinn;6for(i=0;in;i++)for(j=0;jn;j++){cinx;a[i].push_back(x);}inverse(a,c,n);for(i=0;in;i++){for(j=0;jn;j++)coutc[i][j];coutendl;}return0;}1.4最大公约数#includestdio.hintgcd(inta,intb){returnb==0?a:gcd(b,a%b);}intlcm(inta,intb){returna*b/gcd(a,b);}1.5欧几里得扩展#includeiostreamusingnamespacestd;intgcd(inta,intb,int&x,int&y){if(b==0){x=1;y=0;returna;}else{intr=gcd(b,a%b,y,x);y-=x*(a/b);7returnr;}}intmain(){inta,b,x,y;scanf(%d%d,&a,&b);printf(%d,gcd(a,b,x,y));printf(%d%d,x,y);return0;}/*求AB的最大公约数，且求出X,Y使得AX+BY=gcd(A,B);15205-11*/1.6素数表#includeiostream#includecmath#includecstring#defineMAX350000000usingnamespacestd;boolvalid[MAX];intprime[MAX];voidgetprime(intn,int&tot,intans[]){inti,j;memset(valid,true,sizeof(valid));for(i=2;i=n;i++){if(valid[i]){tot++;ans[tot]=i;}for(j=1;(j=tot)&&(i*ans[j]=n);j++){valid[i*ans[j]]=false;if(i%ans[j]==0)break;}}8}intmain(){inti,n,sum=0,j=0;cinn;getprime(n,sum,prime);for(i=1;i=sum;i++){coutprime[i];j++;if(j%10==0)coutendl;}return0;}1.7判断素数#includeiostream#includecmathusingnamespacestd;longlongintrsa(longlonginta,longlongintk,longlongintm){if(k==0)return1%m;longlonginttmp=rsa(a,k1,m);tmp=tmp*tmp%m;if(k&1)tmp=tmp*a%m;returntmp;}booltest(intn,inta,intd){if(n==2)returntrue;if(n==a)returntrue;if((n&1)==0)returnfalse;while(!(d&1))d=d1;longlongintt=rsa(a,d,n);while((d!=n-1)&&(t!=1)&&(t!=n-1)){9t=t*t%n;d=d1;}return(t==n-1)||((d&1)==1);}boolisprime(intn){if(n2)returnfalse;inta[]={2,3,61,4567,23456789},i;for(i=0;i5;i++)if(!test(n,a[i],n-1))returnfalse;returntrue;}intmain(){longlonginti,n,sum=0;cinn;for(i=2;i=n;i++)if(isprime(i)){couti;sum++;if(sum%10==0)coutendl;}return0;}1.8分解质因数#includeiostream#includecmath#defineMAX10000longlonginta[MAX],b[MAX],tot;usingnamespacestd;voidfactor(longlongintn,longlonginta[],longlongintb[],longlongint&tot){longlonginttemp=sqrt(n)+1,now=n;inti;tot=0;for(i=2;i=temp;i++)if(now%i==0)10{a[++tot]=i;b[tot]=0;while(now%i==0){b[tot]++;now/=i;}temp=sqrt(now)+1;}if(now!=1){a[++tot]=now;b[tot]=1;}}intmain(){longlongintn,i;cinn;//fenjie(