模板
最近切题总是要套模板，而找模板太烦了，于是把模板整理一下贴出来
一、基本
1.读入优化★★★★
1 2 3 4 | 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';} |
1 2 3 4 | 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.离散化★★☆ 小心使用
1 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.二分★★★ 小心使用
1 | for(l=1,r=n;l<=r;)if(ok(mid=l+r>>1))r=mid-1,ans=mid;else l=mid+1; |
5.高精度★★☆
二、图论
1.邻接表★★★★★
1 | void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;} |
1 | 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
1 | 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; |
1 2 3 4 5 6 7 8 9 10 11 | 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+堆★★
1 2 3 4 5 6 7 8 9 10 11 12 | 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.二分图★★
1 2 3 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★★★★
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | 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.费用流★★★★
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | 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★★☆
1 2 3 4 5 | 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★★★☆
1 2 3 4 5 6 | 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.树分治★★☆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | 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.基环树找环★★
1 2 3 4 5 6 7 8 9 10 11 12 | 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.最小树形图★
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | 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.并查集★★★★ 要路径压缩！
1 | int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);} |
2.可并堆★★★★ 返回x
1 2 3 4 5 6 7 | 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.树状数组★★★★ 二维注意
1 2 | 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.线段树★★★★
1 2 3 4 5 6 7 8 | 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★
1 2 3 4 5 6 7 8 9 10 | 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★★★☆
1 2 3 4 5 6 7 | 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.主席树★★☆
1 2 3 4 5 6 7 8 9 10 | 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.树链剖分★★★☆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | 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★★★
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | 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★★
1 2 3 4 5 | 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★★
1 2 3 4 5 6 7 | 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★★
1 | 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★
1 2 3 4 5 6 7 8 | 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自动机★★☆
1 2 3 4 5 6 7 | 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★★★☆
1 2 3 4 | 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★★
1 2 3 4 5 6 7 8 9 10 11 | 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.扩展欧几里得★★★★
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.快速幂★★★★
1 | 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★☆
1 2 3 4 5 6 | 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.线性筛★★★★
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | 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]; }} |
1 2 3 4 5 6 7 | 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)求逆元★★
1 | for(inv[1]=1,i=2;i<=m+1;i++)inv[i]=(P-P/i)*inv[P%i]%P; |
6.O(lgn)求欧拉函数★★
1 2 3 4 5 6 | 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.高斯消元★★★
1 2 3 4 | 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.线性基★★☆
1 2 3 4 5 6 7 8 | 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.矩阵乘法★★★☆
1 2 3 4 5 6 7 8 9 | 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.组合数递推★★★☆
1 | 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.卢卡斯及扩展★★☆
1 | LL lucas(LL n,LL m,LL p){return !m?1:lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;} |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | 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★☆
1 2 3 4 5 6 7 8 9 | 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★★☆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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★★☆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | 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.计算几何★★☆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | 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]; }} |
1 2 3 4 5 6 | 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;} |
1 2 3 4 | 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.单纯形★★☆
2022年9月19日 00:29
Every student of class 10 can learn Hindi easily and this is or National language, Hindi is the most important language for every student, AP SSC Hindi Model Paper and the Board of Secondary Education, Andhra Pradesh (BSEAP) class 10th of SSC students also can download the AP 10th Hindi Model Paper 2023 Pdf with Solved question paper in chapter wise for all lessons of the course as AP SSC Hindi Model Paper 2023. Every student of class 10 can learn Hindi easily and this is or National language, Hindi is the most important language for every student.