最近切题总是要套模板，而找模板太烦了，于是把模板整理一下贴出来

一、基本

1.读入优化★★★★

void read(int &x){
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}

void read(int &x){
	for(f=0,ch=getchar();ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=1;
	for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';if(f)x=-x;
}

2.输出优化☆

3.离散化★★☆ 小心使用

for(i=1;i<=n;i++)scanf("%d",&x[i]),v[i]=x[i];
sort(v+1,v+n+1);cnt=unique(v+1,v+n+1)-(v+1);
for(i=1;i<=n;i++)x[i]=lower_bound(v+1,v+cnt+1,x[i])-v;

4.二分★★★ 小心使用

for(l=1,r=n;l<=r;)if(ok(mid=l+r>>1))r=mid-1,ans=mid;else l=mid+1;

5.高精度★★☆

二、图论

1.邻接表★★★★★

void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}

void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}

2.SPFA★★★★ 注意标记v[x]=0

for(memset(d,63,sizeof(d)),d[q[t=1]=1]=0,v[1]=1;h^t;)for(i=fir[x=q[++h]],v[x]=0;i;i=ne[i])if(d[x]+va[i]<d[y=la[i]])if(d[y]=d[x]+va[i],!v[y])v[q[++t]=y]=1;

struct SPFA{
	int n,h,t,S,tot,q[N],d[N],fir[N],la[M],ne[M],va[M];bool v[N];
	void in(){tot=0;memset(d,63,sizeof d);CL(v);CL(fir);}
	void ins(int x,int y,int z){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;va[tot]=z;}
	void work(){
		int i,x,y;
		for(h=d[q[t=1]=S]=0;h^t;)
			for(i=fir[x=q[h=h%n+1]],v[x]=0;i;i=ne[i])
				if(d[x]+va[i]<d[y=la[i]])if(d[y]=d[x]+va[i],!v[y])v[q[t=t%n+1]=y]=1;
	}
}G;

3.Dijsktra+堆★★ 

struct Dijkstra{
	#define CL(a) memset(a,0,sizeof a)
	int h,t,S,tot,d[N],fir[N],la[M],ne[M],va[M],q[N];bool v[N];
	struct W{int x,z;bool operator<(W a)const{return a.z<z;}};priority_queue<W>Q;
	void in(){tot=0;CL(fir);CL(v);}
	void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
	void work(){
		int i,x,y;for(i=1;i<=T;i++)d[i]=1e9;
    	for(Q.push(W{1,d[h=S]=t=0});!Q.empty();)
			if(x=Q.top().x,Q.pop(),!v[x])for(v[x]=1,i=fir[x];i;i=ne[i])if(d[x]+va[i]<d[la[i]])Q.push(W{la[i],d[la[i]]=d[x]+va[i]});
    }
}G;

4.二分图★★

bool fd(int x,int z){
	for(int i=fir[x],y;i;i=ne[i])if(v[y=la[i]]!=z)if(v[y]=z,!lk[y]||fd(lk[y],z))return lk[y]=x,1;
	return 0;
}

5.KM☆

6.ISAP★★★★

struct MaxFlow{
	int S,T,tot,w,fir[N],cur[N],pre[N],d[N],nb[N],va[M],la[M],ne[M];
	#define CL(a) memset(a,0,sizeof a)
	void in(){tot=1;CL(fir);CL(d);CL(nb);CL(pre);}
	void ins(int x,int y,int fl){
    	la[++tot]=y;ne[tot]=fir[x];va[tot]=fl;fir[x]=tot;
    	la[++tot]=x;ne[tot]=fir[y];va[tot]=0;fir[y]=tot;
	}
	int FLOW(){
		int i,u,V,fl=0;
		for(i=1;i<=T;i++)cur[i]=fir[i];
    	for(u=S,nb[0]=T;d[S]<T;){
        	if(u==T){
           		for(V=1e9,i=S;i!=T;i=la[cur[i]])if(va[cur[i]]<V)V=va[cur[u=i]];
            	for(fl+=V,i=S;i!=T;i=la[cur[i]])va[cur[i]]-=V,va[cur[i]^1]+=V;
        	}
        	for(i=cur[u];i;i=ne[i])if(va[i]&&d[la[i]]+1==d[u])break;
        	if(i)cur[u]=i,pre[la[i]]=u,u=la[i];else{
            	if(0==--nb[d[u]])break;
            	for(i=cur[u]=fir[u],w=T;i;i=ne[i])if(d[la[i]]<w&&va[i])w=d[la[i]];
            	++nb[d[u]=w+1];if(u!=S)u=pre[u];
        	}
    	}
    	return fl;
	}
}G;

7.费用流★★★★

struct CostFlow{
	int S,T,h,t,tot,ans,fir[N],va[M],la[M],ne[M],q[N],d[N],fa[N],pre[N],co[M];bool v[N];
	#define CL(a) sizeof(a,0,sizeof a)
	void in(){CL(fir);CL(pre);CL(fa);tot=1;}
	void ins(int x,int y,int fl,int z){
    	la[++tot]=y;ne[tot]=fir[x];va[tot]=fl;co[tot]=z;fir[x]=tot;
    	la[++tot]=x;ne[tot]=fir[y];va[tot]=0;co[tot]=-z;fir[y]=tot;
	}
	bool spfa(){
		int i,x,y;
    	for(memset(d,63,sizeof d),CL(v),d[S]=h=0,v[q[t=1]=S]=1;h^t;)
        	for(i=fir[x=q[h=h%T+1]],v[x]=0;i;i=ne[i])
            	if(d[x]+co[i]<d[y=la[i]]&&va[i]){
                	d[y]=d[fa[y]=x]+co[pre[y]=i];
                	if(!v[y])v[q[t=t%T+1]=y]=1;
            	}
    	return d[T]<1e9;
	}
	void end(){
		int i,p=1e9;
		for(i=T;i!=S;i=fa[i])p=min(p,va[pre[i]]);
		for(i=T;i!=S;i=fa[i])va[pre[i]]-=p,va[pre[i]^1]+=p,ans+=p*co[pre[i]];
	}
	int cal(){for(ans=0;spfa();end());return ans;}
}G;

8.tarjan★★☆

void tj(int x){
    low[x]=dfn[x]=++id;is[x]=1;q[++t]=x;int y,i,o=0;
    for(i=fir[x];i;i=ne[i])if(!dfn[y=la[i]])tj(y),low[x]=min(low[x],low[y]);else if(is[y])low[x]=min(low[x],dfn[y]);
    if(dfn[x]==low[x])for(cnt++;o!=x;o=q[t--],bl[o]=cnt,is[o]=0);
}

9.双连通分量★

10.Dorminator Tree★

11.LCA★★★☆

int lca(int x,int y){
    if(d[x]<d[y])swap(x,y);int t=d[x]-d[y],i;
    for(i=0;i<=17;i++)if(t>>i&1)x=F[x][i];
    for(i=17;i>=0;i--)if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];
    return x==y?x:F[x][0];
}

12.树分治★★☆

int dis(int x,int y){
	int w=d[x]+d[y],t;x=pos[x];y=pos[y];
	if(x>y)swap(x,y);t=gl[y-x+1];
	return w-2*min(F[x][t],F[y-(1<<t)+1][t]);
}
void dfs(int x,int fa){
	F[pos[x]=++mt][0]=d[x];
	for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)d[la[i]]=d[x]+va[i],dfs(la[i],x),F[++mt][0]=d[x];
}
void dsz(int x,int fa){
	sz[x]=1;mv[x]=0;
	for(int i=fir[x],y;i;i=ne[i])if(!vis[y=la[i]]&&y!=fa)dsz(y,x),sz[x]+=sz[y],mv[x]=max(mv[x],sz[y]);
}
void drt(int zs,int x,int fa,int&rt){
	mv[x]=max(mv[x],sz[zs]-sz[x]);if(mv[x]<mv[rt]||!rt)rt=x;
	for(int i=fir[x];i;i=ne[i])if(!vis[y=la[i]]&&y!=fa)drt(zs,y,x,rt);
}
int fz(int x){
	int i,p,rt=0;dsz(x,0);drt(x,x,0,rt);vis[rt]=1;
	for(i=fir[rt];i;i=ne[i])if(!vis[la[i]])Ins(rt,la[i],fz(la[i]));
	return rt;
}

13.基环树找环★★

void fcur(int x){
	v[x]=++sz;
	for(int i=fir[x];i;i=ne[i]){
		int y=la[i];
		if(y==fa[x])continue;
		if(v[y]){
			if(v[y]<v[x])continue;
			cir[++num]=x;c[x]=1;
			for(;x!=y;y=fa[y])c[y]=1,cir[++num]=y;
		}else fa[y]=x,fcur(y);
	}
}

14.最小树形图★

for(;;){
		for(n=cnt,rt=id[rt],i=1;i<=n;i++)low[i]=1e9;
		for(i=1;i<=m;i++)if(X[i]!=Y[i]&&Z[i]<low[Y[i]])low[Y[i]]=Z[i],pre[Y[i]]=X[i];
		for(low[rt]=0,cnt=0,i=1;i<=n;i++)id[i]=v[i]=0;
		for(i=1;i<=n;i++){
			for(ans+=low[x=i];v[x]!=i&&!id[x]&&x!=rt;x=pre[x])v[x]=i;
			if(x!=rt&&!id[x])for(id[x]=++cnt,y=pre[x];x!=y;y=pre[y])id[y]=cnt;
		}
		if(!cnt)break;
		for(i=1;i<=n;i++)if(!id[i])id[i]=++cnt;
		for(i=1;i<=m;i++){
			y=Y[i];X[i]=id[X[i]];Y[i]=id[Y[i]];
			if(X[i]!=Y[i])Z[i]-=low[y];
		}
	}

三、数据结构

1.并查集★★★★ 要路径压缩！

int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}

2.可并堆★★★★ 返回x

int merge(int x,int y){
    if(!x||!y)return x+y;
    if(a[x]>a[y])swap(x,y);
    c[x][1]=merge(c[x][1],y);
    swap(c[x][0],c[x][1]);
    return x;
}

3.树状数组★★★★ 二维注意

void add(int x,int z){for(;x<=n;x+=x&-x)c[x]+=z;}
int query(int x){for(sum=0;x;x-=x&-x)sum+=c[x];return sum;}

4.线段树★★★★

void ins(int k,int l,int r,int x,int y,int z){
    if(t[k].lz)t[k<<1].v+=t[k].lz,t[k<<1|1].v+=t[k].lz,t[k<<1].lz+=t[k].lz,t[k<<1|1].lz+=t[k].lz,t[k].lz=0;
    if(x<=l&&r<=y){t[k].lz+=z,t[k].v+=z;return;}
    int mid=l+r>>1;
    if(x<=mid)ins(k<<1,l,mid,x,y,z);
    if(y>mid)ins(k<<1|1,mid+1,r,x,y,z);
    t[k].v=max(t[k<<1].v,t[k<<1|1].v);
}

5.fhqtreap★

int merge(int x,int y){ 
    if(!x||!y)return x?x:y;int z=0;
    if(ran[x]>ran[y])pd(y),z=y,ls[z]=merge(x,ls[y]);else pd(x),z=x,rs[z]=merge(rs[x],y);
    ps(z);return z;
}
void split(int x,int &y,int &z,int k){
    y=z=0;if(!x)return;pd(x);
    if(sz[ls[x]]>=k)z=x,split(ls[x],y,ls[z],k),ps(z);
    else y=x,split(rs[x],rs[y],z,k-sz[ls[x]]-1),ps(y);
}

6.Splay★★★☆

void R(int x){
    int y=fa[x],k=(c[y][0]==x);
    c[y][!k]=c[x][k];fa[c[x][k]]=y;
    fa[x]=fa[y];c[fa[y]][c[fa[y]][1]==y]=x;
    c[x][k]=y;fa[y]=x;ps(y);
}
void sy(int x,int &rt){for(;y=fa[x];R(x))if(fa[y])R((x==c[y][0])==(y==c[fa[y]][0])?y:x);ps(x);rt=x;}

7.主席树★★☆

void ins(int l,int r,int x,int &y,int k){
	sz[y=++zs]=sz[x]+1;if(l==r)return;
	ls[y]=ls[x];rs[y]=rs[x];int mid=(l+r)>>1;
	a[k]<=hash[mid]?ins(l,mid,ls[x],ls[y],k:ins(mid+1,r,rs[x],rs[y],k);
}
int ask(int l,int r,int x,int y,int k){
	if(l==r)return l;int mid=(l+r)>>1;
	if(sz[ls[y]]-sz[ls[x]]>=k)return ask(l,mid,ls[x],ls[y],k); 
	else return ask(mid+1,r,rs[x],rs[y],k-(sz[ls[y]]-sz[ls[x]]));
}

8.树链剖分★★★☆

void dfs(int x){
    sz[x]=1;int i,y;for(i=fir[x];i;i=ne[i])if(fa[x]!=la[i]){
		fa[y=la[i]]=x,h[y]=h[x]+1,dfs(y),sz[x]+=sz[y];
		if(sz[y]>sz[hs[x]])hs[x]=y;
	}
}
void dfs2(int x,int f){
	pos[x]=++ps;bl[x]=f;if(hs[x])dfs2(hs[x],f);
	for(int i=fir[x];i;i=ne[i])if(fa[x]!=la[i]&&la[i]!=hs[x])dfs2(la[i],la[i]);
}
void queryin(int x,int y){
    for(;bl[x]!=bl[y];x=fa[bl[x]]){
        if(h[bl[x]]<h[bl[y]])swap(x,y);
        add(pos[bl[x]],1);add(pos[x]+1,-1);
    }
    if(pos[x]>pos[y])swap(x,y);
    add(pos[x],1);add(pos[y]+1,-1);
}

9.LCT★★★

bool ir(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
void rev(int x){swap(c[x][0],c[x][1]);rv[x]^=1;}
void pd(int x){if(rv[x])rev(c[x][0]),rev(c[x][1]),rv[x]=0;}
void R(int x){
	int y=fa[x],k=c[y][0]==x;
	fa[c[y][!k]=c[x][k]]=y;
	fa[x]=fa[y];if(!ir(y))c[fa[y]][c[fa[y]][1]==y]=x;
	fa[c[x][k]=y]=x;ps(y);
}
void dw(int x){if(!ir(x))dw(fa[x]);pd(x);}
void sy(int x){for(dw(x);!ir(x);R(x))if(!ir(fa[x]))R(c[fa[x]][0]==x^c[fa[fa[x]]][0]==fa[x]?x:fa[x]);ps(x);}
int fd(int x){for(;fa[x];x=fa[x]);return x;}
void acs(int x){for(o=0;x;c[x][1]=o,ps(x),o=x,x=fa[x])sy(x);}
void mrt(int x){acs(x);sy(x);rev(x);}
void lk(int x,int y){mrt(x);fa[x]=y;}
void ct(int x,int y){mrt(x);acs(y);sy(y);c[y][0]=fa[x]=0;}

10.K-D树★☆

四、字符串

1.KMP★★

for(scanf("%s",s+1),n=strlen(s+1),i=2;i<=n;i++){
	for(;k&&s[k+1]^s[i];k=p[k]);
	if(s[k+1]==s[i])k++;
        p[i]=k;
}

2.Manacher★★

scanf("%s",s);n=strlen(s);ma[l++]='$';ma[l++]='#';
for(i=0;i<n;i++)ma[l++]=s[i],ma[l++]='#';
for(i=0;i<l;i++){
	r[i]=mx>i?min(r[2*p-i],mx-i):1;
	for(;ma[i+r[i]]==ma[i-r[i]];r[i]++);
	if(i+r[i]>mx)mx=i+r[i],p=i;
}

3.Tire★★

for(scanf("%s",s),u=i=0;i<n;u=c[u][o],i++)if(!c[u][o=s[i]-'a'])c[u][o]=++id;

4.可持久化Tire★

void ins(int x,int &y,int z,int d){
	int p=(z>>d)&1;s[y=++tot]=s[x]+1;if(d<0)return;
	c[y][p^1]=c[x][p^1];ins(c[x][p],c[y][p],z,d-1);
}
int qu(int x,int y,int z,int d){
	if(d<0)return 0;int p=(z>>d)&1;
	if(s[c[y][p^1]]-s[c[x][p^1]])return (1<<d)+qu(c[x][p^1],c[y][p^1],z,d-1);else return qu(c[x][p],c[y][p],z,d-1);
}

5.AC自动机★★☆

for(q[t=1]=1;h<t;)
	for(x=q[++h],i=0;i<2;i++){
		y=son[x][i];if(!y){son[x][i]=son[fail[x]][i];continue;}
		for(k=fail[x];!son[k][i];k=fail[k]);
		fail[y]=son[k][i];dg[y]|=dg[fail[y]];
		q[++t]=y;
	}

6.SA★

7.SAM★★★☆

void add(int x){
    for(p=np,st[np=++cnt]=st[p]+1;p&&!c[p][x];p=F[p])c[p][x]=np;to[np]=i;pos[i]=np;
    if(!p)F[np]=1;else if(st[p]+1==st[q=c[p][x]])F[np]=q;else for(st[nq=++cnt]=st[p]+1,memcpy(c[nq],c[q],sizeof c[q]),F[nq]=F[q],F[q]=F[np]=nq;p&&c[p][x]==q;p=F[p])c[p][x]=nq;
}

8.PAM★★

void add(int c,int n){
    while(s[n-len[p]-1]!=s[n])p=fa[p];
    if(!ch[p][c]){
        int now=++cnt,k=fa[p];
        len[now]=len[p]+2;
        while(s[n-len[k]-1]!=s[n])k=fa[k];
        fa[now]=ch[k][c];ch[p][c]=now;
    }
    p=ch[p][c];sz[p]++;
}
cnt=1;fa[0]=fa[1]=1;len[1]=-1;

五、数论&计算几何

1.扩展欧几里得★★★★

void exgcd(LL a,LL b,LL &x,LL &y){if(!b){x=1;y=0;return;}exgcd(b,a%b,y,x);y-=x*(a/b);}

2.快速幂★★★★

LL pow(LL a,LL b,LL p){for(sum=1,a%=p;b;a=a*a%p,b>>=1)if(b&1)sum=sum*a%p;return sum;}

3.BSGS★☆

LL bsgs(LL a,LL b,LL p){
    LL m=ceil(sqrt(p)),v=pow(pow(a,m,p),p-2,p),i,e=1;map<LL,LL>mp;mp[1]=0;
    for(i=1;i<m;i++)if(!mp.count(e=e*a%p))mp[e]=i;
    for(i=0;i<m;b=b*v%p,i++)if(mp.count(b))return i*m+mp[b];
    return -2;
}

4.线性筛★★★★

for(i=2;i<=n;i++){
        if(!f[i]){
            prime[++p]=i;
            cnt[i]=1;
            phi[i]=i-1;
            u[i]=-1;
        }
        for(j=1;j<=p&&i*prime[j]<=n;j++){
            f[i*prime[j]]=1;
            cnt[i*prime[j]]=cnt[i]+1;
            if(i%prime[j]==0){
            	u[prime[j]*i]=0;
		phi[i*prime[j]]=phi[i]*prime[j];
		break;
	    }
		phi[i*prime[j]]=phi[i]*(prime[j]-1);
	    u[prime[j]*i]=-u[i];
        }
}

for(i=2;i<=n;i++){
        if(!f[i])p[++t]=i;
        for(j=1;j<=t&&i*p[j]<=n;j++){
            f[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
 }

5.O(n)求逆元★★

for(inv[1]=1,i=2;i<=m+1;i++)inv[i]=(P-P/i)*inv[P%i]%P;

6.O(lgn)求欧拉函数★★

LL phi(LL n){
    LL i,re=n;
    for(i=2;i*i<=n;i++)if(n%i==0)for(re=re/i*(i-1);n%i==0;)n/=i;
    if(n>1)re=re/n*(n-1);
    return re%MOD;
}

7.Millar-Rabin★★

8.高斯消元★★★

for(i=1;i<=n;i++){
		for(t=a[i][i],j=1;j<=n+1;j++)a[i][j]/=t;
		for(j=1;j<=n;j++)if(i!=j)for(t=a[j][i],k=1;k<=n+1;k++)a[j][k]-=t*a[i][k];
	}

9.线性基★★☆

for(i=n;i;i--){
        int t=a[i];
        for(j=30;j>=0;j--)if((a[i]>>j)&1){
            if(!ins[j]){ins[j]=a[i];break;}
            else a[i]^=ins[j];
        }
        if(a[i])ans+=t;
    }

10.矩阵乘法★★★☆

JZ cheng(JZ a,JZ b){
	JZ c;memset(c.m,0,sizeof c.m);
	c.x=a.x;c.y=b.y;
	for(int i=1;i<=a.x;i++)
		for(int j=1;j<=b.y;j++)
			for(int k=1;k<=a.y;k++)
				c.m[i][j]=(c.m[i][j]+(a.m[i][k]%MOD)*(b.m[k][j]%MOD))%MOD;
	return c;
}

11.组合数递推★★★☆

for(i=0;i<=n;i++)for(c[i][0]=1,j=1;j<=n;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%M;

12.卢卡斯及扩展★★☆

LL lucas(LL n,LL m,LL p){return !m?1:lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;}

LL pow(LL a,LL b,LL p){LL sum=1;for(a%=p;b;a=a*a%p,b>>=1)if(b&1)sum=sum*a%p;return sum;}
U fac(LL k,LL n){
	if(!n)return U{1,0};
	LL x=n/p[k],y=n/P[k],ans=1;LL i;
	if(y){
		for(i=2;i<P[k];i++)if(i%p[k])ans=ans*(i%P[k])%P[k];
	    ans=pow(ans,y,P[k]);
	}
	for(i=y*P[k];i<=n;i++)if(i%p[k])ans=ans*(i%M)%M;
	U z=fac(k,x);return U{ans*z.x%M,x+z.z};
}
LL get(LL k,LL n){
	U a=fac(k,n*2),b=fac(k,n),c=fac(k,n+1);
	return pow(p[k],a.z-b.z-c.z,P[k])*a.x%P[k]*pow(b.x,P[k]/p[k]*(p[k]-1)-1,P[k])%P[k]*pow(c.x,P[k]/p[k]*(p[k]-1)-1,P[k])%P[k];
}
void C(LL n){for(LL i=1;i<=l;i++)w=M/P[i],ans=(ans+w*get(i,n)%M*pow(w,P[i]/p[i]*(p[i]-1)-1,P[i]))%M;}

13.CRT★☆

LL CRT(){
    for(ans=0,sum=M-1,i=0;i<4;i++){
        d=sum/w[i];
        exgcd(d,w[i],x,y);
        ans=(ans+d*x*a[i])%sum;
    }
    while(ans<=0)ans+=sum;
    return ans;
}

14.FFT★★☆

typedef complex<double>C;
void FFT(C *a,int f){
	int i,j,k,p;for(i=0;i<N;i++)if(g[i]>i)swap(a[i],a[g[i]]);
	for(i=1;i<N;i<<=1){
		C e(cos(pi/i),f*sin(pi/i));
		for(j=0;j<N;j+=i<<1){
			C w(1,0);for(k=0;k<i;k++,w*=e){
				C x=a[j+k],y=w*a[j+k+i];
				a[j+k]=x+y;a[j+k+i]=x-y;
			}
		}
	}
}
for(i=1;i<N;i++)g[i]=g[i>>1]>>1|((i&1)<<17);

15.NTT%998244353★★☆

void Init(int n){
    int t,i;for(t=0;n>>t+2;t++);
    for(i=1;i<n;i++)g[i]=g[i>>1]>>1|((i&1)<<t);
}
void NTT(LL A[N],int f,int n){
    int i,j,k,b=0;
    Init(n);
    for(i=0;i<n;i++)if(g[i]>i)swap(A[i],A[g[i]]);
    for(i=1;i<n;i<<=1){
        b++;
        w=pow(s,(1<<23-b)*119);
        if(f<0)w=pow(w,M-2);
        for(j=0;j<n;j+=i<<1){
            w0=1;
            for(k=0;k<i;k++){
                x=A[j+k];
                A[j+k]=(x+A[j+k+i]*w0)%M;
                A[j+k+i]=(x-A[j+k+i]*w0)%M;
                if(A[j+k+i]<0)A[j+k+i]+=M;
                w0=w0*w%M;
            }
        }
    }
    if(f<0){
        LL v=pow(n,M-2);
        for(i=0;i<n;i++)A[i]=A[i]*v%M;
    }
}

16.多项式求逆★☆

17.计算几何★★☆

double dis(P a,P b){return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);}
double multi(P a,P b,P c){return(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
P operator-(P a,P b){return P{a.x-b.x,a.y-b.y};}
double operator*(P a,P b){return a.x*b.y-a.y*b.x;}
bool operator<(P a,P b){
	double t=(a-p[1])*(b-p[1]);
	return t<0||(t==0&&dis(a,p[1])<dis(b,p[1]));
}
int main(){
	scanf("%d",&n);u=1;
	for(i=1;i<=n;i++){
		scanf("%lf%lf",&p[i].x,&p[i].y);
		if(p[i].x<p[u].x||p[i].x==p[u].x&&p[i].y<p[u].y)u=i;
	}
	swap(p[1],p[u]);sort(p+2,p+n+1);q[1]=p[1];q[2]=p[2];top=2;
	for(i=3;i<=n;i++){
		while(top>1&&(p[i]-q[top-1])*(q[top]-q[top-1])<=0)top--;
		q[++top]=p[i];
	}
}

bool cal(int n,int x,int y){
	int i,j,w=0;
	for(i=0,j=n-1;i<n;j=i++)
if(((G[i].y>y)^(G[j].y>y))&&(x<(double)(G[j].x-G[i].x)*(y-G[i].y)/(G[j].y-G[i].y)+G[i].x))w^=1;
	return w;
}

P get(P z,P x,P y){//z为点，x和y为线段两端点，这里的*是点积
	P o=y-x;if((z-x)*o<=0)return x;if((z-y)*(x-y)<=0)return y;
	double k=((z-x)*o)/(o*o);return x+o*k;
}

18.半平面交★

19.单纯形★★☆

• 相关文章推荐
• 全局相关文章