「Author」模板集合 学习笔记 (怀念版)

停更3年了，好怀念，上一次还是 $\downarrow$

$\mathtt{Update}\ \mathtt{2020.12.4}$

数学

裴蜀定理

我又来水代码了 我已开始还以为裴蜀是Chinese $\mathtt{Link}$

#include<bits/stdc++.h>
using namespace std;
int n,ans,x;
inline int gcd(int a,int b) {
    return !b?a:gcd(b,a%b);
}
int main() {
    int i,j;
    scanf("%d%d",&n,&ans);
    for(i=1;i<n;i++) scanf("%d",&x),ans=gcd(ans,abs(x));
    printf("%d",ans);
    return 0;
}

nim游戏

水代码 判断异或值即可

#include<bits/stdc++.h>
using namespace std;
int n,T,ans;
int read() {
    int s=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)){s=(s<<1)+(s<<3)+c-'0';c=getchar();}
    return s;
}
int main() {
    T=read();
    while(T--) {
        n=read();ans=0;
        for(int i=1;i<=n;i++) ans^=read();
        puts(ans?"Yes":"No");
    }
    return 0;
}

线性基

$\mathtt{OI-wiki\ Link}$

挺好用的 /dei!

#include<bits/stdc++.h>
#define LL long long
#define N 55
using namespace std;
int n;
LL x,ans,p[N];
int main() {
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++) {
        scanf("%lld",&x);
        for(j=51;j>=0;j--)
            if((x>>j)&1) {
                if(!p[j]){p[j]=x;break;}
                x^=p[j];
            }
    }
    for(i=51;i>=0;i--)
        if((ans^p[i])>ans) ans^=p[i];
    printf("%lld",ans);
    return 0;
}

卢卡斯定理

$\mathtt{Link}$ 即：

$$\binom nm \equiv \binom {\lfloor n/p\rfloor} {\lfloor m/p\rfloor}\cdot\binom {n\mod p} {m\mod p}\pmod p$$

#include<bits/stdc++.h>
#define N 100007
#define LL long long
using namespace std;
int T;
LL n,m,p,inv[N],mul[N];
LL C(LL n,LL m) {
    if(m>n) return 0;
    return mul[n]*inv[m]*inv[n-m]%p;
}
LL Lucas(LL n,LL m) {
    if(!m) return 1;
    return C(n%p,m%p)*Lucas(n/p,m/p)%p;
}
int main() {
    int i;inv[1]=mul[1]=inv[0]=mul[0]=1;
    scanf("%d",&T);
    while(T--) {
        scanf("%lld%lld%lld",&n,&m,&p);
        for(i=2;i<=p;i++) inv[i]=(p-p/i)*inv[p%i]%p;//线性求逆元
        for(i=2;i<=p;i++) inv[i]=inv[i-1]*inv[i]%p,mul[i]=mul[i-1]*i%p;
        printf("%lld\n",Lucas(n+m,m));
    }
    return 0;
}

扩展卢卡斯

此时模数不是质数，需要通过中国剩余定理合并 $\mathtt{Link}$

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 1000003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
LL n,m,ans,p;
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline void Ex_gcd(rll a,rll b,rll &x,rll &y) {
    if(!b) {x=1,y=0;return;}
    Ex_gcd(b,a%b,y,x),y-=a/b*x;
}
inline LL Pow(rll a,rll b,rint p) {
    rll res=1;for(;b;b>>=1,a=a*a%p)
    if(b&1) res=res*a%p;return res;
}
inline LL fac(rll n,rll pi,rll p) {
    if(!n) return 1;
    rll res=1,i;
    for(i=2;i<=p;i++)
        if(i%pi) res=res*i%p;
    res=Pow(res,n/p,p);
    for(i=2;i<=n%p;i++)
        if(i%pi) res=res*i%p;
    return res*fac(n/pi,pi,p)%p;
}
inline LL inv(rll n,rll p) {
    rll x,y;Ex_gcd(n,p,x,y);
    return (x+=p)>p?x-p:x;
}
inline LL CRT(rll b,rll c) {
    return b*inv(p/c,c)%p*(p/c)%p;
}
inline LL C(rll n,rll m,rll pi,rll pk) {
    rll up=fac(n,pi,pk),d1=fac(m,pi,pk),d2=fac(n-m,pi,pk);
    rll res=0,i;
    for(i=n;i;i/=pi) res+=i/pi;
    for(i=m;i;i/=pi) res-=i/pi;
    for(i=n-m;i;i/=pi) res-=i/pi;
    return up*inv(d1,pk)%pk*inv(d2,pk)%pk*Pow(pi,res,pk)%pk;
}
inline int Ex_Lucas(rll n,rll m) {
    rll tp=p,c;
    for(rint i=2;i*i<=tp;i++)
        if(tp%i==0) {
            c=1;
            while(tp%i==0) c*=i,tp/=i;
            (ans+=CRT(C(n,m,i,c),c))%=p;
        }
    if(tp>1) (ans+=CRT(C(n,m,tp,tp),tp))%=p;
    return ans;
}
int main()
{
    scanf("%lld%lld%d",&n,&m,&p);
    printf("%d",Ex_Lucas(n,m));
    return 0;
}

乘法逆元2

$Loj$ 加强版 $\mathtt{Link}$$ 做法：先求整体的逆元，再处理前后缀乘积的该元素逆元

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rLL rgt LL
#define inf 0x7f7f7f7f
#define N 5000007
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
int n;LL a[N],k,p,ans,inv,c=1,ls[N],rs[N];
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline LL Pow(rLL a,rint b) {
    rLL res=1;
    for(;b;a=a*a%p,b>>=1)
        if(b&1) res=res*a%p;
    return res;
}
int main() {
    int i,j;
    n=read(),p=read(),k=read(),ls[0]=rs[n+1]=1;
    for(i=1;i<=n;i++) a[i]=read(),ls[i]=ls[i-1]*a[i]%p;//前缀积
    inv=Pow(ls[n],p-2),c=Pow(k,n),k=Pow(k,p-2);//整体逆元
    for(i=n;i;i--)
        ans+=(inv*ls[i-1]%p)*c%p,inv=inv*a[i]%p,c=c*k%p;//后缀积
    printf("%d\n",ans%p);
    return 0;
}

数据结构

莫队

选的是我写莫队(假装)顶峰时的代码 $\mathtt{Link}$

#include<bits/stdc++.h>
#define getchar() *(p++)
#define rgt register
#define rint rgt int
#define N 1000007
using namespace std;
struct node{
    int l,r,i;
}b[N];
int n,m,t,l,r,block,pos[N],Ans[N];
int s[N],a[N],d[N],f[N],sum[N],ans;
char bf[1<<25],*p=bf;
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline bool cmp(rgt node a,rgt node b) {//看似很飘的样子(奇偶性优化
    return (pos[a.l]^pos[b.l])?a.l<b.l:(pos[a.l]&1)?a.r<b.r:a.r>b.r;
}
inline bool Add(rgt int x) {if(!sum[f[x]]++) ans^=a[x];}
inline bool Del(rgt int x) {if(!(--sum[f[x]])) ans^=a[x];}
int main()
{
    rint i;bf[fread(bf,1,1<<25,stdin)]='\0',n=read();
    for(i=1;i<=n;i++) d[i]=a[i]=read(),s[i]=s[i-1]^a[i];
    m=read();sort(d+1,d+1+n),t=unique(d+1,d+1+n)-d-1,block=n/sqrt(m*0.9);//玄学的块的大小
    for(i=1;i<=n;i++) f[i]=lower_bound(d+1,d+t+1,a[i])-d,pos[i]=i/block;
    for(i=1;i<=m;i++) b[i].l=read(),b[i].r=read(),b[i].i=i;
    sort(b+1,b+1+m,cmp),l=1;
    for(i=1;i<=m;i++) {//尽量先Add再Del,否则可能会出现一些不必要的问题
        while(r<b[i].r) Add(++r);
        while(l>b[i].l) Add(--l);
        while(r>b[i].r) Del(r--);
        while(l<b[i].l) Del(l++);
        Ans[b[i].i]=ans^s[b[i].l-1]^s[b[i].r];
    }
    for(i=1;i<=m;i++) printf("%d\n",Ans[i]);
    return 0;
}

树链剖分

树链剖分的理论复杂度是 $m\log^2n$，但是有其优秀的常数，一般跑不满 $\mathtt{Link}$

其分为重链和长链剖分，这里写的是重链剖分，据某神仙说，树链剖分虽长但是吼打，是 $OIer$ $\times \times$ 的首选…

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 100007
using namespace std;
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int head[N],ver[N<<1],nxt[N<<1],in[N],a[N],out[N];
int fa[N],size[N],dep[N],son[N];
int seg[N],rev[N],top[N],num;
LL f[N<<2],tag[N<<2],ans,p;
int n,T,L,R,t,x,y,w,root;
inline void add(rint x,rint y) {
    ver[++t]=y,nxt[t]=head[x],head[x]=t,
    ver[++t]=x,nxt[t]=head[y],head[y]=t;
}
inline LL dec(rll x){return(x>=p)?x-p:x;}
inline void dfs1(rint k) {
    rint i,to;
    dep[k]=dep[fa[k]]+1,size[k]=1;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i];if(to==fa[k]) continue;
        fa[to]=k,dfs1(to),size[k]+=size[to];
        if(size[to]>size[son[k]])//重儿子
            son[k]=to;
    }
}
inline void dfs2(rint k) {
    in[k]=num;//子树的其实可以不用这么维护，但是我懒的改了，in[k]=seg[k]
    if(son[k]) {//out[k]=seg[k]+size[k]-1
        seg[son[k]]=++num,
        top[son[k]]=top[k],
        rev[num]=son[k],
        dfs2(son[k]);
    }
    rint i,to;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i];if(top[to]) continue;
        seg[to]=++num,rev[num]=top[to]=to;
        dfs2(to);//rev表示序号所对原来的位置
    }out[k]=num;
}
inline void built(rint k,rint l,rint r) {
    if(l==r){f[k]=a[rev[l]];return;}
    rint m=(l+r)>>1,ls=k<<1;
    built(ls,l,m),built(ls|1,m+1,r);
    f[k]=dec(f[ls]+f[ls|1]);
}
inline void push(rint k,rint l,rint r) {
    f[k]=(f[k]+tag[k]*(r-l+1))%p;
    if(l!=r) {
        rint ls=k<<1;
        tag[ls]=dec(tag[ls]+tag[k]),
        tag[ls|1]=dec(tag[ls|1]+tag[k]);
    }tag[k]=0;
}
inline void Modify(rint k,rint l,rint r) {
    if(tag[k]) push(k,l,r);
    if(r<L||R<l) return;
    if(L<=l&&r<=R) {tag[k]=w;return push(k,l,r);}
    rint m=(l+r)>>1,ls=k<<1;
    Modify(ls,l,m),Modify(ls|1,m+1,r);
    f[k]=dec(f[ls]+f[ls|1]);
}
inline void Query(rint k,rint l,rint r) {
    if(tag[k]) push(k,l,r);
    if(r<L||R<l) return;
    if(L<=l&&r<=R) {ans=dec(ans+f[k]);return;}
    rint m=(l+r)>>1,ls=k<<1;
    Query(ls,l,m),Query(ls|1,m+1,r);
}
#define fx top[x]
#define fy top[y]
inline void Add(rint x,rint y) {
    w=read()%p;
    while(fx!=fy) {
        if(dep[fx]<dep[fy]) swap(x,y);//保证跳的是深度较小的点
        L=seg[fx],R=seg[x],
        Modify(1,1,n),x=fa[fx];//跳轻边
    }
    if(dep[x]<dep[y]) swap(x,y);
    L=seg[y],R=seg[x],Modify(1,1,n);
}
inline void Ask(rint x,rint y) {
    while(fx!=fy) {
        if(dep[fx]<dep[fy]) swap(x,y);
        L=seg[fx],R=seg[x],
        Query(1,1,n),x=fa[fx];
    }
    if(dep[x]<dep[y]) swap(x,y);
    L=seg[y],R=seg[x],Query(1,1,n);
}
int main()
{
    rint i,op;
    n=read(),T=read(),root=read(),p=read();
    for(i=1;i<=n;i++) a[i]=read()%p;
    for(i=1;i<n;i++) add(read(),read());
    num=seg[root]=1,rev[1]=top[root]=root;//注意root不同
    dfs1(root),dfs2(root),built(1,1,n);//建树
    while(T--) {
        op=read();
        if(op==1||op==3) {
            if(op==3) {
                x=read(),w=read()%p,
                L=in[x],R=out[x],Modify(1,1,n);
            }
            else Add(read(),read());
        }
        else {
            ans=0;
            if(op==2) Ask(read(),read());
            else x=read(),L=in[x],R=out[x],Query(1,1,n);
            printf("%lld\n",ans);
        }
    }
    return 0;
}

主席树

可持久化线段树1(主席树)模板题，基本操作

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define inf 0x7f7f7f7f
#define N 200003
using namespace std;
struct node{
    int l,r,sum;
}T[N*80];
int a[N],b[N],root[N];
int n,m,k,t,res,ans;
inline int read() {
    rint s=0,p=1;
    rgt char c=getchar();
    while(!isdigit(c)) p=(c=='-')?-1:1,c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s*p;
}
inline void modify(rint l,rint r,rint &x,rint y,rint pos) {
    T[++res]=T[y];T[res].sum++;x=res;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(pos<=mid) modify(l,mid,T[x].l,T[y].l,pos);
    else modify(mid+1,r,T[x].r,T[y].r,pos);
}
inline void query(rint l,rint r,rint x,rint y,rint k) {
    if(l==r) {ans=l;return;}
    rint mid=(l+r)>>1,sum=T[T[y].l].sum-T[T[x].l].sum;
    if(k<=sum) query(l,mid,T[x].l,T[y].l,k);
    else query(mid+1,r,T[x].r,T[y].r,k-sum);
}
int main() {
    rint i,x,y;n=read();m=read();
    for(i=1;i<=n;i++) b[i]=a[i]=read();
    sort(b+1,b+1+n),t=unique(b+1,b+1+n)-b-1;
    for(i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+1+t,a[i])-b,
        modify(1,t,root[i],root[i-1],a[i]);
    for(i=1;i<=m;i++) {
        x=read(),y=read(),k=read(),
        query(1,t,root[x-1],root[y],k);
        printf("%d\n",b[ans]);
    }
    return 0;
}

可持久化线段树

第一次打可持久线段树（标记永久化），来自某道由 $\color{red}{\mathtt{b}}\color{black}{\mathtt{ztMinamoto}}\%\%\%$ 翻译的题 $\mathtt{Link}$

#include<bits/stdc++.h>//大致上和主席树类似，emmm...貌似主席树就是可持久化线段树...
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 100003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline LL read() {
    rll s=0,p=0;
    rgt char c=getchar();
    while(!isdigit(c)) p=(c=='-'),c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return p?-s:s;
}
inline void getc(char&c) {
    c=getchar();while(c<'A'||c>'Z') c=getchar();
}
struct node{
    int ls,rs;
    LL sum,tag;
}T[N*160];
int n,m,L,R,t,res,a[N],root[N];LL w,ans;
inline void built(rint k,rint l,rint r) {
    cmax(t,k);
    if(l==r) {T[k].sum=a[l];return;}
    rint m=(l+r)>>1,ls=k<<1;
    built(T[k].ls=ls,l,m),built(T[k].rs=ls|1,m+1,r),
    T[k].sum=T[ls].sum+T[ls|1].sum;
}
inline void Modify(rint l,rint r,rint &x,rint y) {
    if(r<L||R<l) return;
    x=++t,T[t]=T[y];
    if(L<=l&&r<=R) {T[x].tag+=w;return;}
    T[t].sum+=w*(min(r,R)-max(l,L)+1);//划重点，标记永久化的影响
    rint m=(l+r)>>1;
    Modify(l,m,T[x].ls,T[y].ls),
    Modify(m+1,r,T[x].rs,T[y].rs);
}
inline void push(rll tag,rint l,rint r) {
    ans+=(min(R,r)-max(L,l)+1)*tag;
}
inline void Query(rint l,rint r,rint root) {
    if(r<L||R<l) return;
    if(T[root].tag) push(T[root].tag,l,r);//划重点，标记永久化的影响
    if(L<=l&&r<=R) {ans+=T[root].sum;return;}
    rint m=(l+r)>>1;
    Query(l,m,T[root].ls),Query(m+1,r,T[root].rs);
}
int main()
{
    rint i;char op;
    n=read(),m=read();
    for(i=1;i<=n;i++) a[i]=read();
    built(1,1,n),root[0]=1;
    while(m--) {
        getc(op);
        if(op=='C') {
            L=read(),R=read(),w=read(),++res;
            Modify(1,n,root[res],root[res-1]);
        }
        else if(op=='Q')
            ans=0,L=read(),R=read(),Query(1,n,root[res]),printf("%lld\n",ans);
        else if(op=='H')
            ans=0,L=read(),R=read(),Query(1,n,root[read()]),printf("%lld\n",ans);
        else res=read();
    }
    return 0;
}

Link Cut Tree

$LCT$ 还是比较好理解的，只是想当初为了 $LCT$ 学 $Splay$ 学的头大 $\mathtt{Link}$

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define N 300007
using namespace std;
int fa[N],v[N],f[N],son[N][2];
int n,T,St[N],top;bool r[N];
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline bool Ide(rint x) {return son[fa[x]][1]==x;}//判断是左还是右儿子
inline bool Tol(rint x) {return (son[fa[x]][0]==x)||(son[fa[x]][1]==x);}//判断是否有实边相连
inline void Flip(rint x) {swap(son[x][0],son[x][1]),r[x]^=1;}//翻转
inline void push(rint x) {//下传翻转标记
    if(!r[x]) return;r[x]=0;
    if(son[x][0]) Flip(son[x][0]);
    if(son[x][1]) Flip(son[x][1]);
}
inline void Update(rint x) {
    f[x]=f[son[x][0]]^f[son[x][1]]^v[x];
}
inline void rotate(rgt int x) {
    rint y=fa[x],z=fa[y];
    rint ys=Ide(x),zs=Ide(y),v=son[x][ys^1];
    if(Tol(y)) son[z][zs]=x;fa[x]=z;//y连的是不是虚边
    son[x][ys^1]=y,fa[y]=x;
    if(v) fa[v]=y;son[y][ys]=v;
    Update(y),Update(x);//Updata
}
inline void Splay(rint x) {
    rint y=x,z;St[top=1]=y;
    while(Tol(y)) St[++top]=y=fa[y];//这里用于下传标记再翻转
    while(top) push(St[top--]);
    while(Tol(x)) {
        y=fa[x],z=fa[y];
        if(Tol(y))//仍然判虚边
            rotate((son[y][0]==x)^(son[z][0]==y)?x:y);//如果在一条链上就先rotate父亲
        rotate(x);//这样能使期望树高为log
    }
}
inline void Access(rint x) {//将x和root连成一条链
    for(rint y=0;x;x=fa[y=x])
        Splay(x),son[x][1]=y,Update(x);
}
inline void Catch(rint x) {//使x成为root
    Access(x),Splay(x),Flip(x);
}
inline int Search(rint x) {//寻找最浅的点，Link和Cut专用
    Access(x),Splay(x);
    while(son[x][0]) push(x),x=son[x][0];
    Splay(x);return x;
}
inline void Link(rint x,rint y) {
    Catch(x);
    if(Search(y)!=x) fa[x]=y;//直接连虚边即可
}
inline void Cut(rint x,rint y) {
    Catch(x);
    if(Search(y)==x&&fa[y]==x&&!son[y][0])//要判断一系列复杂的东西
        fa[y]=son[x][1]=0,Update(x);
}
inline void Query(rint x,rint y) {
    Catch(x),Access(y),Splay(y);
    printf("%d\n",f[y]);
}
int main()
{
    rint i,p,x,y;
    n=read(),T=read();
    for(i=1;i<=n;i++) v[i]=read();
    while(T--) {
        p=read(),x=read(),y=read();
        if(p==0) Query(x,y);
        else if(p==1) Link(x,y);
        else if(p==2) Cut(x,y);
        else Splay(x),v[x]=y,Update(x);
    }
    return 0;
}

貌似也是 $LCT$ 教会我卡常和压行（毒瘤码风

---

动态规划

数位 DP

数位 $DP$ 还是比较好理解的，需要注意的就是一些初始化和 $status$

模板题 [SCOI2009]windy数

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 13
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int l,r,t,num[N],f[N][N],ans;
inline int dfs(rint k,rint st,rint op) {
    if(!k) return 1;
    if(!op&&~f[k][st]) return f[k][st];//对没有达到上限的一般情况记忆化
    rint i,t=op?num[k]:9,res=0;//t表示的是当前枚举的上限
    for(i=0;i<=t;i++) {
        if(abs(st-i)<2) continue;
        if(st==11&&i==0)
            res+=dfs(k-1,11,op&(i==t));
        else res+=dfs(k-1,i,op&(i==t));
    }
    if(!op) f[k][st]=res;
    return res;
}
inline int solve(rint x) {
    memset(f,-1,sizeof(f)),t=0;//个人感觉这里第二次不用memset
    while(x) num[++t]=x%10,x/=10;
//  do num[++t]=x%10,x/=10; while(x);这样就可以把0算进去，有些题目会要求，但是问题不大
    return dfs(t,11,1);
}
int main() {
    l=read()-1,r=read();//对询问求见进行差分
    printf("%d",solve(r)-solve(l));
    return 0;
}

SAC#1 - 萌数

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define p 1000000007
#define N 1003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int top,num[N],sum[N],bi[N];
int ans,f[N][11][11][2];
char a[N],b[N];
inline int dec(rint x){return(x>=p)?x-p:x;}
inline int dfs(rint k,rint sec,rint fir,rint st,rint zt,rint op) {//六维状态
    if(st) return f[k][sec][fir][st]=op?sum[k]+1:bi[k+1];
    if(!k) return st;
    if(!op&&~f[k][sec][fir][st]) return f[k][sec][fir][st];
    rint i,t=op?num[k]:9;rll res=0;
    for(i=0;i<=t;i++) res=dec(res+dfs(k-1,fir,(i==0&&zt)?-1:i,st|(i==sec||i==fir),zt&(i==0),op&(i==t)));
    if(!op) f[k][sec][fir][st]=res;
    return res;
}
int main()
{
    rint i,j;bi[1]=1;
    for(i=2;i<N;i++) bi[i]=(LL)bi[i-1]*10%p;
    scanf("%s%s",a+1,b+1),top=strlen(a+1);
    for(i=1;i<=top;i++) num[i]=a[top-i+1]-'0';--num[1];
    i=1;while(num[i]<0) --num[i+1],num[i]+=10,++i;
    if(!num[top]) --top;memset(f,-1,sizeof(f));
    for(i=1;i<=top;i++) sum[i]=(sum[i-1]+(LL)num[i]*bi[i])%p;
    ans=-dfs(top,-1,-1,0,1,1),top=strlen(b+1);
    for(i=1;i<=top;i++) num[i]=b[top-i+1]-'0';
    for(i=1;i<=top;i++) sum[i]=(sum[i-1]+(LL)num[i]*bi[i])%p;
//    memset(f,-1,sizeof(f));第二次真不用memset
    ans+=dfs(top,-1,-1,0,1,1),printf("%d",(ans%p+p)%p);
    return 0;
}

求每位数的和 SP17247 PR003004 - Digit Sum

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
int num[19],t,nm,T;
LL f[19][191][2],l,r;
inline LL dfs(rint k,rint st,rint op) {
    if(!k) return st;
    if(~f[k][st][op]) return f[k][st][op];
    rint i,t=op?num[k]:9;rll res=0;
    for(i=0;i<=t;i++) res+=dfs(k-1,st+i,op&(i==t));
    return f[k][st][op]=res;
}
inline LL solve(rll c) {
    t=0;while(c) num[++t]=c%10,c/=10;
    memset(f,-1,sizeof(f));//记得初始化为0
    return dfs(t,0,1);
}
int main() {
    scanf("%d",&T);
    while(T--)
        scanf("%lld%lld",&l,&r),l=max(l-1,0ll),//不能为-1
        printf("%lld\n",solve(r)-solve(l));//差分
    return 0;
}

求数字出现的次数 Luogu P2602 [ZJOI2010]数字计数

对于这题我也不知道为什么开结构体所有一起算会炸，发现问题的联系我跪谢

最恐怖的是稍微改点地方答案就不同，$IDE$ 上跑的结果也不同

$Wrong\ Answer\ version$

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 11
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
struct node{
    LL s[11];int p;
    inline node operator+ (const node a) const{
        node c;
        for(rint i=0;i<=9;i++) c.s[i]=s[i]+a.s[i];
        return c;
    }
    inline node operator- (const node a) const{
        node c;
        for(rint i=0;i<=9;i++) c.s[i]=s[i]-a.s[i];
        return c;
    }
}f[13][11],ans,init;
int num[13],top;
LL l,r,a[11],sum[13],b[15];
inline node dfs(rint k,rint st,rint zt,rint op) {
    node res=init;
    if(!zt) res.s[st]+=op?sum[k]+1:b[k+1];
    if(!k) return res;
    if(!op&&f[k][st].p) return f[k][st];
    rint i,t=op?num[k]:9;
    for(i=0;i<=t;i++) res=res+dfs(k-1,i,zt&(i==0),op&(i==t));
    if(!op) f[k][st]=res;
    return res;
}
inline void solve(rll l,rll r) {
    top=0;do num[++top]=r%10,sum[top]=num[top]*b[top]+sum[top-1],r/=10; while(r);ans=dfs(top,0,1,1);
    top=0;do num[++top]=l%10,sum[top]=num[top]*b[top]+sum[top-1],l/=10; while(l);ans=ans-dfs(top,0,1,1);
}
int main() {
    rint i;b[1]=init.p=1;
    for(i=2;i<13;i++) b[i]=b[i-1]*10;
    scanf("%lld%lld",&l,&r),solve(l-1,r);
    for(i=0;i<=9;++i) printf("%lld ",ans.s[i]);
    return 0;
}

$Accepted\ version$

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int t,num[15];
LL l,r,f[15][15][2][2];
inline LL dfs(rint k,rint st,rint zt,rint op,rint nm) {
    if(!k) return st;
    if(~f[k][st][zt][op]) return f[k][st][zt][op];
    rint i,t=op?num[k]:9;rll res=0;
    for(i=0;i<=t;i++)
        res+=dfs(k-1,st+((!zt||i)&&i==nm),zt&(i==0),op&(i==t),nm);//前导0的特判
    f[k][st][zt][op]=res;
    return res;
}
inline LL solve(rll x,rint nm) {
    t=0;while(x) num[++t]=x%10,x/=10;
    memset(f,-1,sizeof(f));return dfs(t,0,1,1,nm);
}
int main()
{
    scanf("%lld%lld",&l,&r),--l;
    for(rint i=0;i<=9;i++) printf("%lld ",solve(r,i)-solve(l,i));//对每位一次计数
    return 0;
}

---

图论

缩点

没想到缩点代码居然还有小长 $\mathtt{Link}$

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define M 200007
#define N 10007
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
int head[N],h[N],ver[M],nxt[M];
int dfn[N],low[N],bl[N],res;
int a[N],f[N],d[N];
int n,m,num,ans,t;
int St[N],top;
bool vis[N];
inline int read() {
    rint s,p;s=p=0;
    rgt char c=getchar();
    while(!isdigit(c)) p=(c=='-'),c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return p?-s:s;
}
inline void add(rint x,rint y) {
    ver[++t]=y,nxt[t]=head[x],head[x]=t;
}
inline void Add(rint x,rint y) {
    ver[++t]=y,nxt[t]=h[x],h[x]=t;
}
inline void tarjan(rint k) {
    dfn[k]=low[k]=++num,St[++top]=k;
    for(rint i=head[k],to;i;i=nxt[i]) {
        to=ver[i];
        if(!dfn[to]) tarjan(to),cmin(low[k],low[to]);
        else if(!bl[to]) cmin(low[k],dfn[to]);//这个特判很重要！
    }
    if(dfn[k]==low[k]) {
        bl[k]=++res,f[res]=a[k];
        while(St[top]!=k)
            bl[St[top]]=res,f[res]+=a[St[top--]];
        top--;
    }
}
inline void solve() {
    rint i,to,cur;
    queue<int>p;
    for(i=1;i<=res;i++)
        if(!d[i]) cmax(ans,f[i]),p.push(i);
    while(!p.empty()) {
        cur=p.front(),p.pop();
        for(i=h[cur];i;i=nxt[i]) {
            to=ver[i],d[to]--,
            cmax(f[to],a[to]+f[cur]),
            cmax(ans,f[to]);
            if(!d[to]) p.push(to);
        }
    }
}
int main()
{
    rint i,j,to,x,y;
    n=read(),m=read();
    for(i=1;i<=n;i++) a[i]=read();
    for(i=1;i<=m;i++) x=read(),add(x,read());
    for(i=1;i<=n;i++) if(!dfn[i]) tarjan(i);//每个都要做一下
    for(i=1;i<=res;i++) a[i]=f[i];
    for(i=1;i<=n;i++)//二次加点有点复杂
        for(j=head[i];j;j=nxt[j]) {
            to=ver[j];
            if(bl[i]==bl[to]) continue;
            Add(bl[i],bl[to]),++d[bl[to]];
        }solve();
    printf("%d",ans);
    return 0;
}

2-SAT 问题

实际上其实是缩点的变种应用 $\mathtt{Link}$

这里应该还有我自己写的 $2-SAT$ 学习笔记

特别注意对各种命题的建边形式

若一种命题的两种情况位于同一强连通则无解，否则 $dfn$ 序即为拓扑序的反序

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 1000003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int head[N<<1],ver[N<<1],nxt[N<<1],n,m,t,num;
int bl[N<<1],St[N<<1],top,dfn[N<<1],low[N<<1],res;//这里都是tarjan的标准配置
bool vis[N],w[N];
inline void add(rint x,rint y) {
    ver[++t]=y,nxt[t]=head[x],head[x]=t;//肯定是单向的，表示若p则q
}
inline void tarjan(rint k) {
    rint i,to;
    dfn[k]=low[k]=++num,St[++top]=k;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i];
        if(!dfn[to]) tarjan(to),cmin(low[k],low[to]);
        else if(!bl[to]) cmin(low[k],dfn[to]);
    }
    if(dfn[k]==low[k]) {
        bl[k]=++res;
        while(St[top]!=k)
            bl[St[top]]=res,--top;
        --top;
    }
}
inline void dfs(rint k) {
    rint i,to;
    if(k>n) vis[k-n]=1,w[k-n]=1;
    else vis[k]=1;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i]>n?ver[i]-n:ver[i];
        if(!vis[to]) dfs(ver[i]);
    }
}
int main()
{
    rint i,x,y,vx,vy;
    n=read(),m=read();
    for(i=1;i<=m;i++) {
        x=read(),vx=read(),
        y=read(),vy=read(),
        add(y+(vy^1)*n,x+vx*n),
        add(x+(vx^1)*n,y+vy*n);
    }
    for(i=1;i<=(n<<1);i++)
        if(!dfn[i]) tarjan(i);
    for(i=1;i<=n;i++)
        if(bl[i]==bl[i+n]) {
            printf("IMPOSSIBLE");
            return 0;
        }
    printf("POSSIBLE\n");
    for(i=1;i<=n;i++) printf("%d ",bl[i]>bl[i+n]);
    return 0;
}

网络最大流

网络流背板子，只是建边较难，卡Dinic是违法的 $\mathtt{Link}$

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define M 100007
#define N 10007
using namespace std;
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
struct node{
    int to,nxt,cap;
    node(int a,int b,int c):to(a),nxt(b),cap(c){ }
    node(){    }
}b[M<<1];
int head[N],dep[N];
int n,m,S,T,t=1,Maxflow;
inline void add(rint x,rint y,rint cap) {//正边流量为cap，反边流量为0
    b[++t]=node(y,head[x],cap),head[x]=t,
    b[++t]=node(x,head[y],0),head[y]=t;
}
inline bool BFS() {
    rint i,c,to;queue<int>p;
    memset(dep,0,sizeof(dep));
    dep[S]=1,p.push(S);//dep[S]一定要赋为0
    while(!p.empty()) {
        c=p.front(),p.pop();
        for(i=head[c];i;i=b[i].nxt) {
            to=b[i].to;
            if(b[i].cap&&!dep[to]) {
                dep[to]=dep[c]+1;//一定要先标记
                if(to==T) return 1;
                p.push(to);
            }
        }
    }return 0;
}
inline int Dinic(rint k,rint flow) {
    if(k==T) return flow;
    rint i,to,cap,res,rest=flow;
    for(i=head[k];i&&rest;i=b[i].nxt) {//rest的条件不要忘记
        to=b[i].to,cap=b[i].cap;//可以用上当前弧优化
        if(cap&&dep[to]==dep[k]+1) {
            res=Dinic(to,min(rest,cap));
            if(!res) dep[to]=0;
            b[i].cap-=res,
            b[i^1].cap+=res,
            rest-=res;
        }
    }return flow-rest;
}
int main()
{
    rint i,x,y,flow=0;
    n=read(),m=read(),S=read(),T=read();
    for(i=1;i<=m;i++)
        x=read(),y=read(),add(x,y,read());
    while(BFS())
        while((flow=Dinic(S,inf)))//这里还可以用上当前弧优化
            Maxflow+=flow;
    printf("%d",Maxflow);
    return 0;
}

后续还会贴上最大流的一些优化

字符串

manacher 算法

Luogu P3805 【模板】manacher算法

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 11000007
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rgt int s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n,m,len,mx,id,p[N<<1],ans;
char s[N<<1],st[N];
inline void init() {
    rint i;len=strlen(st+1);
    s[0]='!',s[1]='#',
    n=(len<<1|1)+1;
    for(i=1;i<=len;i++)//扩展为 !#st_1#st_2...#? 形式
        s[i<<1]=st[i],s[i<<1|1]='#';
    s[n]='?';return;
}
inline void manacher() {
    rint i;init();
    for(i=1;i<=n;i++) {
        if(i<mx) p[i]=min(p[(id<<1)-i],mx-i);//合理利用已处理部分
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]]) ++p[i];
        if(i+p[i]>mx) mx=i+p[i],id=i;
    }
}
int main() {
    rint i;scanf("%s",st+1);
    manacher();for(i=1;i<n;i++) cmax(ans,p[i]);
    printf("%d",ans-1);return 0;
}

KMP 算法

Luogu P3375 【模板】KMP字符串匹配

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define N 1000003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n,A,B,p[N];
char a[N],b[N];
int main()
{
    rint i,j;
    scanf("%s",a+1),scanf("%s",b+1);
    A=strlen(a+1),B=strlen(b+1);
    for(i=2,j=0;i<=B;i++) {//求next因此从i=2开始
        while(j&&b[i]!=b[j+1]) j=p[j];
        if(b[i]==b[j+1]) ++j;p[i]=j;
    }
    for(i=1,j=0;i<=A&&j<=B;i++) {
        while(j&&(j==B||a[i]!=b[j+1])) j=p[j];
        if(a[i]==b[j+1]) ++j;
        if(j==B) printf("%d\n",i-B+1);//出现的位置
    }
    for(i=1;i<=B;i++) printf("%d ",p[i]);
    return 0;
}

后缀数组

Luogu P3809 【模板】后缀排序 (SA)

#include<bits/stdc++.h>
#define N 1000010
using namespace std;
int n,m,x[N],y[N],c[N],sa[N],p;
char s[N];
int main()
{
    int i,k;
    scanf("%s",s);
    n=strlen(s);m=125;
    for(i=0;i<n;i++) c[x[i]=s[i]]++;
    for(i=1;i<m;i++) c[i]+=c[i-1];
    for(i=0;i<n;i++) sa[--c[x[i]]]=i;
    for(k=1;k<=n;k<<=1) {
        p=0;
        for(i=n-k;i<n;i++) y[p++]=i;
        for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
        for(i=0;i<m;i++) c[i]=0;
        for(i=0;i<n;i++) c[x[y[i]]]++;
        for(i=1;i<m;i++) c[i]+=c[i-1];
        for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);p=1;x[sa[0]]=0;
        for(i=1;i<n;i++)
            x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k])?p-1:p++;
        if(p>=n) break;
        m=p;
    }
    for(i=0;i<n;i++) printf("%d ",sa[i]+1);
    return 0;
}