线段树 1
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
const LL N=1e5+2;
struct tree {
LL l,r,sum,tag;
} tr[N<<2];
#define l(x) tr[x].l
#define r(x) tr[x].r
#define sum(x) tr[x].sum
#define tag(x) tr[x].tag
LL a[N];
void build(LL x,LL l,LL r) {
l(x)=l,r(x)=r;
if(l==r) {
sum(x)=a[l];
return;
}
LL mid=(l+r)>>1;
build(x<<1,l,mid),build(x<<1|1,mid+1,r);
sum(x)=sum(x<<1)+sum(x<<1|1);
}
inline void spread(int x) {
if(tag(x)) {
sum(x<<1)+=tag(x)*(r(x<<1)-l(x<<1)+1);
sum(x<<1|1)+=tag(x)*(r(x<<1|1)-l(x<<1|1)+1);
tag(x<<1)+=tag(x),tag(x<<1|1)+=tag(x),tag(x)=0;
}
}
void add(LL x,LL l,LL r,LL del) {
if(l<=l(x)&&r(x)<=r) {
sum(x)+=del*(r(x)-l(x)+1);
tag(x)+=del;
return;
}
spread(x);
LL mid=(l(x)+r(x))>>1;
if(l<=mid) {
add(x<<1,l,r,del);
}
if(mid<r) {
add(x<<1|1,l,r,del);
}
sum(x)=sum(x<<1)+sum(x<<1|1);
}
LL query(LL x,LL l,LL r) {
if(l<=l(x)&&r(x)<=r) {
return sum(x);
}
spread(x);
LL mid=(l(x)+r(x))>>1,sum=0;
if(l<=mid) {
sum=query(x<<1,l,r);
}
if(mid<r) {
sum+=query(x<<1|1,l,r);
}
return sum;
}
int main() {
LL n,m;
scanf("%lld %lld",&n,&m);
for(LL i=1; i<=n; i++) {
scanf("%lld",a+i);
}
build(1,1,n);
while(m--) {
LL opt,x,y;
scanf("%lld %lld %lld",&opt,&x,&y);
if(opt^2) {
LL k;
scanf("%lld",&k);
add(1,x,y,k);
} else {
printf("%lld
",query(1,x,y));
}
}
return 0;
}
树状数组 1
#include<bits/stdc++.h>
using namespace std;
inline int lowbit(int x) {
return x&(-x);
}
const int N=5e5+5;
int n,tr[N<<2];
inline void add(int x,int del) {
while(x<=n) {
tr[x]+=del,x+=lowbit(x);
}
}
inline int query(int x) {
int sum=0;
while(x>0) {
sum+=tr[x],x-=lowbit(x);
}
return sum;
}
int main() {
int m;
scanf("%d %d",&n,&m);
for(int i=1,x; i<=n; i++) {
scanf("%d",&x),add(i,x);
}
while(m--) {
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
if(x==1) {
add(y,z);
} else {
printf("%d
",query(z)-query(y-1));
}
}
return 0;
}
最小费用最大流
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
bool vis[N];
int n,m,s,t,x,y,z,f,dis[N],pre[N],last[N],flow[N],maxflow,mincost;
//dis最小花费;pre每个点的前驱；last每个点的所连的前一条边；flow源点到此处的流量
struct Edge {
int v,nxt,flow,dis;//flow流量 dis花费
} e[N];
int head[N],cnt;
queue<int> q;
void add_edge(int from,int v,int flow,int dis) {
e[++cnt].nxt=head[from],e[cnt].v=v,e[cnt].flow=flow,e[cnt].dis=dis,head[from]=cnt;
}
bool spfa(int s,int t) {
memset(dis,0x7f,sizeof(dis)),memset(flow,0x7f,sizeof(flow));
memset(vis,0,sizeof(vis));
q.push(s),vis[s]=1,dis[s]=0,pre[t]=-1;
while(q.size()) {
int now=q.front();
q.pop(),vis[now]=0;
for(int i=head[now]; i!=-1; i=e[i].nxt) {
if(e[i].flow>0 && dis[e[i].v]>dis[now]+e[i].dis) {//正边
dis[e[i].v]=dis[now]+e[i].dis,pre[e[i].v]=now;
last[e[i].v]=i,flow[e[i].v]=min(flow[now],e[i].flow);
if(!vis[e[i].v]) {
vis[e[i].v]=1,q.push(e[i].v);
}
}
}
}
return pre[t]^-1;
}
int main() {
memset(head,-1,sizeof(head)),cnt=-1;//初始化
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1; i<=m; i++) {
scanf("%d%d%d%d",&x,&y,&z,&f);
add_edge(x,y,z,f); add_edge(y,x,0,-f);
//反边的流量为0，花费是相反数
}
while(spfa(s,t)) {
int now=t;
maxflow+=flow[t],mincost+=flow[t]*dis[t];
while(now^s) {//从源点一直回溯到汇点
e[last[now]].flow-=flow[t],e[last[now]^1].flow+=flow[t],now=pre[now];
}
}
printf("%d %d",maxflow,mincost);
return 0;
}
快速幂||取余运算
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
LL pow(LL x,LL y,LL p) {
LL ans=1;
while(y) {
if(y&1) {
ans=ans*x%p;
}
x=x*x%p,y>>=1;
}
return ans;
}
int main() {
LL b,p,k;
scanf("%lld %lld %lld",&b,&p,&k);
printf("%lld^%lld mod %lld=%lld",b,p,k,pow(b,p,k)%k);
return 0;
}
多项式乘法（FFT）
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL mod=998244353,G=3,N=2200000;
LL n,m,iN,a[N],b[N],tr[N];
void inc(LL &a,LL b) {
a+=b;
if(a>=mod) {
a-=mod;
}
}
void dec(LL &a,LL b) {
a-=b;
if(a<0) {
a+=mod;
}
}
LL _inc(LL a,LL b) {
a+=b;
if(a>=mod) {
a-=mod;
}
return a;
}
LL _dec(LL a,LL b) {
a-=b;
if(a<0) {
a+=mod;
}
return a;
}
LL mi(LL a,LL k=mod-2) {
LL sum=1;
while(k) {
if(k&1) {
sum=sum*a%mod;
}
a=a*a%mod,k>>=1;
}
return sum;
}
const LL iG=mi(G);
void NTT(LL *f,bool flag) {
for(LL i=0; i<n; i++) {if(i<tr[i]){swap(f[i],f[tr[i]]);
}
}
for(LL p=2; p<=n; p<<=1) {
LL angle=mi(flag?G:iG,(mod-1)/p);
for(LL k=0; k<n; k+=p) {
LL buf=1;
for(LL i=k; i<k+p/2; i++) {
LL tt=f[i+p/2]*buf%mod;
f[i+p/2]=_dec(f[i],tt),inc(f[i],tt);
buf=buf*angle%mod;
}
}
}
}
int main() {
scanf("%lld%lld",&n,&m);
for(LL i=0; i<=n; i++) {
scanf("%lld",a+i);
}
for(LL i=0; i<=m; i++) {
scanf("%lld",b+i);
}
for(m+=n,n=1; n<=m; n<<=1);
for(LL i=0; i<n; i++) {
tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
}
NTT(a,1),NTT(b,1);
for(LL i=0; i<n; i++) {
a[i]=a[i]*b[i]%mod;
}
NTT(a,0),iN=mi(n);
for(LL i=0; i<=m; i++) {
printf("%lld ",a[i]*iN%mod);
}
}
KMP 字符串匹配
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+2;
int kmp[N]= {0};
char a[N],b[N];
int main() {
scanf("%s%s",a+1,b+1);
int la=strlen(a+1),lb=strlen(b+1),j=0;
for(int i=2; i<=lb; i++) {
while(j>0&&(b[i]^b[j+1])) {
j=kmp[j];
}
if(b[i]==b[j+1]) {
j++;
}
kmp[i]=j;
}
j=0;
for(int i=1; i<=la; i++) {
while(j>0&&(a[i]^b[j+1])) {
j=kmp[j];
}
if(a[i]==b[j+1]) {
j++;
}
if(j==lb) {
printf("%d
",i-lb+1);
j=kmp[j];
}
}
for(int i=1; i<=lb; i++) {
printf("%d ",kmp[i]);
}
return 0;
}
差分约束算法
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
struct edge {
int v,w,nxt;
} e[N];
int n,m,head[N],cnt,dis[N],tot[N];
bitset<N> vis;
void add(int u,int v,int w) {
e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
}
bool spfa(int s) {
queue<int> q;
memset(dis,63,sizeof(dis));
dis[s]=0,vis[s]=1;
q.push(s);
while(q.size()) {
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u]; i; i=e[i].nxt) {
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w) {
dis[v]=dis[u]+e[i].w;
if(!vis[v]) {
vis[v]=1,tot[v]++;
if(tot[v]==n+1) {
return 0;
}
q.push(v);
}
}
}
}
return 1;
}
int main() {
scanf("%d %d",&n,&m);
for(int i=1; i<=n; i++) {
add(0,i,0);
}
for(int i=1,v,u,w; i<=m; i++) {
scanf("%d %d %d",&v,&u,&w),add(u,v,w);
}
if(!spfa(0)) {
puts("NO");
return 0;
}
for(int i=1; i<=n; i++) {
printf("%d ",dis[i]);
}
return 0;
}
网络最大流
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
const LL N=1002,M=5002,inf=1e9;
struct edge {
LL to,nxt,w;
} e[M<<1];
LL n,m,s,t,cnt=1,head[N],d[N];
void add(int u,int v,int w) {
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt,e[cnt].w=w;
}
bool bfs() {
queue<LL> q;
q.push(s);
for(int i=1; i<=n; i++) {
d[i]=inf;
}
d[s]=0;
while(q.size()) {
LL x=q.front();
q.pop();
for(LL i=head[x]; i; i=e[i].nxt) {
LL v=e[i].to;
if(e[i].w&&d[v]==inf) {
q.push(v),d[v]=d[x]+1;
if(v==t) {
return 1;
}
}
}
}
return 0;
}
LL dfs(LL x,LL sum) {
if(x==t) {
return sum;
}
LL res=0;
for(int i=head[x]; i&∑ i=e[i].nxt) {
int v=e[i].to;
if(e[i].w>0&&d[v]==d[x]+1) {
int k=dfs(v,min(sum,e[i].w));
if(!k) {
d[v]=inf;
}
e[i].w-=k,e[i^1].w+=k,res+=k,sum-=k;
}
}
return res;
}
int main() {
scanf("%lld %lld %lld %lld",&n,&m,&s,&t);
for(LL i=1,u,v,w; i<=m; i++) {
scanf("%lld %lld %lld",&u,&v,&w),add(u,v,w),add(v,u,0);
}
LL ans=0;
while(bfs()) {
ans+=dfs(s,inf);
}
printf("%lld",ans);
return 0;
}
卢卡斯定理
#include<bits/stdc++.h>
#define N 100010
using namespace std;
using LL=long long;
LL p,a[N];
LL pow(LL x,LL y) {
x%=p;
LL ans=1;
while(y) {
if(y&1) {
ans=ans*x%p;
}
x=x*x%p,y>>=1;
}
return ans;
}
LL C(LL n,LL m) {
if(m>n) {
return 0;
}
return (a[n]*pow(a[m],p-2))%p*pow(a[n-m],p-2)%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() {
LL T;
scanf("%lld",&T);
while(T--) {
LL n,m;
scanf("%lld %lld %lld",&n,&m,&p);
a[0]=1;
for(LL i=1; i<=p; i++) {
a[i]=(a[i-1]*i)%p;
}
printf("%lld
",Lucas(n+m,n));
}
}
树状数组 2
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+2;
int n,tr[N<<2];
inline int lowbit(int x) {
return x&(-x);
}
void add(int p,int del) {
while(p<=n) {
tr[p]+=del;
p+=lowbit(p);
}
}
int query(int p) {
int sum=0;
while(p>0) {
sum+=tr[p];
p-=lowbit(p);
}
return sum;
}
int main() {
int m;
scanf("%d %d",&n,&m);
int lst=0;
for(int i=1,x; i<=n; i++) {
scanf("%d",&x);
add(i,x-lst);
lst=x;
}
while(m--) {
int op,x,y,k;
scanf("%d %d",&op,&x);
if(op^2) {
scanf("%d %d",&y,&k);
add(x,k),add(y+1,-k);
} else {
printf("%d
",query(x));
}
}
return 0;
}
线性筛素数
#include<bits/stdc++.h>
using namespace std;
const int N=1e8+5;
int cnt,p[N];
bitset<N> is;
int main() {
int n,q;
scanf("%d %d",&n,&q);
for(int i=2; i<=n; i++) {
if(!is[i]) {
p[++cnt]=i;
}
for(int j=1; j<=cnt; j++) {
if(1LL*i*p[j]>=N) {
break;
}
is[i*p[j]]=1;
if(i*p[j]==0) {
break;
}
}
}
while(q--) {
int k;
scanf("%d",&k),printf("%d
",p[k]);
}
return 0;
}
AC 自动机
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
int n;
int tr[N][26],tot,e[N],fail[N];
void insert(char *s) {
int u=0;
for(int i=1; s[i]; i++) {
if(!tr[u][s[i]-'a']) {
tr[u][s[i]-'a']=++tot;
}
u=tr[u][s[i]-'a'];
}
e[u]++;
}
void build() {
queue<int> q;
for(int i=0; i<26; i++) {
if(tr[0][i]) {
q.push(tr[0][i]);
}
}
while(q.size()) {
int u=q.front();
q.pop();
for(int i=0; i<26; i++) {
if(tr[u][i]) {
fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
} else {
tr[u][i]=tr[fail[u]][i];
}
}
}
}
int query(char *s) {
int u=0,res=0;
for(int i=1; s[i]; i++) {
u=tr[u][s[i]-'a'];
for(int j=u; j&&e[j]^-1; j=fail[j]) {
res+=e[j],e[j]=-1;
}
}
return res;
}
char s[N];
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%s",s+1),insert(s);
}
build(),scanf("%s",s+1),printf("%d",query(s));
return 0;
}
二分图最大匹配
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,e,ans,match[N];
bool a[N][N],vis[N];
bool dfs(int x) {
for(int i=1; i<=m; i++) {
if(!vis[i]&&a[x][i]) {
vis[i]=1;
if(!match[i]||dfs(match[i])) {
match[i]=x;
return 1;
}
}
}
return 0;
}
int main() {
scanf("%d %d %d",&n,&m,&e);
for(int i=1,u,v; i<=e; i++) {
scanf("%d %d",&u,&v),a[u][v]=1;
}
for (int i=1; i<=n; i++){
ans+=dfs(i);
memset(vis,0,sizeof(vis));
}
printf("%d",ans);
return 0;
}
可持久化线段树 1
#include<bits/stdc++.h>
using namespace std;
struct abc {
int l,r,val;
} tree[1000001<<5];
int top,a[1000005],root[1000005];
int New(int node) {
tree[++top]=tree[node];
return top;
}
int build(int node,int begin,int end) {
node=++top;
if(begin==end) {
tree[node].val=a[begin];
return top;
}
int mid=(begin+end)>>1;
tree[node].l=build(tree[node].l,begin,mid);
tree[node].r=build(tree[node].r,mid+1,end);
return node;
}
int update(int node,int begin,int end,int x,int val) {
node=New(node);
if(begin==end) {
tree[node].val=val;
} else {
int mid=(begin+end)>>1;
if(x<=mid) {
tree[node].l=update(tree[node].l,begin,mid,x,val);
} else {
tree[node].r=update(tree[node].r,mid+1,end,x,val);
}
}
return node;
}
int query(int node,int begin,int end,int x) {
if(begin==end) {
return tree[node].val;
} else {
int mid=(begin+end)>>1;
if(x<=mid) {
return query(tree[node].l,begin,mid,x);
} else {
return query(tree[node].r,mid+1,end,x);
}
}
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i=1; i<=n; i++) {
scanf("%d",a+i);
}
root[0]=build(0,1,n);
for(int i=1,rt,mode,x; i<=m; i++){
scanf("%d %d %d",&rt,&mode,&x);
if(mode==1) {
int y;
scanf("%d",&y);
root[i]=update(root[rt],1,n,x,y);
} else {
printf("%d
",query(root[rt],1,n,x));
root[i]=root[rt];
}
}
}
ST表
#include<bits/stdc++.h>
using namespace std;
int f[100005][40];
inline int ask(int l,int r) {
int k=(int)(log(r-l+1)/log(2));
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main() {
int n,m;
scanf("%d %d",&n,&m);
for(int i=1; i<=n; i++) {
scanf("%d",f[i]);
}
int t=log2(n);
for(int j=1; j<=t; j++) {
for (int i=1; i<=n-(1<<j)+1; i++) {
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
for(int i=1,l,r; i<=m; i++) {
scanf("%d %d",&l,&r);
printf("%d
",ask(l,r));
}
return 0;
}
nim 游戏
#include<bits/stdc++.h>
using namespace std;
int main() {
int T;
scanf("%d",&T);
while(T--) {
int n;
scanf("%d",&n);
int tmp;
scanf("%d",&tmp);
for(int i=1; i<n; i++) {
int x;
scanf("%d",&x),tmp^=x;
}
if(tmp) {
puts("Yes");
} else {
puts("No");
}
}
return 0;
}
乘法逆元
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int ans=0,f=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') {
f=-1;
}
c=getchar();
}
while(c>='0'&&c<='9') {
ans=(ans<<3)+(ans<<1)+(c-'0');
c=getchar();
}
return ans*f;
}
inline void print(int x) {
if(x<0) {
x*=-1,putchar('-');
}
if(x>9) {
print(x/10);
}
putchar(x%10+'0');
}
int ans[3000005]= {0,1};
int main() {
int n=read(),p=read();
putchar('1'),putchar('
');
for(int i=2; i<=n; i++) {
ans[i]=1LL*(p-p/i)*ans[p%i]%p;
print(ans[i]),putchar('
');
}
}
