数学篇

欧拉筛

#include <cstdio> using namespace std; int n,i,j,sc[],tot; bool ss[]; int main() { scanf("%d",&n); for (i=2;i<=n;i++) { if (!ss[i]) { ss[i]=true; sc[++tot]=i; } for (j=1;j<=tot&&i*sc[j]<=n;j++) { ss[i*sc[j]]=true; if (i%sc[j]==0) break; } } for (i=1;i<=tot;i++) printf("%d ",sc[i]); }

phi

讯享网#include <cstdio> #include <cmath> using namespace std; int main() { int n,i; scanf("%d",&n); int ans=1; for (i=2;i*i<=n;i++) if (n%i==0) { ans*=i-1;n/=i; while (n%i==0) n/=i,ans*=i; } if (n>1) ans*=n-1; printf("%d",ans); }

线性求phi

#include <cstdio> using namespace std; int phi[10005]; int main() { int n,i,j; scanf("%d",&n); phi[1]=1; for (i=2;i<=n;i++) if (!phi[i]) { for (int j=i;j<=n;j+=i) { if (!phi[j]) phi[j]=j; phi[j]=phi[j]/i*(i-1); } } for (i=1;i<=n;i++) printf("%d ",phi[i]); }

exgcd

讯享网#include <cstdio> using namespace std; int a,b,x,y,c; int gcd(int a,int b) { if (b) return gcd(b,a%b); else return a; } void exgcd(int a,int b,int &x,int &y) { if (!b) { 
  
    
  x=1;y=0;} else {exgcd(b,a%b,y,x); y-=x*(a/b);} } int main() { scanf("%d%d%d",&a,&b,&c); exgcd(a,b,x,y); int g=gcd(a,b); if (c%g==0) printf("%d %d",x*c/g,y*c/g); }

逆元

Lucas

#include <cstdio> #define LL long long using namespace std; const int N=1e5; int n,m,p;LL mul[N+5],inv[N+5]; void init() { int i; mul[0]=1; for (i=1;i<=p;i++) mul[i]=mul[i-1]*i%p; inv[0]=1; inv[1]=1; 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]*inv[i-1]%p; } LL C(int n,int m) { if (n>m) return 0; return mul[m]*inv[n]%p*inv[m-n]%p; } LL Lucas(int n,int m) { if (n>m) return 0; LL ans=1; for (;n;n/=p,m/=p) ans=ans*C(n%p,m%p)%p; return ans; } int main() { int T; scanf("%d",&T); while (T--) { scanf("%d%d%d",&n,&m,&p); init(); printf("%lld\n",Lucas(m,m+n)%p); } }

矩阵快速幂

讯享网#include <cstdio>  #include <cstring>  #define LL long long  using namespace std; const int Mod=1e9+7; struct hh{LL sq[105][105];void cl(){memset(sq,0,sizeof(sq));}}ans; int n; hh work(hh a,hh b) { int i,j,k; hh c;c.cl(); for (i=1;i<=n;i++) for (j=1;j<=n;j++) for (k=1;k<=n;k++) c.sq[i][j]=(a.sq[i][k]*b.sq[k][j]%Mod+c.sq[i][j])%Mod; return c; } hh ksm(LL k) { hh a; a=ans; for (;k;k>>=1,a=work(a,a)) if (k&1) ans=work(ans,a); return ans; } int main() { int i,j;LL k; scanf("%d%lld",&n,&k); for (i=1;i<=n;i++) for (j=1;j<=n;j++) { int a; scanf("%d",&a); ans.sq[i][j]=a; } ans=ksm(k-1); for (i=1;i<=n;i++) { for (j=1;j<=n;j++) printf("%lld ",ans.sq[i][j]); printf("\n"); } } 

图论篇

st表

#include <cmath> #include <cstdio> #include <iostream> #define sz 19 using namespace std; const int N=; int maxx[N][sz],n,m,i; void init() { for (int j=1;j<sz;j++) for (int i=1;i<=n;i++) if (i+(1<<j)-1<=n) maxx[i][j]=max(maxx[i][j-1],maxx[i+(1<<j-1)][j-1]); else break; } int main() { scanf("%d%d",&n,&m); for (i=1;i<=n;i++) scanf("%d",&maxx[i][0]); init(); while (m--) { int l,r; scanf("%d%d",&l,&r); int k=log2(r-l+1); printf("%d\n",max(maxx[l][k],maxx[r-(1<<k)+1][k])); } }

负环

讯享网#include <cstdio> #include <queue> #include <iostream> #include <cstring> #define N  using namespace std; int tot,nxt[N*2],point[N],v[N*2],c[N*2],tim[N],dis[N],n; bool vis[N],fff; void addline(int x,int y,int z){++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z;} void spfa(int now) { vis[now]=1; for (int i=point[now];i;i=nxt[i]) if (dis[v[i]]>dis[now]+c[i] && !fff) { dis[v[i]]=dis[now]+c[i]; if (vis[v[i]]) fff=1; spfa(v[i]); } vis[now]=0; } int main() { int T; scanf("%d",&T); while (T--) { int m,i;fff=0;tot=0;memset(point,0,sizeof(point)); scanf("%d%d",&n,&m); for (i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); addline(x,y,z); if (z>=0) addline(y,x,z); } memset(dis,0,sizeof(dis));//判负环的时候设成0更好 memset(vis,0,sizeof(vis)); for (i=1;i<=n;i++){spfa(i);if (fff) break;} if (fff) printf("YE5\n");else printf("N0\n"); } }

二分图匹配

#include <cstdio> #define N +5 using namespace std; int tot,nxt[N*2],point[N],v[N*2],belong[N],vis[N]; void addline(int x,int y) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; } bool find(int x,int k) { for (int i=point[x];i;i=nxt[i]) if (vis[v[i]]!=k) { vis[v[i]]=k; if (!belong[v[i]] || find(belong[v[i]],k)) { belong[v[i]]=x; return true; } } return false; } int main() { int n,m,e,i,x,y,ans=0; scanf("%d%d%d",&n,&m,&e); for (i=1;i<=e;i++) { scanf("%d%d",&x,&y); if (x>n || y>m) continue; y+=n;addline(x,y); } for (i=1;i<=n;i++) if (find(i,i)) ans++; printf("%d",ans); }

堆dij

讯享网#include <cstdio>  #include <cstring>  #include <queue>  #define M  #define N 10005  using namespace std; struct qnode { int node,dis; bool operator <(const qnode a) const { 
  
    
  return dis>a.dis;} }; priority_queue<qnode>q; int tot,nxt[M],point[M],v[M],cc[M],dis[N]; bool vis[N]; void addline(int x,int y,int cap) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; cc[tot]=cap; } int main() { int n,m,s,i; scanf("%d%d%d",&n,&m,&s); for (i=1;i<=m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); addline(a,b,c); } memset(vis,0,sizeof(vis)); memset(dis,0x7f,sizeof(dis)); dis[s]=0; q.push((qnode){s,0}); while (!q.empty()) { qnode noww=q.top(); q.pop(); int now=noww.node; if (vis[now]) continue; vis[now]=true; for (i=point[now];i;i=nxt[i]) if (dis[v[i]]>dis[now]+cc[i]) { dis[v[i]]=dis[now]+cc[i]; q.push((qnode){v[i],dis[v[i]]}); } } for (i=1;i<=n;i++) if (dis[i]==) printf(" "); else printf("%d ",dis[i]); } 

手写堆

#include <cstdio> #include <iostream> using namespace std; int q[],tot=0; void push(int x) { q[++tot]=x; int fa=tot>>1,now=tot; while (fa&&q[fa]>q[now]) { swap(q[fa],q[now]); now=fa; fa>>=1; } } void del() { q[1]=q[tot--]; int now=1,l=now<<1,r=now<<1|1,better=l; if (r<=tot && q[r]<q[l]) better=r; while (better<=tot && q[now]>q[better]) { swap(q[now],q[better]); now=better; l=now<<1; r=now<<1|1; better=l; if (r<=tot && q[r]<q[l]) better=r; } } int main() { int Q; scanf("%d",&Q); while (Q--) { int id,x;scanf("%d",&id); if (id==1) { scanf("%d",&x); push(x); } else if (id==2) printf("%d\n",q[1]); else del(); } }

树链剖分

讯享网#include <cstdio> #include <iostream> #define LL long long using namespace std; const int N=; int tot,nxt[N*2],point[N],v[N*2]; int h[N],size[N],father[N],son[N],top[N],totw,num[N],out[N],a[N],tree[N*4]; LL ww[N*4],p,delta[N*4]; void addline(int x,int y) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; } void dfs_1(int now,int dep,int fa) { h[now]=dep;father[now]=fa;int maxx=0; for (int i=point[now];i;i=nxt[i]) if (v[i]!=fa) { dfs_1(v[i],dep+1,now); size[now]+=size[v[i]]; if (maxx<size[v[i]]){maxx=size[v[i]]; son[now]=v[i];} } size[now]++; } void dfs_2(int now,int fa) { if (son[fa]==now) top[now]=top[fa]; else top[now]=now; num[now]=++totw; if (son[now]) { dfs_2(son[now],now); for (int i=point[now];i;i=nxt[i]) if (v[i]!=fa && v[i]!=son[now]) dfs_2(v[i],now); } out[now]=totw; } void updata(int now){ww[now]=ww[now<<1]+ww[now<<1|1];} void build(int now,int l,int r) { if (l==r) { ww[now]=a[tree[l]]; return; } int mid=(l+r)>>1; build(now<<1,l,mid); build(now<<1|1,mid+1,r); updata(now); } void pushdown(int now,int l,int r,int mid) { if (delta[now]) { ww[now<<1]=(ww[now<<1]+(LL)(mid-l+1)*delta[now])%p; ww[now<<1|1]=(ww[now<<1|1]+(LL)(r-mid)*delta[now]%p)%p; delta[now<<1]+=delta[now]; delta[now<<1|1]+=delta[now]; delta[now]=0; } } void change(int now,int l,int r,int lrange,int rrange,int k) { if(lrange<=l && rrange>=r) { delta[now]+=k; ww[now]=(r-l+1)*k%p+ww[now]; ww[now]%=p; return; } int mid=(l+r)>>1;pushdown(now,l,r,mid); if (lrange<=mid) change(now<<1,l,mid,lrange,rrange,k); if (rrange>mid) change(now<<1|1,mid+1,r,lrange,rrange,k); updata(now); } LL qurry(int now,int l,int r,int lrange,int rrange) { int mid=(l+r)>>1;LL ans=0;pushdown(now,l,r,mid); if(lrange<=l && rrange>=r) return ww[now]; if (lrange<=mid) ans=(ans+qurry(now<<1,l,mid,lrange,rrange))%p; if (rrange>mid) ans=(ans+qurry(now<<1|1,mid+1,r,lrange,rrange))%p; ans%=p; return ans; } int main() { int n,m,r,i; scanf("%d%d%d%lld",&n,&m,&r,&p); for (i=1;i<=n;i++) scanf("%d",&a[i]); for (i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); addline(x,y); } dfs_1(r,1,0); dfs_2(r,0); for (i=1;i<=n;i++) tree[num[i]]=i; build(1,1,n); while (m--) { int id,x,y,z; scanf("%d",&id); if (id==1) { scanf("%d%d%d",&x,&y,&z); int f1=top[x],f2=top[y]; while (f1!=f2) { if (h[f1]<h[f2]){swap(f1,f2); swap(x,y);} change(1,1,n,num[f1],num[x],z); x=father[f1]; f1=top[x]; } if (num[x]>num[y]) swap(x,y); change(1,1,n,num[x],num[y],z); } else if (id==2) { scanf("%d%d",&x,&y); int f1=top[x],f2=top[y];LL ans=0; while (f1!=f2) { if (h[f1]<h[f2]){swap(f1,f2); swap(x,y);} ans+=qurry(1,1,n,num[f1],num[x]); ans%=p; x=father[f1]; f1=top[x]; } if (num[x]>num[y]) swap(x,y); ans+=qurry(1,1,n,num[x],num[y]); ans%=p; printf("%lld\n",ans); } else if (id==3) { scanf("%d%d",&x,&z); change(1,1,n,num[x],out[x],z); } else { scanf("%d",&x); printf("%lld\n",qurry(1,1,n,num[x],out[x])%p); } } }

字符篇

KMP

#include <cstdio> #include <cstring> #include <iostream> using namespace std; int t[],l1,l2,i; char s1[],s2[]; void kmp()//失配函数都是被匹配串的。  { t[0]=-1; for (int i=0;i<l2;i++) { int j=t[i]; while (j!=-1 && s2[i]!=s2[j]) j=t[j]; t[i+1]=++j; } } int main() { scanf("%s%s",s1,s2); l1=strlen(s1); l2=strlen(s2); kmp();int j=0; for (i=0;i<l1;i++) { while (s1[i]!=s2[j] && j!=-1) j=t[j]; j++; if (j==l2) { printf("%d\n",i-l2+2); j=t[j]; } } for (i=1;i<=l2;i++) printf("%d ",t[i]); }

AC自动机

讯享网#include <queue> #include <cstdio> #include <cstring> using namespace std; const int N=1e6; int ch[N+5][30],is_end[N+5],tot,fail[N+5]; char ss[N+5],st[N+5];bool vis[N+5]; void trie() { int now=0,l=strlen(ss); for (int i=0;i<l;i++) { int x=ss[i]-'a'; if (!ch[now][x]) ch[now][x]=++tot; now=ch[now][x]; } is_end[now]++; } void sp() { queue<int>q; int now=0; for (int i=0;i<26;i++) if (ch[now][i]) q.push(ch[now][i]); while (!q.empty()) { int now=q.front(); q.pop(); for (int i=0;i<26;i++) { if (!ch[now][i]) { ch[now][i]=ch[fail[now]][i]; continue; } fail[ch[now][i]]=ch[fail[now]][i]; q.push(ch[now][i]); } } } void ac() { int now=0,l=strlen(st),ans=0; for (int i=0;i<l;i++) { vis[now]=1; int x=st[i]-'a'; int y=ch[now][x]; while (y && !vis[y]) { vis[y]=1; ans+=is_end[y]; y=fail[y]; } now=ch[now][x]; } printf("%d",ans); } int main() { int n; scanf("%d",&n); while(n--){ 
  
    
  scanf("%s",ss);trie();} sp(); scanf("%s",st); ac(); }

字符串hash