考前复习 打打模板

快读：

#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int rd(){
    int x=0,f=1;char c=gc();
    for(;c<'0'||c>'9';c=gc()) if(c=='-') f=0;
    for(;c>='0'&&c<='9';c=gc()) x=x*10+c-48;
    return f?x:-x;
}

快写：

char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
inline void print(int x){
    if(C>1<<20) Ot();if(x<0) sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}

 网络流（？）：算了好像csp不会考，留给以后

高斯消元：01+自由变元的板

void dfs(int x){
    if(!x){
        int tmp=0;
        for(int i=0;ia[i][n];
        anss=min(anss,tmp);return;
    }bool flag=0;
    if(!a[x][x]){
        if(a[x][n]) return;
        dfs(x-1);flag=1;a[x][n]=1;
    }for(int i=x-1;~i;i--){
        b[i][x]=a[i][n];
        a[i][n]^=(a[i][x]&a[x][n]);
    }dfs(x-1);
    for(int i=x-1;~i;i--) a[i][n]=b[i][x];
    if(flag) a[x][n]=0;
}int gauss(){
    int i=0,j=0;
    for(;i){
        int r=i;
        for(int k=i+1;kif(abs(a[k][j])>abs(a[r][j])) r=k;
        if(!abs(a[r][j])){i--;continue;}
        if(i!=r) for(int k=0;k<=n;k++) swap(a[r][k],a[i][k]);
        for(int k=i+1;kif(a[k][j])
            for(int l=j;l<=n;l++) a[k][l]^=a[i][l];
    }dfs(n-1);
    return anss!=inf;
}

扩欧：

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

扩展中国剩余定理：

int exgcd(int a,int b,int &x,int &y){
    if(!b){x=1,y=0;return;}
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;return d;
}int ex_crt(){
    int lcm=mod[1],lst=x[1];
    for(int i=2;i<=n;i++){
        int l=((x[i]-lst)%mod[i]+mod[i])%mod[i],x,y,k=lcm;
        int gcd=exgcd(lcm,mod[i],x,y);
        x=(x*l/gcd%(mod[i]/gcd)+(mod[i]/gcd))%(mod[i]/gcd);
        lcm=lcm*mod[i]/gcd,lst=(lst+k*x)%lcm;
    }return (lst%lcm+lcm)%lcm;
}

 Splay：

inline int Son(int x){return son[fa[x]][1]==x;}
inline void update(int x){
    sz[x]=sz[son[x][0]]+sz[son[x][1]]+1;
    sum[x]=sum[son[x][1]]+sum[son[x][0]]+a[x];
    lm[x]=max(lm[son[x][0]],sum[son[x][0]]+lm[son[x][1]]+a[x]);
    rm[x]=max(rm[son[x][1]],sum[son[x][1]]+rm[son[x][0]]+a[x]);
    mx[x]=rm[son[x][0]]+lm[son[x][1]]+a[x];
    if(son[x][0]) mx[x]=max(mx[x],mx[son[x][0]]);
    if(son[x][1]) mx[x]=max(mx[x],mx[son[x][1]]);
}inline void putdown(int x){
    int l=son[x][0],r=son[x][1];
    if(lzy[x]){
        rev[x]=0;lzy[x]=0;
        if(l) lzy[l]=1,a[l]=a[x],sum[l]=a[x]*sz[l];
        if(r) lzy[r]=1,a[r]=a[x],sum[r]=a[x]*sz[r];
        if(a[x]>0){
            if(l) lm[l]=rm[l]=mx[l]=sum[l];
            if(r) rm[r]=lm[r]=mx[r]=sum[r];
        }else{
            if(l) lm[l]=rm[l]=0,mx[l]=a[x];
            if(r) lm[r]=rm[r]=0,mx[r]=a[x];
        }
    }if(rev[x]){
        rev[x]=0;rev[l]^=1;rev[r]^=1;
        swap(lm[l],rm[l]);swap(lm[r],rm[r]);
        swap(son[l][0],son[l][1]),swap(son[r][0],son[r][1]);
    }
}int build(int l,int r,int f){
    int mid=(l+r)>>1;fa[mid]=f;
    if(l0]=build(l,mid-1,mid);
    if(r>mid) son[mid][1]=build(mid+1,r,mid);
    update(mid);return mid;
}inline void rotate(int x){
    int y=fa[x],z=fa[y],k=Son(x);
    fa[x]=z;z?son[z][Son(y)]=x:rt=x;
    son[y][k]=son[x][k^1];
    fa[son[y][k]]=y;fa[y]=x;
    son[x][k^1]=y;update(y);update(x);
}inline void splay(int x,int y){
    for(int f=fa[x];f=fa[x],f!=y;rotate(x))
        if(fa[f]!=y) rotate(Son(x)==Son(f)?f:x);
    !y?rt=x:rt=rt;
}inline int find(int x){
    int u=rt;
    while(u){
        putdown(u);
        if(x<=sz[son[u][0]]) u=son[u][0];
        else if(sz[son[u][0]]+1==x) return u;
        else x-=sz[son[u][0]]+1,u=son[u][1];
    }return u;
}