模板

FWT

void fwtor(int sz[132000],int n)
{
    for(int i=2;i<=n;i=(i<<1))
    {
        for(int j=0;j>1);k++)
                sz[j+(i>>1)+k]=(sz[j+(i>>1)+k]+sz[j+k])%md;
        }
    }
}
void ifwtor(int sz[132000],int n)
{
    for(int i=2;i<=n;i=(i<<1))
    {
        for(int j=0;j>1);k++)
                sz[j+(i>>1)+k]=(sz[j+(i>>1)+k]-sz[j+k]+md)%md;
        }
    }
}
void fwtand(int sz[132000],int n)
{
    for(int i=2;i<=n;i=(i<<1))
    {
        for(int j=0;j>1);k++)
                sz[j+k]=(sz[j+k]+sz[j+(i>>1)+k])%md;
        }
    }
}
void ifwtand(int sz[132000],int n)
{
    for(int i=2;i<=n;i=(i<<1))
    {
        for(int j=0;j>1);k++)
                sz[j+k]=(sz[j+k]-sz[j+(i>>1)+k]+md)%md;
        }
    }
}
void fwtxor(int sz[132000],int n)
{
    for(int i=2;i<=n;i=(i<<1))
    {
        for(int j=0;j>1);k++)
            {
                int a=sz[j+k],b=sz[j+(i>>1)+k];
                sz[j+k]=(a+b)%md;
                sz[j+(i>>1)+k]=(a-b+md)%md;
            }
        }
    }
}
void ifwtxor(int sz[132000],int n)
{
    for(int i=2;i<=n;i=(i<<1))
    {
        for(int j=0;j>1);k++)
            {
                int a=sz[j+k],b=sz[j+(i>>1)+k];
                sz[j+k]=1ll*(a+b)*inv%md;
                sz[j+(i>>1)+k]=1ll*(a-b+md)*inv%md;
            }
        }
    }
}

KD树

void update(int x)
{
    if(bk[x])
        zx[x]=inf,wz[x]=-1;
    else
        zx[x]=qz[x],wz[x]=x;
    if(cl[x]!=0&&wz[cl[x]]!=-1&&zx[cl[x]]<=zx[x])
        zx[x]=zx[cl[x]],wz[x]=wz[cl[x]];
    if(cr[x]!=0&&wz[cr[x]]!=-1&&zx[cr[x]]<=zx[x])
        zx[x]=zx[cr[x]],wz[x]=wz[cr[x]];
}
void pur(int x,int y)
{
    if(ld[x]!=-1&&y>=ld[x])
        return;
    ld[x]=y;
    if(qz[x]>y)qz[x]=y;
    if(zx[x]>y)zx[x]=y;
}
void pushdown(int x)
{
    if(ld[x]==-1)return;
    if(cl[x]!=0)pur(cl[x],ld[x]);
    if(cr[x]!=0)pur(cr[x],ld[x]);
    ld[x]=-1;
}
void clean(int x)
{
    if(fa[x]!=0)
        clean(fa[x]);
    pushdown(x);
}
void del(int x)
{
    clean(x);
    bk[x]=true;
    for(int i=x;i!=0;i=fa[i])
        update(i);
}
int buix(SPx sz[70010],int l,int r);
int buiy(SPx sz[70010],int l,int r);
void pushup(int rt)
{
    if(cl[rt]!=0)
    {
        lx[rt]=min(lx[rt],lx[cl[rt]]);rx[rt]=max(rx[rt],rx[cl[rt]]);
        ly[rt]=min(ly[rt],ly[cl[rt]]);ry[rt]=max(ry[rt],ry[cl[rt]]);
        fa[cl[rt]]=rt;
    }
    if(cr[rt]!=0)
    {
        lx[rt]=min(lx[rt],lx[cr[rt]]);rx[rt]=max(rx[rt],rx[cr[rt]]);
        ly[rt]=min(ly[rt],ly[cr[rt]]);ry[rt]=max(ry[rt],ry[cr[rt]]);
        fa[cr[rt]]=rt;
    }
}
bool fugai(int Lx,int Rx,int Ly,int Ry,int lx,int rx,int ly,int ry)
{
    return Lx<=lx&&rx<=Rx&&Ly<=ly&&ry<=Ry;
}
bool fenli(int Lx,int Rx,int Ly,int Ry,int lx,int rx,int ly,int ry)
{
    return Lx>rx||lx>Rx||Ly>ry||ly>Ry;
}
int X[70010],Y[70010];
int buix(SPx sz[70010],int l,int r)
{
    if(l>=r)return 0;
    qsort(sz+l,r-l,sizeof(SPx),cmpx);
    int m=(l+r-1)>>1,rt=sz[m].i;
    lx[rt]=rx[rt]=sz[m].x;
    ly[rt]=ry[rt]=sz[m].y;
    cl[rt]=buiy(sz,l,m);
    cr[rt]=buiy(sz,m+1,r);
    pushup(rt);
    return rt;
}
int buiy(SPx sz[70010],int l,int r)
{
    if(l>=r)return 0;
    qsort(sz+l,r-l,sizeof(SPx),cmpy);
    int m=(l+r-1)>>1,rt=sz[m].i;
    lx[rt]=rx[rt]=sz[m].x;
    ly[rt]=ry[rt]=sz[m].y;
    cl[rt]=buix(sz,l,m);
    cr[rt]=buix(sz,m+1,r);
    pushup(rt);
    return rt;
}
void songc(int i,int Lx,int Rx,int Ly,int Ry,int z)
{
    if(ld[i]!=-1&&z>ld[i])
        return;
    if(fenli(Lx,Rx,Ly,Ry,lx[i],rx[i],ly[i],ry[i]))
        return;
    if(fugai(Lx,Rx,Ly,Ry,lx[i],rx[i],ly[i],ry[i]))
    {
        pur(i,z);
        return;
    }
    pushdown(i);
    if(fugai(Lx,Rx,Ly,Ry,X[i],X[i],Y[i],Y[i]))
    {
        if(qz[i]>z)
            qz[i]=z;
        update(i);
    }
    if(cl[i]!=0)
        songc(cl[i],Lx,Rx,Ly,Ry,z);
    if(cr[i]!=0)
        songc(cr[i],Lx,Rx,Ly,Ry,z);
    update(i);
}

欧拉回路

void dfs(int u)
{
	for(int &i=fr[u];i!=-1;i=ne[i])
	{
		if(bk[i/2])
			continue;
		bk[i/2]=true;
		int a=u,b=v[i];
		dfs(v[i]);
		lu[ls]=a;lv[ls++]=b;
		if(i==-1)break;
	}
}

线性基

    for(int i=0;i<=50;i++)
        zt[i]=-1;
    for(int i=0;i=0;j--)
        {
            if(t&(1ll<=0;i--)
    {
        if(zt[i]!=-1&&(jg^zt[i])>jg)
            jg=(jg^zt[i]);
    }
    printf("%lld",jg);

强连通分量

int dfn[MN],low[MN],tm=0,scc[MN],ss=0,st[MN],tp=0;
void tarjan(int u)
{
	dfn[u]=low[u]=++tm;
	st[tp++]=u;
	for(int i=fr[u];i!=-1;i=ne[i])
	{
		int t=v[i];
		if(!dfn[t])
		{
			tarjan(t);
			low[u]=min(low[u],low[t]);
		}
		else if(!scc[t])
			low[u]=min(low[u],dfn[t]);
	}
	if(dfn[u]==low[u])
	{
		ss+=1;
		while(1)
		{
			scc[st[tp-1]]=ss;
			tp-=1;
			if(st[tp]==u)break;
		}
	}
}

FFT

#include 
#include 
struct cp
{
	double a,b;
	cp(){}
	cp(double A,double B)
	{
		a=A;b=B;
	}
};
cp operator+(cp x,cp y)
{
	return cp(x.a+y.a,x.b+y.b);
}
cp operator-(cp x,cp y)
{
	return cp(x.a-y.a,x.b-y.b);
}
cp operator*(cp x,cp y)
{
	return cp(x.a*y.a-x.b*y.b,x.a*y.b+x.b*y.a);
}
void FFT(cp sz[140000],int n,int lx)
{
	double pi=acos(-1.0);
	for(int i=0,t=0;it)
		{
			cp o=sz[i];
			sz[i]=sz[t];
			sz[t]=o;
		}
		for(int j=(n>>1);(t^=j)>1));
	}
	for(int h=2;h<=n;h=(h<<1))
	{
		cp wn(cos(2*pi*lx/h),sin(2*pi*lx/h));
		for(int i=0;i>1);j++,w=w*wn)
			{
				t=w*sz[j+(h>>1)];
				sz[j+(h>>1)]=sz[j]-t;
				sz[j]=sz[j]+t;
			}
		}
	}
	if(lx==-1)
	{
		for(int i=0;i=n)
		{
			n=i;
			break;
		}
	}
	FFT(sz,n,1);
	FFT(sz,n,-1);
	for(int i=0;i

	void man()
	{
		int ma=-1,wz=-1;
		for(int i=0;ima)
					cd[i]=ma-i+1;
			}
			while(i-cd[i]>=0&&i+cd[i]ma)
			{
				ma=i+cd[i]-1;
				wz=i;
			}
		}
	}

bool dfs(int u)
{
    vg[u]=true;
    for(int i=0;iexg[i])
                exg[i]=sz[i][j];
        }
    }//初始化
    for(int i=0;i