快排

procedure qsort(l,r:longint);var i,j,t,m:longint;begin i:=l; j:=r; m:=a[(i+j) div 2]; repeatwhile a[i]
     
      j; if i
      
       l then qsort(l,j);  end;
      
     

 

堆

1.数组开两倍

procedure insert(x:longint);var t,s,v:longint;begin  len:=len+1; f[len]:=x; s:=len;  while (s<>1)and(f[s div 2]>f[s]) do   begin     v:=f[s div 2]; f[s div 2]:=f[s]; f[s]:=v;     s:=s div 2;   end;end;function get:longint;var t,s,v:longint;begin  get:=f[1]; f[1]:=f[len]; len:=len-1; t:=1;  while (t*2<=len)or(t*2+1<=len) do   begin     if (t*2+1>len)or(f[t*2]
     
      f[s] then      begin        v:=f[t]; f[t]:=f[s]; f[s]:=v; t:=s;      end  else break;   end;end;
     

 

 

欧拉函数（单个数值）

function phi(x:longint):longint;var ans,i:longint;begin  ans:=x;  for i:=2 to trunc(sqrt(x)) do   begin   if x mod i=0 then ans:=ans div i*(i-1);   while x mod i=0 do x:=x div i;   end;  if x<>1 then ans:=ans div x*(x-1);  exit(ans);end;

欧拉函数（批量处理）

procedure work;var i,j:longint;begin  p:=0;  for i:=0 to n do e[i]:=i;  for i:=2 to n do    if e[i]=i then     begin j:=i;     while j<=n do begin e[j]:=e[j] div i*(i-1); inc(j,i); end;     end;  for i:=1 to n do   begin     if e[i]=i-1 then begin inc(p); prime[p]:=i; end;   end;end;

质数筛法

procedure work(n:longint);var i,j:longint;begin  num:=0;  for i:=1 to n do g[i]:=true;  for i:=2 to n do   if g[i]=true then    begin      inc(num); prime[num]:=i;      j:=i*2;      while j<=n do begin g[j]:=false; j:=j+i; end;    end;end;

质因数分解

procedure fenjie(x:longint);var i,y:longint;begin  t:=0;y:=x;  for i:=1 to num do   begin     if prime[i]>y div 2 then exit;     if x mod prime[i]=0 then     begin     inc(t); w[t]:=prime[i];     while x mod prime[i]=0 do x:=x div prime[i];     end;     if x=1 then break;   end;end;

 

快速幂

function quick(x,n,p:qword):qword;var ans:qword;begin  ans:=1;  while n>0 do  begin   if n and 1>0 then ans:=cheng(ans,x,p);   x:=cheng(x,x,p);   n:=n>>1;  end;  exit(ans);end;

快速乘

function cheng(x,n,p:qword):qword;var ans:qword;begin ans:=0;  while n>0 do   begin     if n and 1>0 then ans:=(ans+x) mod p;     x:=(x+x) mod p;     n:=n>>1;   end;  exit(ans);end;

 

拓扑排序

for i:=1 to n do if u[i]=0 then begin inc(t); f[t]:=i; end;  repeat    x:=f[t]; dec(t); inc(num);    new(p); p:=a[x];    while p<>nil do     begin       y:=p^.data;         dec(u[y]);       if u[y]=0 then        begin          inc(t); f[t]:=y;        end;       p:=p^.next;     end;  until num=n;

 

 

强连通分量tarjan

思路：dfn为遍历到各点的时间，low表示每个点能够追溯到的最早的栈中节点的次序号 instack表示结点是否在栈中。

对图遍历如果x的儿子y没访问过，则访问并用low[y]更行low[x]，如果x的儿子y被访问过，则用dfn[y]更新low[x]，这样就知道了x最早回溯到的点（在栈中），在栈中low[x]相等的值构成强连通分量。

procedure tarjan(x:longint);var y:longint; p:point;begin  inc(s); low[x]:=s; dfn[x]:=s; inc(t); q[t]:=x;  instack[x]:=true;  new(p); p:=a[x];  while p<>nil do   begin     y:=p^.x;     if dfn[y]=0 then begin tarjan(y); low[x]:=min(low[x],low[y]); end      else if instack[y]=true then low[x]:=min(low[x],dfn[y]);     p:=p^.next;   end;  if dfn[x]=low[x] then   begin     inc(num);     repeat       y:=q[t]; dec(t); f[y]:=x;instack[y]:=false;     until x=y;   end;end;

主程序

for i:=1 to n do begin dfn[i]:=0; low[i]:=0; w[i]:=0; instack[i]:=false; end;  s:=0; t:=0; num:=0;  for i:=1 to n do if dfn[i]=0 then tarjan(i);

 

 

 

树的直径

思路：求树上最长路，对于各个点，求出它儿子中最长和次长的链相加。

procedure dfs(x,e:longint);var p:point; y:longint;begin  s1[x]:=x; s2[x]:=x; new(p); p:=a[x];  while p<>nil do   begin     y:=p^.x;     if y=e then begin p:=p^.next; continue; end;     dfs(y,x);     if f1[y]+p^.v>f1[x] then     begin       f2[x]:=f1[x]; s2[x]:=s1[x];       f1[x]:=f1[y]+p^.v; s1[x]:=y;      end     else     if f1[y]+p^.v>f2[x] then     begin       f2[x]:=f1[y]+p^.v; s2[x]:=y;     end;     p:=p^.next;   end;  if f1[x]+f2[x]>f1[max]+f2[max] then   max:=x;end;

 

kmp算法

p[1]:=0; j:=0;  for i:=2 to m do   begin     while (j>0)and(b[j+1]<>b[i]) do j:=p[j];     if b[j+1]=b[i] then inc(j);     p[i]:=j;   end;  j:=0; kmp:=0;  for i:=1 to n do    begin      while (j>0)and(b[j+1]<>a[i]) do j:=p[j];      if b[j+1]=a[i] then inc(j);      if j=m then begin inc(kmp); j:=p[j]; end;    end;

 

 

LCA

倍增

1.不要忘记dfs后调用work

2.注意枚举2^i时要包含0，注意顺序

procedure work;var i,j:longint;begin  for i:=0 to 19 do   for j:=1 to n do    f[i+1,j]:=f[i,f[i,j]];end;function lca(x,y:longint):longint;var i,t:longint;begin  if deep[x]
     
      >i)and 1=1 then x:=f[i,x];  if x=y then exit(x);  for i:=19 downto 0 do   if f[i,x]<>f[i,y] then   begin x:=f[i,x]; y:=f[i,y]; end;  exit(f[0,x]);end;
     

 

二分图

染色

function dfs(x,color:longint):boolean;var p:point; y:longint;begin  new(p); p:=w[x]; g[x]:=color;  while p<>nil do   begin     y:=p^.x;     if g[y]=color then exit(false);     if (g[y]=0)and(not dfs(y,-color)) then exit(false);     p:=p^.next;   end;  exit(true);end;function cheak(s:longint):boolean;var i:longint;begin  for i:=1 to n do g[i]:=0;  for i:=1 to n do   if g[i]=0 then    if not dfs(i,1) then exit(false);  exit(true);end;

 组合

费马小定理，快速求C(n,m)的值

procedure make;var i:longint;begin  f[0]:=1; g[0]:=1;  for i:=1 to n do   begin     f[i]:=(f[i-1]*i) mod num;     g[i]:=g[i-1]*quick(i,num-2) mod num;   end;end;function get(x,y:int64):int64;var i:longint; t:int64;begin  if (x=0)or(y=0)or(x=y) then exit(1);  exit(((f[x]*g[x-y]) mod num)*g[y] mod num);end;

 

同余

ax≡1(mod m)

program asdf;var  a,m,x,y,t:longint;function extgcd(a,b:longint;var x,y:longint):longint;var d:longint;begin  if b<>0 then begin d:=extgcd(b,a mod b,y,x); y:=y-(a div b)*x; end   else begin x:=1;y:=0; d:=a; end;  exit(d);end;begin  readln(a,m);  x:=0; y:=0;  t:=extgcd(a,m,x,y);  writeln((x+m) mod m);end.