后缀自动机
int ch[N*2][26],pre[N*2],len[N*2],last=1,k=1;
void Append(int c)
{
int p=last;last=++k;len[k]=len[p]+1;
for(;!ch[p][c]&&p;p=pre[p])
ch[p][c]=k;
if(!p){pre[k]=1;return;}
int np=ch[p][c];
if(len[np]==len[p]+1){pre[k]=np;return;}
int q=++k;
memcpy(ch[q],ch[np],sizeof(ch[q]));
pre[q]=pre[np];len[q]=len[p]+1;
pre[np]=pre[last]=q;
for(;ch[p][c]==np;p=pre[p])
ch[p][c]=q;
}
Dinic
int dis[N],head[N],Next[E],adj[E],cap[E],k=1,S,T;
int que[N],now[N];
void addedge(int u,int v,int w)
{
Next[++k]=head[u],head[u]=k,adj[k]=v,cap[k]=w;
Next[++k]=head[v],head[v]=k,adj[k]=u,cap[k]=0;
}
bool BFS()
{
int i,l,r;
memset(dis,-1,sizeof(dis));
que[l=r=1]=S;
dis[S]=0;
while(l<=r)
{
for(i=head[que[l]];i;i=Next[i])
if(dis[adj[i]]==-1&&cap[i])
{
dis[adj[i]]=dis[que[l]]+1;
que[++r]=adj[i];
}
++l;
}
return (dis[T]!=-1);
}
int fl;
bool DFS(int i,int f)
{
if(i==T)
{
fl=f;
return true;
}
int j;
for(j=now[i];j;now[i]=j=Next[j])
if(dis[adj[j]]==dis[i]+1&&cap[j]&&DFS(adj[j],min(cap[j],f)))
{
cap[j]-=fl;
cap[j^1]+=fl;
return true;
}
return false;
}
long long Dinic()
{
long long ans=0;
while(BFS())
{
memcpy(now,head,sizeof(head));
while(DFS(S,inf))
ans+=fl;
}
return ans;
}
SPFA费用流
int head[N],Next[E],adj[E],cap[E],cost[E];
int q[N*20],pre[N],vis[N],now[N];
int flow,S,T,num=1;
long long d[N];
void addedge(int u,int v,int f,int w)
{
Next[++num]=head[u],head[u]=num,adj[num]=v,cap[num]=f,cost[num]=w;
Next[++num]=head[v],head[v]=num,adj[num]=u,cap[num]=0,cost[num]=-w;
}
bool SPFA()
{
int i,l,r;
q[l=r=1]=S;
vis[S]=1;
memset(d,0x7f,sizeof(d));
d[S]=0;
while(l<=r)
{
for(i=head[q[l]];i;i=Next[i])
if(cap[i]&&d[adj[i]]>d[q[l]]+cost[i])
{
d[adj[i]]=d[q[l]]+cost[i];
if(!vis[adj[i]])
{
vis[adj[i]]=1;
q[++r]=adj[i];
}
}
vis[q[l]]=0;
++l;
}
return (d[T]<1<<30);
}
bool dfs(int i,int f)
{
if(i==T)
{
flow=f;
return true;
}
if(vis[i])
return false;
int j;
vis[i]=1;
for(j=now[i];j;now[i]=j=Next[j])
if(cap[j]&&d[adj[j]]==d[i]+cost[j]&&dfs(adj[j],min(f,cap[j])))
{
cap[j]-=flow;
cap[j^1]+=flow;
vis[i]=0;
return true;
}
vis[i]=0;
return false;
}
long long ans,ansf;
void minmax()
{
while(SPFA())
{
memcpy(now,head,sizeof(now));
while(dfs(S,inf))
ans+=flow*d[T],ansf+=flow;
}
}
多项式乘法
const int M=998244353;
const int N=100005,E=262144;
int R[N*4];
long long qpow(long long a,long long b)
{
long long ans=1;
while(b)
{
if(b&1)
ans=ans*a%M;
a=a*a%M;
b>>=1;
}
return ans;
}
long long wn[N*4],iwn[N*4];
void init()
{
int i;
iwn[E/2]=wn[E/2]=1;
long long s1=qpow(3,(M-1)/E);
long long s2=qpow(s1,M-2);
for(i=E/2+1;i<E;++i)
{
wn[i]=wn[i-1]*s1%M;
iwn[i]=iwn[i-1]*s2%M;
}
for(i=E/2-1;i;--i)
{
wn[i]=wn[i<<1];
iwn[i]=iwn[i<<1];
}
}
void NTT(long long *f,int lim,int op)
{
int i,j,k;
for(i=0;i<lim;++i)
{
R[i]=(R[i>>1]>>1)|(i&1?lim>>1:0);
if(R[i]<i)
swap(f[R[i]],f[i]);
}
for(i=1;i<lim;i<<=1)
for(j=0;j<lim;j+=(i<<1))
for(k=j;k<j+i;++k)
{
long long a=f[k],b=f[k+i];
long long w=(op==1?wn[k-j+i]:iwn[k-j+i]);
f[k]=(a+b*w)%M;
f[k+i]=(a-b*w)%M;
}
if(op==-1)
{
long long inv=qpow(lim,M-2);
for(i=0;i<lim;++i)
f[i]=f[i]*inv%M;
}
}
void mult(long long *a,int n,long long *b,int m)
{
if(n+m<=300)
{
long long t[n+m-1];
memset(t,0,sizeof(t));
for(int i=0;i<n;++i)
{
int j;
for(j=0;j+4<=m;j+=4)
{
t[i+j]=(t[i+j]+a[i]*b[j])%M;
t[i+j+1]=(t[i+j+1]+a[i]*b[j+1])%M;
t[i+j+2]=(t[i+j+2]+a[i]*b[j+2])%M;
t[i+j+3]=(t[i+j+3]+a[i]*b[j+3])%M;
}
for(;j<m;++j)
t[i+j]=(t[i+j]+a[i]*b[j])%M;
}
for(int i=0;i<n+m-1;++i)
a[i]=t[i];
return;
}
int lim=1;
while(lim<n+m)
lim<<=1;
for(int i=n;i<lim;++i)
a[i]=0;
for(int i=m;i<lim;++i)
b[i]=0;
NTT(a,lim,1);
NTT(b,lim,1);
for(int i=0;i<lim;++i)
a[i]=a[i]*b[i]%M;
NTT(a,lim,-1);
}
杜教筛
const int N=3000000;
int prime[N/5],vis[N+5],phi[N+5],mu[N+5],k,i;
long long sm[N+5],sp[N+5];
long long smu[1000005],sphi[1000005];
long long Smu(int m)
{
if(m<=N)
return sm[m];
int t=n/m;
if(smu[t])
return smu[t];
smu[t]=1;
for(int l=2,r;l<=m;l=r+1)
{
r=m/(m/l);
smu[t]-=(r-l+1)*Smu(m/l);
}
return smu[t];
}
long long Sphi(int m)
{
if(m<=N)
return sp[m];
int t=n/m;
if(sphi[t])
return sphi[t];
sphi[t]=1ll*m*(m+1)/2;
for(int l=2,r;l<=m;l=r+1)
{
r=m/(m/l);
sphi[t]-=(r-l+1)*Sphi(m/l);
}
return sphi[t];
}
void xxs()
{
int i,j;
mu[1]=phi[1]=1;
for(i=2;i<=N;++i)
{
if(!vis[i])
{
mu[i]=-1;
phi[i]=i-1;
vis[i]=1;
prime[++k]=i;
}
for(j=1;i*prime[j]<=N;++j)
{
int t=i*prime[j];
vis[t]=1;
if(i%prime[j]==0)
{
mu[t]=0;
phi[t]=phi[i]*prime[j];
break;
}
else
{
mu[t]=mu[i]*mu[prime[j]];
phi[t]=phi[i]*phi[prime[j]];
}
}
}
for(i=1;i<=N;++i)
{
sm[i]=sm[i-1]+mu[i];
sp[i]=sp[i-1]+phi[i];
}
}
Dijkstra
int k,head[N],Next[N*2],adj[N*2],leng[N*2],vis[N],n;
long long d[N];
struct str{
long long d;
int x;
};
bool operator <(str a,str b)
{
return a.d>b.d;
}
priority_queue<str> q;
void Push(int u,int v,int w)
{
Next[++k]=head[u];
head[u]=k;
adj[k]=v;
leng[k]=w;
}
void Dij(int S)
{
int i,j;
for(i=1;i<=n;++i)
{
d[i]=1000000000000000000ll;
vis[i]=0;
}
d[S]=0;
q.push((str){0,S});
while(!q.empty())
{
str x=q.top();
q.pop();
if(vis[x.x])
continue;
vis[x.x]=1;
for(j=head[x.x];j;j=Next[j])
if(d[adj[j]]>d[x.x]+leng[j])
{
d[adj[j]]=d[x.x]+leng[j];
q.push((str){d[adj[j]],adj[j]});
}
}
}
主席树（以单点加为例）
int ch[N*20][2],tree[N*20],k;
void pushup(int i)
{
tree[i]=tree[ch[i][0]]+tree[ch[i][1]];
}
void modify(int i,int l,int r,int x,int y)
{
if(l==r)
{
++k;
tree[k]=tree[i]+y;
return;
}
int mid=l+r>>1;
int u=++k;
if(mid>=x)
{
ch[u][1]=ch[i][1];
ch[u][0]=k+1;
modify(ch[i][0],l,mid,x,y);
pushup(u);
}
else
{
ch[u][0]=ch[i][0];
ch[u][1]=k+1;
modify(ch[i][1],mid+1,r,x,y);
pushup(u);
}
}
void Build(int i,int l,int r)
{
if(l==r)
return;
int mid=l+r>>1;
ch[i][0]=++k;
Build(ch[i][0],l,mid);
ch[i][1]=++k;
Build(ch[i][1],mid+1,r);
}
int Query(int i,int l,int r,int x)
{
if(l==r)
return tree[i];
int mid=l+r>>1;
if(mid>=x)
return Query(ch[i][0],l,mid,x);
else
return Query(ch[i][1],mid+1,r,x);
}
部分几何模板
struct str{
int x,y;
}q[500005];
struct pt{
double x,y;
};
pt operator -(pt a,pt b)
{
return (pt){a.x-b.x,a.y-b.y};
}
pt operator +(pt a,pt b)
{
return (pt){a.x+b.x,a.y+b.y};
}
double area(pt x,pt y)
{
return fabs((x.x*y.y-x.y*y.x)/2);
}
double dot(pt x,pt y)
{
return x.x*y.x+x.y*y.y;
}
double dis(pt x,pt y)
{
return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double D(pt x,pt y,pt a)//点到线段距离
{
if(dot(a-x,y-x)<0||dot(a-y,x-y)<0)
return min(dis(x,a),dis(y,a));
return area(x-a,y-a)*2/dis(x,y);
}
咕咕咕……