作者：everlasting
模板：NTT
|
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#include<bits/stdc++.h> #define maxn 60060*3 #define ll long long #define mod 998244353 #define g 3 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } int n,m; int rev[maxn],c[maxn]; int a[maxn],b[maxn]; inline void init(){ n=rd(); static char ch[maxn]; scanf("%s",ch); for(int i=0; i<n; i++)a[i]=ch[n-i-1]-'0'; scanf("%s",ch); for(int i=0; i<n; i++)b[i]=ch[n-i-1]-'0'; } inline int ksm(int A,int B){ int ret=1; while(B){ if(B%2)ret=(ll)A*ret%mod; A=(ll)A*A%mod; B/=2; } return ret; } void ntt(int *A,int flag){ int bit=0; while((1<<bit)<n)bit++; for(int i=0; i<n; i++){ rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1)); if(i<rev[i])swap(A[i],A[rev[i]]); } for(int len=1; len<n; len*=2){ int tmp=ksm(g,(mod-1)/(len*2)); if(flag==-1)tmp=ksm(tmp,mod-2); for(int i=0; i<n; i+=len*2){ int w=1; for(int j=0; j<len; j++,w=(ll)w*tmp%mod){ int x=A[i+j]; int y=(ll)w*A[i+j+len]%mod; A[i+j]=(x+y)%mod; A[i+j+len]=(x-y+mod)%mod; } } } int inv=ksm(n,mod-2); if(flag==-1)for(int i=0; i<n; i++)A[i]=(ll)A[i]*inv%mod; } inline void work(){ m=n*2; for(n=1; n<m; n*=2); ntt(a,1); ntt(b,1); for(int i=0; i<n; i++)a[i]=(ll)a[i]*b[i]%mod; ntt(a,-1); for(int i=0; i<m; i++)c[i]=a[i]; while(c[m-1]==0)m--; for(int i=0; i<m; i++){ if(c[i]>=10){ c[i+1]+=c[i]/10; c[i]%=10; if(i==m-1)m++; } } for(int i=m-1; i>=0; i--)printf("%d",c[i]); puts(""); } int main(){ init(); work(); return 0; } |
模板：FFT
|
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include<bits/stdc++.h> #define db double #define maxn 60060*3 #define cp complex<db> #define pi acos(-1) using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } int n,m; int rev[maxn],c[maxn]; cp a[maxn],b[maxn]; inline void init(){ n=rd(); static char ch[maxn]; scanf("%s",ch); for(int i=0; i<n; i++)a[i]=ch[n-i-1]-'0'; scanf("%s",ch); for(int i=0; i<n; i++)b[i]=ch[n-i-1]-'0'; } void fft(cp *A,int flag){ int bit=0; while((1<<bit)<n)bit++; for(int i=0; i<n; i++){ rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1)); if(i<rev[i])swap(A[i],A[rev[i]]); } for(int len=1; len<n; len*=2){ cp tmp(cos(pi/len),flag*sin(pi/len)); for(int i=0; i<n; i+=len*2){ cp w(1,0); for(int j=0; j<len; j++,w*=tmp){ cp x=A[i+j]; cp y=w*A[i+j+len]; A[i+j]=x+y; A[i+j+len]=x-y; } } } if(flag==-1)for(int i=0; i<n; i++)A[i]/=n; } inline void work(){ m=n*2; for(n=1; n<m; n*=2); fft(a,1); fft(b,1); for(int i=0; i<n; i++)a[i]*=b[i]; fft(a,-1); for(int i=0; i<m; i++)c[i]=(int)(a[i].real()+0.5); while(c[m-1]==0)m--; for(int i=0; i<m; i++){ if(c[i]>=10){ c[i+1]+=c[i]/10; c[i]%=10; if(i==m-1)m++; } } for(int i=m-1; i>=0; i--)printf("%d",c[i]); puts(""); } int main(){ init(); work(); return 0; } |
模板：半平面交
|
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include<bits/stdc++.h> #define db double #define maxn 505 #define eps 1e-7 #define Vector point using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct point{ db x,y; point(db xx=0,db yy=0){x=xx,y=yy;} friend point operator + (Vector a,Vector b){return point(a.x+b.x,a.y+b.y);} friend point operator - (Vector a,Vector b){return point(a.x-b.x,a.y-b.y);} friend point operator * (Vector a,db b){return point(a.x*b,a.y*b);} friend point operator / (Vector a,db b){return point(a.x/b,a.y/b);} friend bool operator < (Vector a,Vector b){return a.x<b.x || fabs(a.x-b.x)<eps && a.y<b.y;} }p[maxn],a[maxn]; struct line{ point p,v; db ang; line(){} line(point P,Vector V){ p=P; v=V; ang=atan2(v.y,v.x); } friend bool operator < (line a,line b){ return a.ang<b.ang; } }L[maxn],q[maxn]; inline db cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}//叉积 inline point GetPoint(line a,line b){//用叉积计算面积，用相似计算交点 Vector V=a.p-b.p; db t=cross(b.v,V)/cross(a.v,b.v); return a.p+a.v*t; } inline bool Onleft(line l,point p){//点是否在向量的左边 return cross(l.v,p-l.p)>0; } int cnt; inline void init(){ int T=rd(); while(T--){ int n=rd(); for(int i=1; i<=n; i++)p[i].x=rd(),p[i].y=rd(); p[n+1]=p[1]; for(int i=1; i<=n; i++)L[++cnt]=line(p[i],p[i+1]-p[i]);//把给定的多边形的所有边变成向量放进集合 } } int head=1,tail=0; inline void hpi(){ sort(L+1,L+cnt+1); q[++tail]=L[1]; for(int i=2; i<=cnt; i++){//把向量依次插入 while(head<tail && !Onleft(L[i],p[tail-1]))tail--;//如果队尾的交点在当前向量的右边，就删掉 while(head<tail && !Onleft(L[i],p[head]))head++;//对队头做相同的处理 q[++tail]=L[i];//把新的向量加进队列 if(fabs(cross(q[tail].v,q[tail-1].v))<eps){//如果新的向量和上一条边是平行的，需要删掉 tail--; if(Onleft(q[tail],L[i].p))q[tail]=L[i]; } if(head<tail)p[tail-1]=GetPoint(q[tail-1],q[tail]);//计算一下新的交点的坐标 } while(head<tail && !Onleft(q[head],p[tail-1]))tail--;//最后进行封口，假装插入一下head，把队尾不合法的向量删掉 p[tail]=GetPoint(q[tail],q[head]);//算一下最后的那个交点 } inline void work(){ hpi(); db ans=0; for(int i=head+1; i<tail; i++){ ans+=cross(p[i]-p[head],p[i+1]-p[head]);//计算面积 } printf("%.3lf\n",ans*0.5); } int main(){ init(); work(); return 0; } |
模板：舞蹈链
|
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
#include<bits/stdc++.h> using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct DLX{ #define maxnode 1000010 #define maxn 1010 int n,m,tot; //n行 m列 现在一共有tot个元素 int U[maxnode],D[maxnode],L[maxnode],R[maxnode]; //U D L R 表示每个点四个方向所指向的节点编号 int Row[maxnode],Col[maxnode]; //Row Col 表示每个点所在的行号和列号 int H[maxn],num[maxn]; //H 是每行的开始位置 num 是每一列有多少个元素 int ansnum,ans[maxn]; //记录答案，表示我们选择了哪些行 inline void init(int N,int M){ n=N,m=M; for(int i=0; i<=m; i++){ num[i]=0; U[i]=D[i]=i; L[i]=i-1; R[i]=i+1; } L[0]=m; R[m]=0; tot=m; for(int i=1; i<=n; i++)H[i]=-1; } inline void add(int x,int y){//在x行y列插入一个元素 tot++; Col[tot]=y; Row[tot]=x; num[y]++; D[tot]=D[y]; U[D[y]]=tot; U[tot]=y; D[y]=tot; //在第y列的列首元素下面插入当前元素 if(H[x]<0){//如果第x行为空，那么将当前元素设为行首元素 H[x]=L[tot]=R[tot]=tot; } else{//否则在第x行的第一个元素后插入当前元素 R[tot]=R[H[x]]; L[R[H[x]]]=tot; L[tot]=H[x]; R[H[x]]=tot; } } inline void remove(int y){//将第y列删除，并删除第y列中所有元素所在的行 L[R[y]]=L[y]; R[L[y]]=R[y]; for(int i=D[y]; i!=y; i=D[i]){ for(int j=R[i]; j!=i; j=R[j]){ U[D[j]]=U[j]; D[U[j]]=D[j]; num[Col[j]]--; } } } inline void restore(int y){//反过来，进行恢复 L[R[y]]=y; R[L[y]]=y; for(int i=U[y]; i!=y; i=U[i]){ for(int j=L[i]; j!=i; j=L[j]){ U[D[j]]=j; D[U[j]]=j; num[Col[j]]++; } } } bool dance(int deep){ if(R[0]==0){ ansnum=deep; return true; } int now=R[0]; for(int i=R[0]; i!=0; i=R[i]){ if(num[i]<num[now])now=i; } //找到列中包含1最少的列，因为这样可以减少dfs的分支 remove(now); for(int i=D[now]; i!=now; i=D[i]){ ans[deep]=Row[i]; for(int j=R[i]; j!=i; j=R[j])remove(Col[j]); if(dance(deep+1))return true; for(int j=L[i]; j!=i; j=L[j])restore(Col[j]); } restore(now); return false; } #undef maxnode #undef maxn }dlx; inline void init(){ int n=rd(),m=rd(); dlx.init(n,m); for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ int x=rd(); if(x)dlx.add(i,j); } } } inline void work(){ if(dlx.dance(0)){ for(int i=0; i<dlx.ansnum; i++){ printf("%d ",dlx.ans[i]); } puts(""); } else puts("No Solution!"); } int main(){ init(); work(); return 0; } |
模板：splay
|
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
#include <bits/stdc++.h> #define MAXN 100010 #define inf INT_MAX/2 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct splay_tree{ int son[MAXN][2],fa[MAXN],val[MAXN],key[MAXN],sz[MAXN]; int tot,root; bool rev[MAXN]; void init(){ memset(son,0,sizeof(son)); memset(fa,0,sizeof(fa)); memset(rev,0,sizeof(rev)); val[1]=-inf,val[2]=inf; key[1]=-inf,key[2]=inf; son[2][0]=1; sz[2]=2;sz[1]=1; fa[1]=2; tot=2; root=2; } void Set(int x,int f,int w){ son[f][w]=x; fa[x]=f; } void pushup(int x){ sz[x]=sz[son[x][0]]+sz[son[x][1]]+1; } void add(int x,int k){ int now=root,pre; while(1){ pre=now; now=son[now][k>key[now]]; if(!now){ now=++tot; Set(now,pre,k>key[pre]); val[now]=x; key[now]=k; sz[now]=1; pushup(pre); splay(x,0); return; } } } bool getlr(int x){ return son[fa[x]][1]==x; } void Rev(int x){ if(!x)return; rev[x]^=1; swap(son[x][0],son[x][1]); } void pushdown(int x){ if(!x)return; if(rev[x]){ Rev(son[x][0]); Rev(son[x][1]); rev[x]^=1; } } void Rotate(int x){ int f=fa[x],ff=fa[f],w=getlr(x); Set(x,ff,getlr(f)); Set(son[x][w^1],f,w); Set(f,x,w^1); pushup(f),pushup(x); } void splay(int x,int to){ pushdown(x); for(int f=fa[x]; f!=to; f=fa[x]){ if(fa[f]!=to)Rotate(getlr(x)==getlr(f)?f:x); Rotate(x); } if(to==0)root=x; } int getkth(int x){ int now=root; while(now){ pushdown(now); if(sz[son[now][0]]==x-1)return now; else if(sz[son[now][0]]<x)x-=sz[son[now][0]]+1,now=son[now][1]; else now=son[now][0]; } } void spilit(int l,int r){ splay(getkth(l),0); splay(getkth(r+2),root); } void Reverse(int l,int r){ spilit(l,r); Rev(son[son[root][1]][0]); } void print(int x){ if(!x)return; pushdown(x); print(son[x][0]); if(val[x]!=inf && val[x]!=-inf)printf("%d ",val[x]); print(son[x][1]); } }splay; int n,m; int main(){ n=rd(),m=rd(); splay.init(); for(int i=1; i<=n; i++)splay.add(i,i); while(m--){ int x=rd(),y=rd(); splay.Reverse(x,y); } splay.print(splay.root); puts(""); return 0; } |