板子合集
WeLikeStudying · · 个人记录
计算几何
二维凸包
#include<bits/stdc++.h>
#define up(a,b,c) for(int a=b;a<=c;++a)
const int N=11e4;
using namespace std;
int n,m;
double rs;
struct ppt
{
double x,y;
void inp()
{
cin>>x>>y;
}
ppt operator - (ppt b)
{
return {x-b.x,y-b.y};
}
double sq()
{
return sqrt(x*x+y*y);
}
double operator * (ppt b)
{
return x*b.y-y*b.x;
}
}e[N];
bool cmp(ppt a,ppt b)
{
double x=(a-e[1])*(b-e[1]);
return x==0?(a-e[1]).sq()<(b-e[1]).sq():x>0;
}
int main()
{
cin>>n;
up(i,1,n)
{
e[i].inp();
if(e[i].x<e[1].x||(e[i].x==e[1].x&&e[i].y>e[1].y))swap(e[i],e[1]);
}
sort(e+2,e+n+1,cmp);
m=1;
up(i,2,n)
{
while(m>1&&(e[i]-e[m])*(e[m]-e[m-1])>=0)--m;
swap(e[++m],e[i]);
}
up(i,1,m)rs+=(e[i]-e[i%m+1]).sq();
printf("%.2lf",rs);
return 0;
} 半平面交
#include<bits/stdc++.h>
#define up(a,b,c)for(int a=b;a<=c;++a)
const int N=55e4;
using namespace std;
struct pt
{
double x,y;
pt operator-(const pt &b)const{return {x-b.x,y-b.y};}
double operator*(const pt &b)const
{
return x*b.y-y*b.x;
}
double arg() const
{
return atan2(y,x);
}
void in()
{
cin>>x>>y;
}
}p[N],q[N];
double xt(const pt &o,const pt &a,const pt &b)
{
return (a-o)*(b-o);
}
struct ln
{
pt s,e;
double ag;
double arg() const
{
return ag;
}
void in(pt S,pt E)
{
e=E,s=S,ag=(E-S).arg();
}
bool operator < (const ln &B) const
{
if(ag==B.ag)
return xt(s,B.s,B.e)>0;
return ag<B.ag;
}
pt operator * (const ln &B) const
{
double S1=xt(s,B.e,e),S2=xt(s,B.s,e);
return {(S1*B.s.x-S2*B.e.x)/(S1-S2),(S1*B.s.y-S2*B.e.y)/(S1-S2)};
}
}e[N],dq[N];
bool ck(const ln &A,const ln &B,const ln &C)
{
return xt(B*C,A.s,A.e)<0;
}
int n,m,s,l;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
{
int n,m;cin>>n;
while(n--)
{
cin>>m;
up(i,1,m)p[i].in();
up(i,1,m)e[++::n].in(p[i],p[i%m+1]);
}
}
sort(e+1,e+n+1);
m=1;
up(i,2,n)
if(e[i].arg()>e[i-1].arg())
e[++m]=e[i];
s=2,l=1;
dq[1]=e[1];
dq[2]=e[2];
up(i,3,m)
{
while(l<s&&ck(e[i],dq[s],dq[s-1]))--s;
while(l<s&&ck(e[i],dq[l],dq[l+1]))++l;
dq[++s]=e[i];
}
while(l<s&&ck(dq[l],dq[s],dq[s-1]))--s;
while(l<s&&ck(dq[s],dq[l],dq[l+1]))++l;
up(i,l,s-1)q[i-l+1]=dq[i]*dq[i+1];
if(s-l>1)q[s-l+1]=dq[s]*dq[l],m=s-l+1;
else m=0;
double ans=0;
up(i,1,m)ans+=q[i]*q[i%m+1];
cout<<fixed<<setprecision(3)<<ans/2.;
return 0;
}闵可夫斯基和
#include<bits/stdc++.h>
#define up(a,b,c) for(int a=b;a<=c;++a)
const int N=11e4;
using namespace std;
int n,m,k,tp,tt;
struct pt
{
double x,y;
void in()
{
cin>>x>>y;
}
pt operator + (pt b)
{
return {x+b.x,y+b.y};
}
pt operator - (pt b)
{
return {x-b.x,y-b.y};
}
double operator ^ (pt b)
{
return x*b.x+y*b.y;
}
double operator * (pt b)
{
return x*b.y-y*b.x;
}
double sq()
{
return sqrt(x*x+y*y);
}
}o,p[N],q[N],f[N],g[N],A[N];
bool cmp(pt a,pt b)
{
double x=(a-o)*(b-o);
return x==0?(a-o).sq()<(b-o).sq():x>0;
}
void conv(pt *e,int &n)
{
up(i,1,n)
if(e[i].x<e[1].x||(e[i].x==e[1].x&&e[i].y>e[1].y))swap(e[i],e[1]);
o=e[1],sort(e+2,e+n+1,cmp);
int m=1;
up(i,2,n)
{
while(m>1&&(e[i]-e[m])*(e[m]-e[m-1])>=0)--m;
swap(e[++m],e[i]);
}
n=m;
}
void mkfsj()
{
up(i,1,n)f[i]=p[i%n+1]-p[i];
up(i,1,m)g[i]=q[i%m+1]-q[i];
A[tt=1]=p[1]+q[1];
int s=1,l=1;o={0,0};
while(s<=n&&l<=m)++tt,A[tt]=A[tt-1]+(cmp(f[s],g[l])?f[s++]:g[l++]);
while(s<=n)++tt,A[tt]=A[tt-1]+f[s++];
while(l<=m)++tt,A[tt]=A[tt-1]+g[l++];
conv(A,tt);
}
bool li(pt a)
{
if(a*A[2]>0||(a*A[2]==0&&a.sq()>A[2].sq()))return 0;
if(a*A[tt]<0||(a*A[tt]==0&&a.sq()>A[tt].sq()))return 0;
int i=lower_bound(A+2,A+tt+1,a,cmp)-A-1;
return (a-A[i])*(A[i%tt+1]-A[i])<=0;
}
int main()
{
cin>>n>>m>>k;
up(i,1,n)p[i].in();conv(p,n);
o={0,0};up(i,1,m)q[i].in(),q[i]=o-q[i];conv(q,m);
mkfsj(),o={0,0};
pt e=A[1];up(i,1,tt)A[i]=A[i]-e;
while(k--)A[0].in(),cout<<li(A[0]-e)<<'\n';
return 0;
}字符串
KMP
#include<fstream>
#include<cstring>
const int N=1100000;
using namespace std;
int n,m,fl[N];
char s[N],t[N];
int main()
{
scanf("%s%s",t,s);
n=strlen(t),m=strlen(s);
int k=fl[0]=fl[1]=0;
for(int i=2;i<=m;++i)
{
while(k&&s[i-1]!=s[k])k=fl[k];
if(s[i-1]==s[k])++k;
fl[i]=k;
}
k=0;
for(int i=1;i<=n;++i)
{
while(k&&t[i-1]!=s[k])k=fl[k];
if(t[i-1]==s[k])++k;
if(k==m)printf("%d\n",i-m+1),k=fl[k];
}
for(int i=1;i<=m;++i)printf("%d ",fl[i]);
return 0;
} Z 函数
#include<fstream>
#include<cstring>
const int N=22000000;
using namespace std;
int n,m,z[N],p[N];
char t[N],s[N];
inline void Z_fuc(char *s,char *t,int *p,int n,int m)
{
*p=0;
while(*p<n&&*p<m&&t[*p]==s[*p])++(*p);
for(int i=1,l=0,r=1;i<n;++i)
{
p[i]=i+z[i-l]<r?z[i-l]:max(0,r-i);
while(p[i]<m&&i+p[i]<n&&t[p[i]]==s[i+p[i]])++p[i];
if(i+p[i]>r)l=i,r=i+p[i];
}
}
inline void print(int *p,int n)
{
long long ans=0;
for(int i=0;i<n;++i)ans^=1ll*(i+1)*(p[i]+1);
printf("%lld\n",ans);
}
int main()
{
scanf("%s%s",t,s);
n=strlen(t),m=strlen(s);
Z_fuc(s,s,z,m,m);print(z,m);
Z_fuc(t,s,p,n,m);print(p,n);
return 0;
} manacher
#include<fstream>
#include<cstring>
const int N=23000000;
using namespace std;
int n,d[N];
char s[N];
int main()
{
scanf("%s",s);n=strlen(s);
for(int i=n-1;i>=0;--i)s[i<<1|1]=s[i];
for(int i=0;i<=n;++i)s[i<<1]='\0';
n=n<<1|1;
for(int i=0,x=0,r=0;i<n;++i)
if(i<r&&i+d[(x<<1)-i]<r)d[i]=d[(x<<1)-i];
else
{
d[i]=max(0,r-i);
while(d[i]<=i&&i+d[i]<n&&s[i-d[i]]==s[i+d[i]])++d[i];
x=i,r=i+d[i]-1;
}
int ans=0;
for(int i=0;i<n;++i)ans=max(ans,d[i]-1);
printf("%d",ans);
return 0;
}AC 自动机
#include<fstream>
const int N=1100000,L=26;
using namespace std;
int n,rt,ans,nd,st,fl[N],g[N],sn[N][L],qwq[N];
bool ok[N];
char s[N];
void insert(char *s)
{
int *u=&rt;
while(*s!='\0')
{
if(!*u)*u=++nd;
u=&sn[*u][*s-'a'];
++s;
}
if(!*u)*u=++nd;
++g[*u];
}
void ac_auto()
{
int l=0,r=1;
fl[rt]=rt;
for(int j=0;j<L;++j)
if(sn[rt][j])fl[qwq[r++]=sn[rt][j]]=rt;
else sn[rt][j]=rt;
while(l<r)
for(int j=0,u=qwq[l++];j<L;++j)
if(sn[u][j])
fl[qwq[r++]=sn[u][j]]=sn[fl[u]][j];
else
sn[u][j]=sn[fl[u]][j];
}
void run(char *s)
{
int u=rt;
while(*s!='\0')
{
u=sn[u][*(s++)-'a'];
for(int z=u;!ok[z]&&z!=fl[z];z=fl[z])
ans+=g[z],ok[z]=1;
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;++i)
{
scanf("%s",s);
insert(s);
}
ac_auto();
scanf("%s",s);
run(s);
printf("%d",ans);
return 0;
} 后缀数组
#include<fstream>
#include<cstring>
#include<algorithm>
const int N=55000,L=16;
using namespace std;
int n;
struct SA
{
char s[N];
int sa[N],rk[N],h[N],bu[N],c[N],lg[N],mx[N][L];
bool cmp(int i,int j)
{
return rk[i]==rk[j]?c[i]<c[j]:rk[i]<rk[j];
}
void sort(int k)
{
fill(bu,bu+k+1,0);
for(int j=0;j<n;++j)++bu[rk[sa[j]]];
for(int j=1;j<=k;++j)bu[j]+=bu[j-1];
for(int j=n-1;j>=0;--j)c[--bu[rk[sa[j]]]]=sa[j];
copy(c,c+n,sa);
}
void calc()
{
for(int i=0;i<n;++i)sa[i]=i,rk[i]=s[i]-'a';
sort(1);fill(c,c+n,0);
for(int i=1,k;i<n;i<<=1)
{
k=0;
for(int j=0;j<n;++j)
rk[sa[j]]=j+1<n&&cmp(sa[j],sa[j+1])?k++:k;
if(k==n)continue;
for(int j=0;j<i;++j)c[j]=n-i+j;
for(int j=0,t=i;j<n;++j)
if(sa[j]>=i)c[t++]=sa[j]-i;
copy(c,c+n,sa);sort(k);
for(int j=0;j<n;++j)
c[j]=i+j<n?rk[i+j]+1:0;
}
for(int i=0;i<n;++i)rk[sa[i]]=i;
for(int i=0,k=0;i<n;++i)
{
if(!rk[i])continue;
if(k)--k;
int pe=sa[rk[i]-1];
while(i+k<n&&pe+k<n&&s[i+k]==s[pe+k])++k;
h[rk[i]]=k;
}
lg[0]=-1;
for(int i=1;i<=n;++i)lg[i]=lg[i>>1]+1,mx[i-1][0]=h[i-1];
for(int i=1;i<=lg[n];++i)
for(int j=0;j+(1<<i)<=n;++j)
mx[j][i]=min(mx[j][i-1],mx[j+(1<<i-1)][i-1]);
}
int LCP(int x,int y)
{
int l=rk[x],r=rk[y];
if(l>r)swap(l,r);
int L=lg[r-l];
return min(mx[l+1][L],mx[r-(1<<L)+1][L]);
}
}lcp,lcs;
void solve()
{
scanf("%d",&n);
for(int i=0;i<n;++i)
scanf(" %c",&lcp.s[i]);
copy(lcp.s,lcp.s+n,lcs.s);
reverse(lcs.s,lcs.s+n);
lcp.calc(),lcs.calc();
int res=1;
for(int i=1;i<=n;++i)
for(int j=0;j+i<n;j+=i)
res=max(res,(lcp.LCP(j,j+i)+lcs.LCP(n-j-1,n-j-i-1)-1)/i+1);
printf("%d\n",res);
}
int main()
{
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}PAM
#include<bits/stdc++.h>
const int N=550000;
using namespace std;
int n,nd,nw,fl[N],len[N],dep[N],sn[N][26];
char s[N];
int main()
{
scanf("%s",s),n=strlen(s);
len[0]=-1,nd=1;
for(int i=0,la=0;i<n;++i)
{
s[i]=(s[i]-97+la)%26;
int k=nw;
while(len[k]>=i||s[i-len[k]-1]!=s[i])k=fl[k];
if(sn[k][s[i]])la=dep[nw=sn[k][s[i]]];
else
{
len[nw=++nd]=len[k]+2;
int &g=sn[k][s[i]];
do k=fl[k];while(s[i-len[k]-1]!=s[i]);
if(sn[k][s[i]])fl[nd]=sn[k][s[i]];
else fl[nd]=1;
la=dep[nd]=dep[fl[nd]]+1,g=nd;
}
printf("%d ",la);
}
return 0;
}图论
单源最短路
#include<bits/stdc++.h>
const int N=4e5;
const long long inf=1ll<<61;
using namespace std;
int n,m,s;
long long f[N];
#define ccf pair<long long,int>
#define w first
#define v second
#define ee(a,b) make_pair(a,b)
vector<ccf>to[N];
priority_queue<ccf,vector<ccf>,greater<ccf>>noi;
int main()
{
cin>>n>>m>>s;
for(int i=1;i<=m;++i)
{
int u,v,w;cin>>u>>v>>w;
to[u].push_back(ee(w,v));
}
fill(f,f+n+1,inf);
noi.push(ee(f[s]=0,s));
while(!noi.empty())
{
int u=noi.top().v;
long long w=noi.top().w;
noi.pop();
if(f[u]==w)
for(auto z:to[u])
if(f[z.v]>w+z.w)
noi.push(ee(f[z.v]=w+z.w,z.v));
}
for(int i=1;i<=n;++i)cout<<(f[i]<inf?f[i]:-1)<<' ';
return 0;
}差分约束
#include<fstream>
const int N=5500,M=11000,INF=1000000000;
using namespace std;
int n,m,tl;
long long dis[N];
struct edge
{
int u,v,w;
}e[M];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)dis[i]=INF;
dis[0]=0;
for(tl=0;tl<n;++tl)
e[tl].u=0,e[tl].v=tl+1,e[tl].w=0;
for(int i=0;i<m;++i)
scanf("%d%d%d",&e[tl+i].v,&e[tl+i].u,&e[tl+i].w);
tl+=m;
int i;
for(i=0;i<=n;++i)
{
bool p=0;
for(int j=0;j<tl;++j)
if(dis[e[j].u]<INF&&dis[e[j].v]>dis[e[j].u]+e[j].w)
dis[e[j].v]=dis[e[j].u]+e[j].w,p=1;
if(!p)break;
}
if(i<=n)
for(int j=1;j<=n;++j)
printf("%lld ",dis[j]);
else printf("NO");
return 0;
} 欧拉回路
#include<bits/stdc++.h>
const int N=22e4;
using namespace std;
int t,n,m,u[N],v[N];
bool vis[N];
vector<int>to[N],res;
void dfs(int U)
{
int x,z,V;
while(!to[U].empty())
{
z=to[U].back(),to[U].pop_back();
if(!vis[x=abs(z)])
vis[x]=1,V=u[x]^U^v[x],dfs(V),res.push_back(z);
}
}
int main()
{
scanf("%d%d%d",&t,&n,&m);
int x=0,y,g;
for(int i=1;i<=m;++i)
{
scanf("%d%d",&u[i],&v[i]),x=u[i];
to[u[i]].push_back(i);
if(t==1)to[v[i]].push_back(-i);
}
dfs(y=x);
bool ok=0;
for(int z:res)
{
g=abs(z);
if(z<0&&y!=u[g])ok=1;
if(z>0&&y!=v[g])ok=1;
y^=u[g]^v[g];
}
if(res.size()<m||ok||y!=x)puts("NO");
else
{
puts("YES");
while(!res.empty())
printf("%d ",res.back()),res.pop_back();
}
return 0;
}点双
#include<bits/stdc++.h>
#define up(a,b,c) for(int a=b;a<=c;++a)
const int N=55e4;
using namespace std;
int n,m,tp,ddd,bcc,dfn[N],low[N],stk[N];
vector<int>to[N],qwq[N];
void dfs(int u)
{
dfn[u]=low[u]=++ddd,stk[++tp]=u;
for(int v:to[u])
{
if(!dfn[v])
{
dfs(v),low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
++bcc;
while(stk[tp+1]!=v)
qwq[bcc].push_back(stk[tp--]);
qwq[bcc].push_back(u);
}
}
else low[u]=min(low[u],dfn[v]);
}
if(to[u].empty())qwq[++bcc].push_back(u);
}
int main()
{
cin>>n>>m;
while(m--)
{
int u,v;
cin>>u>>v;
if(u!=v)
to[u].push_back(v),
to[v].push_back(u);
}
up(i,1,n)if(!dfn[i])dfs(i);
cout<<bcc;
up(i,1,bcc)
{
cout<<'\n'<<qwq[i].size();
for(int x:qwq[i])
cout<<' '<<x;
}
return 0;
}边双
#include<bits/stdc++.h>
#define up(a,b,c) for(int a=b;a<=c;++a)
const int N=55e4,M=22e5;
using namespace std;
int n,m,tp,ddd,dcc,r,x[M],y[M],dfn[N],low[N],bel[N],stk[N],qwq[N];
vector<int>to[N];
void dfs(int u,int la)
{
low[u]=dfn[u]=++ddd,stk[++tp]=u;
for(int z:to[u])
{
int v=u^x[z]^y[z];
if(!dfn[v])dfs(v,z),low[u]=min(low[u],low[v]);
else if(z!=la)low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
++dcc;
while(stk[tp+1]!=u)
bel[qwq[r++]=stk[tp--]]=dcc;
}
}
int main()
{
cin>>n>>m;
up(i,1,m)
cin>>x[i]>>y[i],
to[x[i]].push_back(i),
to[y[i]].push_back(i);
up(i,1,n)
if(!dfn[i])dfs(i,0);
cout<<dcc;
for(int i=0,j=1;i<r;i=j)
{
while(j<r&&bel[qwq[i]]==bel[qwq[j]])++j;
cout<<'\n'<<j-i;
up(z,i,j-1)cout<<' '<<qwq[z];
}
return 0;
}缩点
#include<bits/stdc++.h>
const int N=11e3;
using namespace std;
struct Tarjan
{
int ddd,ins[N],low[N],dfn[N],scc,fo[N];
vector<int>to[N],used;
stack<int>pts;
void reset()
{
ddd=scc=0;
for(int u:used)
dfn[u]=0,to[u].clear();
used.clear();
}
void add(int u,int v)
{
used.push_back(u),
used.push_back(v),
to[u].push_back(v);
}
void dfs(int u)
{
dfn[u]=low[u]=++ddd,ins[u]=1,pts.push(u);
for(int v:to[u])
if(!dfn[v])
dfs(v),low[u]=min(low[u],low[v]);
else
if(ins[v])
low[u]=min(low[u],dfn[v]);
if(dfn[u]==low[u])
{
int v;
while((v=pts.top())!=u)
fo[v]=scc,ins[v]=0,pts.pop();
fo[u]=scc,ins[u]=0,pts.pop(),++scc;
}
}
void run()
{
for(int u:used)
if(!dfn[u])dfs(u);
}
}T;
int a[N],sm[N];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
while(m--)
{
int u,v;scanf("%d%d",&u,&v);
T.add(u,v);
}
T.run();
for(int i=1;i<=n;++i)
assert(dfn[i]),sm[T.fo[i]]+=a[i];
int res=0;
for(int i=0;i<T.scc;++i)
res=max(sm[i],res);
printf("%d",res);
return 0;
}割点
#include<fstream>
const int N=22000,M=110000;
using namespace std;
int n,m,nm,hd[N],dfn[N],low[N];
bool pig[N];
struct edge
{
int to,nt;
}e[M<<1];
void add(int u,int v)
{
static int tl=0;
++tl;
e[tl].to=v,e[tl].nt=hd[u];
hd[u]=tl;
}
int D=0;
void dfs(int u,int f)
{
low[u]=dfn[u]=++D;
int c=0;
for(int z=hd[u];z;z=e[z].nt)
{
int v=e[z].to;
if(!dfn[v])
{
dfs(v,u);
if(u==f)++c;
else
if(low[v]>=dfn[u])pig[u]=1;
low[u]=min(low[u],low[v]);
}
else
if(v!=f)low[u]=min(low[u],dfn[v]);
}
if(c>1&&u==f)pig[u]=1;
if(pig[u])++nm;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
for(int i=1;i<=n;++i)
if(!dfn[i])dfs(i,i);
printf("%d\n",nm);
for(int i=1;i<=n;++i)
if(pig[i])printf("%d ",i);
return 0;
}2-SAT
#include<fstream>
const int B=1100000;
using namespace std;
int n,m,hd[B<<1],dfn[B<<1],low[B<<1],wt[B<<1],stk[B<<1],ans[B],dzd,scc,top;
bool ins[B<<1],ok;
struct edge
{
int to,nt;
}e[B<<1];
void add(int u,int v)
{
static int tl=0;
++tl;
e[tl].to=v,e[tl].nt=hd[u];
hd[u]=tl;
}
void dfs(int u)
{
low[u]=dfn[u]=++dzd,ins[u]=1,stk[top++]=u;
for(int z=hd[u];z;z=e[z].nt)
{
int v=e[z].to;
if(!dfn[v])
{
dfs(v);
low[u]=min(low[u],low[v]);
}
else
if(ins[v])low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
while(stk[--top]!=u)
{
int v=stk[top];
ins[v]=0,wt[v]=scc;
}
ins[u]=0,wt[u]=scc++;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i)
{
int u,v,ou,ov;
scanf("%d%d%d%d",&u,&ou,&v,&ov);
add(u<<1|(!ou),v<<1|ov),
add(v<<1|(!ov),u<<1|ou);
}
for(int i=2;i<=(n<<1|1);++i)
if(!dfn[i])dfs(i);
ok=1;
// for(int i=2;i<=(n<<1|1);++i)printf("%d? ",wt[i]);
for(int i=1;i<=n&&ok;++i)
if(wt[i<<1]==wt[i<<1|1])ok=0;
else ans[i]=(wt[i<<1|1]<wt[i<<1]);
if(!ok)puts("IMPOSSIBLE");
else
{
puts("POSSIBLE");
for(int i=1;i<=n;++i)
printf("%d ",ans[i]);
}
return 0;
} 网络流
struct Dicnic
{
int n,nd,s,t,hd[N],hu[N],lvl[N],qwq[N];
const int inf=(1u<<31)-1;
struct edge
{
int v,c,nt;
}e[M];
void reset()
{
fill(hd,hd+n,-1),nd=0;
}
void add(int u,int v,int c)
{
e[nd]={v,c,hd[u]},hd[u]=nd++,
e[nd]={u,0,hd[v]},hd[v]=nd++;
}
bool bfs()
{
int l=0,r=1;
fill(lvl,lvl+n,inf),copy(hd,hd+n,hu),qwq[0]=s,lvl[s]=0;
while(l<r)
for(int u=qwq[l++],z=hd[u],v;~z;z=e[z].nt)
if(e[z].c&&lvl[u]+1<lvl[v=e[z].v])
lvl[v]=lvl[u]+1,qwq[r++]=v;
return lvl[t]<inf;
}
int dfs(int u,int fl)
{
if(u==t)return fl;
int sm=0;
for(int &z=hu[u],v;~z;z=e[z].nt)
if(e[z].c&&lvl[u]+1==lvl[v=e[z].v])
{
int c=dfs(v,min(fl,e[z].c));
fl-=c,sm+=c,e[z].c-=c,e[z^1].c+=c;
if(!fl)break;
}
return sm;
}
int flow()
{
int ans=0;
while(bfs())ans+=dfs(s,inf);
return ans;
}
}D;最小费用流
#include<bits/stdc++.h>
using ll=long long;
const int N=55e3,M=N*10;
const ll inf=1ll<<62;
using namespace std;
int n,m,s,t,nd,flow,hd[N],hu[N];
ll d[N],h[N],cost;
struct edge
{
int v,w,c,nt;
}e[M];
struct ee
{
ll w;
int u;
bool operator < (ee b) const
{
return b.w<w;
}
};
priority_queue<ee>qwq;
void add()
{
int u,v,w,c;scanf("%d%d%d%d",&u,&v,&w,&c);
e[nd]={v,w,c,hd[u]},hd[u]=nd++,
e[nd]={u,0,-c,hd[v]},hd[v]=nd++;
}
bool bfs()
{
copy(hd,hd+n+1,hu),fill(d,d+n+1,inf);
qwq.push({d[s]=0,s});
while(!qwq.empty())
{
int u=qwq.top().u;ll w=qwq.top().w;qwq.pop();
if(d[u]<w)continue;
for(int z=hd[u];z!=-1;z=e[z].nt)
if(e[z].w&&d[e[z].v]>w+h[u]-h[e[z].v]+e[z].c)
d[e[z].v]=w+e[z].c+h[u]-h[e[z].v],
qwq.push({d[e[z].v],e[z].v});
}
return d[t]<inf;
}
bool ins[N];
int dfs(int u,int fl)
{
if(!fl||u==t)return fl;
int sm=0;ins[u]=1;
for(int &z=hu[u];z!=-1;z=e[z].nt)
if(e[z].w&&!ins[e[z].v]&&d[u]+h[u]+e[z].c-h[e[z].v]==d[e[z].v])
{
int c=dfs(e[z].v,min(fl,e[z].w));
e[z].w-=c,e[z^1].w+=c,cost+=1ll*c*e[z].c,sm+=c,fl-=c;
if(!fl)break;
}ins[u]=0;
return sm;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
fill(hd,hd+n+1,-1),fill(d,d+n+1,inf);
while(m--)add();
while(bfs())
{
flow+=dfs(s,1<<30);
for(int i=1;i<=n;++i)h[i]+=d[i];
}
printf("%d %lld\n",flow,cost);
return 0;
}无源汇有上下界可行流
#include<bits/stdc++.h>
const int N=333,M=33333,INF=2147483647;
using namespace std;
int n,m,s,t,nd,d[N],to[N],hd[N],hu[N],lvl[N],qwq[N];
struct edge
{
int to,nt,cap;
}e[M];
void add(int u,int v,int cap)
{
e[nd]={v,hd[u],cap};hd[u]=nd++;
e[nd]={u,hd[v],0};hd[v]=nd++;
}
struct que
{
int u,v,l,r;
void read()
{
scanf("%d%d%d%d",&u,&v,&l,&r);
d[u]-=l,d[v]+=l;add(u,v,r-l);
}
}q[M];
bool bfs()
{
copy(hd,hd+n+2,hu);fill(lvl,lvl+n+2,INF);
int l=0,r=0;qwq[r++]=s,lvl[s]=0;
while(l<r)
for(int u=qwq[l++],z=hd[u];~z;z=e[z].nt)
{
int v=e[z].to;
if(lvl[u]+1<lvl[v]&&e[z].cap>0)
lvl[v]=lvl[u]+1,qwq[r++]=v;
}
return lvl[t]<INF;
}
int dfs(int u,int f)
{
if(u==t||!f)return f;
int sm=0;
for(int &z=hu[u];~z;z=e[z].nt)
{
int v=e[z].to;
if(lvl[u]+1==lvl[v]&&e[z].cap>0)
{
int c=dfs(v,min(f,e[z].cap));
e[z].cap-=c,e[z^1].cap+=c,sm+=c,f-=c;
}
if(!f)break;
}
return sm;
}
int main()
{
scanf("%d%d",&n,&m);
fill(hd,hd+n+2,-1);s=0,t=n+1;
for(int i=0;i<m;++i)q[i].read();
for(int i=1;i<=n;++i)
{
to[i]=nd;int x=d[i];
if(x>0)add(0,i,x);
else add(i,t,-x);
}
while(bfs())dfs(s,INF);
bool ok=1;
for(int i=1;i<=n;++i)
{
int x=d[i];
if(x!=0&&e[to[i]].cap>0)ok=0;
}
if(ok)
{
puts("YES");
for(int i=0;i<m;++i)
printf("%d\n",q[i].r-e[i<<1].cap);
}
else puts("NO");
return 0;
}有源汇有上下界最大流
#include<fstream>
const int N=333,M=22222,INF=2147483647;
using namespace std;
int n,m,s,t,nd,to[N],d[N],hd[N],hu[N],lvl[N],qwq[N];
struct edge
{
int to,nt,cap;
}e[M];
void add(int u,int v,int c)
{
e[nd]={v,hd[u],c};hd[u]=nd++;
e[nd]={u,hd[v],0};hd[v]=nd++;
}
struct que
{
int u,v,l,r;
void read()
{
scanf("%d%d%d%d",&u,&v,&l,&r);
d[u]-=l,d[v]+=l,add(u,v,r-l);
}
}q[M];
bool bfs()
{
copy(hd,hd+n+2,hu);fill(lvl,lvl+n+2,INF);
int l=0,r=0;qwq[r++]=s,lvl[s]=0;
while(l<r)
for(int u=qwq[l++],z=hd[u];~z;z=e[z].nt)
{
int v=e[z].to;
if(lvl[u]+1<lvl[v]&&e[z].cap>0)
lvl[v]=lvl[u]+1,qwq[r++]=v;
}
return lvl[t]<INF;
}
int dfs(int u,int f)
{
if(u==t||!f)return f;
int sm=0;
for(int &z=hu[u];~z;z=e[z].nt)
{
int v=e[z].to;
if(lvl[u]+1==lvl[v]&&e[z].cap>0)
{
int c=dfs(v,min(f,e[z].cap));
sm+=c,f-=c,e[z].cap-=c,e[z^1].cap+=c;
if(!f)break;
}
}
return sm;
}
int dicnic()
{
int res=0;
while(bfs())res+=dfs(s,INF);
return res;
}
int main()
{
int y,h;
scanf("%d%d%d%d",&n,&m,&y,&h);s=0,t=n+1;
fill(hd,hd+n+2,-1);
for(int i=0;i<m;++i)q[i].read();
for(int i=1;i<=n;++i)
{
to[i]=nd;
if(d[i]<0)add(i,t,-d[i]);
else add(s,i,d[i]);
}
add(h,y,INF);dicnic();
bool ok=1;
for(int i=1;i<=n;++i)
if(e[to[i]].cap>0)ok=0;
if(ok)s=y,t=h,printf("%d",dicnic());
else puts("please go home to sleep");
return 0;
}有源汇有上下界最小流
#include<fstream>
const int N=55555,M=433333,INF=2147483647;
using namespace std;
int n,m,s,t,nd,to[N],d[N],hd[N],hu[N],lvl[N],qwq[N];
struct edge
{
int to,nt,cap;
}e[M];
void add(int u,int v,int c)
{
e[nd]={v,hd[u],c};hd[u]=nd++;
e[nd]={u,hd[v],0};hd[v]=nd++;
}
struct que
{
int u,v,l,r;
void read()
{
scanf("%d%d%d%d",&u,&v,&l,&r);
d[u]-=l,d[v]+=l,add(u,v,r-l);
}
}q[M];
bool bfs()
{
copy(hd,hd+n+2,hu);fill(lvl,lvl+n+2,INF);
int l=0,r=0;qwq[r++]=s,lvl[s]=0;
while(l<r)
for(int u=qwq[l++],z=hd[u];~z;z=e[z].nt)
{
int v=e[z].to;
if(lvl[u]+1<lvl[v]&&e[z].cap>0)
{
lvl[v]=lvl[u]+1,qwq[r++]=v;
if(v==t)return 1;
}
}
return 0;
}
int dfs(int u,int f)
{
if(u==t||!f)return f;
int sm=0;
for(int &z=hu[u];~z;z=e[z].nt)
{
int v=e[z].to;
if(lvl[u]+1==lvl[v]&&e[z].cap>0)
{
int c=dfs(v,min(f,e[z].cap));
sm+=c,f-=c,e[z].cap-=c,e[z^1].cap+=c;
if(!f)break;
}
}
return sm;
}
int dicnic()
{
int res=0;
while(bfs())res+=dfs(s,INF);
return res;
}
int main()
{
int y,h;
scanf("%d%d%d%d",&n,&m,&y,&h);s=0,t=n+1;
fill(hd,hd+n+2,-1);
for(int i=0;i<m;++i)q[i].read();
for(int i=1;i<=n;++i)
{
to[i]=nd;
if(d[i]<0)add(i,t,-d[i]);
else add(s,i,d[i]);
}
add(h,y,INF);dicnic();
bool ok=1;
for(int i=1;i<=n;++i)
if(e[to[i]].cap>0)ok=0;
if(ok)
{
s=h,t=y;int giao=e[--nd].cap;
e[nd].cap=0;e[--nd].cap=0;
printf("%d",giao-dicnic());
}
else puts("please go home to sleep");
return 0;
}数论
Pollard-rho
#include<fstream>
#include<cmath>
#define auto long long
using namespace std;
const int tl=12;
const auto p[]={2,3,5,7,11,13,17,19,23,29,31,37};
inline auto product(auto x,auto y,auto n)//防爆乘
{
register long long ans=
x*y-(long long)((long double)x*y/n+0.5)*n;//技巧性极强
return ans<0?ans+n:ans;
}
auto gcd(auto a,auto b)
{
return (b==0)?a:gcd(b,a%b);
}
inline auto power(auto x,auto a,auto mod)//快速幂的另一种写法
{
auto res;
for(res=1;a!=0;a>>=1)
{
if((a&1)!=0)res=product(res,x,mod);
x=product(x,x,mod);
}
return res;
}
inline bool Miller_Rabin(auto x)
{
if(x<=2)return x==2;//特判
auto v1=x-1;
while((v1&1)==0)v1>>=1;
for(int i=0;i<tl;i++)
{
if(x==p[i])return 1;//显然
bool ok=0;
auto v=v1;
auto y=power(p[i],v,x);
if(y==1)ok=1;
else
{
while(v<x-1)
{
if(y==x-1)
{
ok=1;
break;
}
v<<=1;
y=product(y,y,x);
}
}
if(!ok)return 0;
}
return 1;
}
inline auto big_rand()
{
static auto sd=19260817;
sd^=sd<<13;
sd^=sd>>17;
return abs(sd^=sd<<5);
}
auto seed,step;
inline auto f(auto a,auto mod)
{
return (product(a,a,mod)+seed)%mod;
}
inline auto floyd(auto n) //绕环
{
seed=big_rand()%n;
auto fast,slow,res=1;
fast=slow=big_rand()%n;
fast=f(fast,n);//注意一开始不要先跳两步
for(register int i=0;fast!=slow;i++)
{
res=product(res,fast-slow+n,n);//段取优化
if(!res)res=fast-slow+n;
if(i%step==0)
{
auto g=gcd(res,n);
if(g!=1)return g;
res=1;
}
fast=f(f(fast,n),n);
slow=f(slow,n);
}
return gcd(res,n);
}
auto mx;
void Pollard_rho(auto n)
{
if(n==1)return;
if(Miller_Rabin(n))
{
mx=max(mx,n);
return;
}
auto k=1;
step=log(n);
step=step<<1|1;
while(k==1)k=floyd(n);
Pollard_rho(k);
Pollard_rho(n/k);
}
int main()
{
int T;auto n;
scanf("%d",&T);
while(T--)
{
mx=0;
scanf("%lld",&n);
Pollard_rho(n);
if(mx!=n)printf("%lld\n",mx);
else printf("Prime\n");
}
return 0;
} 拓展欧几里得
#include<iostream>
#define auto long long
using namespace std;
auto x,y,m,n,L;
auto exgcd(auto a,auto b,auto &x,auto &y)
{
if(!b)
{
x=1;y=0;
return a;
}
auto g=exgcd(b,a%b,y,x);
y-=a/b*x;
return g;
}
int main()
{
auto a,b,c,x,y,g;
cin>>a>>b>>c;
g=exgcd(a,b,x,y);
if(c%g==0)
{
x*=c/g;y*=c/g;
cout<<"x="<<x<<' '<<"y="<<y<<endl;
}
else
cout<<"No solution."<<endl;
return 0;
}类欧几里得
ll like_gcd(ll a,ll b,ll c,ll n) {
if(a==0)return b/c*(n+1);
if(a>=c||b>=c)return n*(n+1)/2*(a/c)+(n+1)*(b/c)+like_gcd(a%c,b%c,c,n);
ll m=(a*n+b)/c;
if(m==0)return 0;
return n*m-like_gcd(c,c-b-1,a,m-1);
}ll g(ll,ll,ll,ll);
ll f(ll a,ll b,ll c,ll n)
{
a%=c,b%=c;
ll m=(a*n+b)/c;
return !a||!n||!m?b:min(b,a-1-g(c,c-b-1,a,m-1));
}
ll g(ll a,ll b,ll c,ll n)
{
a%=c,b%=c;
ll m=(a*n+b)/c;
return !a||!n||!m?a*n+b:max((a*n+b)%c,c-1-f(c,c-b-1,a,m-1));
}BSGS
#include<fstream>
#include<bitset>
#include<cmath>
using namespace std;
struct hash_map
{
static const int mod=10000019;
int v[mod],p[mod];
void insert(const int key,const int a)
{
int hd=key%mod;
while(v[hd])
hd=(hd+1)%mod;
v[hd]=key;
p[hd]=a;
}
int find(const int key)
{
int hd=key%mod;
while(v[hd]!=key)
{
if(!v[hd])return 2147483647;//判断不行
hd=(hd+1)%mod;
}
return p[hd];
}
}H;
int power(int x,int p,int mod)
{
if(!p)return 1%mod;
long long res=power(x,p>>1,mod);
res=res*res%mod;
if(p&1)res=res*x%mod;
return res;
}
int main()
{
int p,b,n;
scanf("%d%d%d",&p,&b,&n);
int sq=sqrt(p),nib=power(b,p-2,p);
long long key=n,k2=power(b,sq,p);
for(int i=0;i<sq;i++)
{
// printf("%d %d\n",key,i);
H.insert(key,i);
key=key*nib%p;
}
key=1;
int ans=0;
for(int i=0;i<=sq;i++)
{
ans=H.find(key);
if(ans!=2147483647)
{
ans+=i*sq;
printf("%d",ans);
return 0;
}
key=key*k2%p;
}
printf("no solution");
return 0;
} exBSGS
#include<fstream>
#include<map>
#include<cmath>
#define auto long long
using namespace std;
auto exgcd(auto a,auto b,auto &x,auto &y)
{
if(!b)
{
x=1;y=0;
return a;
}
auto res=exgcd(b,a%b,y,x);
y-=a/b*x;
return res;
}
auto exbsgs(auto a,auto b,auto mod)
{
a%=mod;b%=mod;//先来一组特判
int tms=0;
auto x,y,g;
while(1)
{
// printf("%lld^x=%lld(mod %lld) For %d\n",a,b==1,mod,tms);
if(b==1)return tms;
g=exgcd(a,mod,x,y);
if(g!=1)
{
tms++;
mod/=g;
if(b%g!=0)return -1;
b/=g;
exgcd(a/g,mod,x,y);
x%=mod;
if(x<0)x+=mod;
b=(b*x)%mod;
}
else
{
x%=mod;
if(x<0)x+=mod;
break;
}
}
a%=mod;
// printf("%lld^x=%lld(mod %lld) For %d\n",a,b,mod,tms);
if(mod==1)return tms;
if(b==1)return tms;
if(a==0)
{
if(b==0)return 1+tms;
return -1;
}
map<auto,int>store;
auto buc=sqrt(mod),mn=mod,val=b,wei=1;
for(int i=0;i<buc;i++)
{
if(store.find(val)!=store.end())break;
// printf("Why?Impossible!%lld\n",val);
store[val]=i;
val=val*x%mod;
wei=wei*a%mod;
}
// printf("%d\n",store[2431]);
val=1;
for(int i=0;i*buc<mod;i++)
{
map<auto,int>::iterator it=store.find(val);
if(it!=store.end())
{
auto res=i*buc+it->second+tms;
return res;
}
val=val*wei%mod;
}
if(mn<mod)return mn;
else return -1;
}
int main()
{
// printf("%lld")
auto a,p,b;
while(1)
{
scanf("%lld%lld%lld",&a,&p,&b);
if(p==0)break;
auto res=exbsgs(a,b,p);
if(res==-1)printf("No Solution\n");
else printf("%lld\n",res);
}
return 0;
}Stern-Brocot 树
#include<bits/stdc++.h>
using ll=long long;
using namespace std;
ll m,n,ra,rb;
double r,mx;
bool ok=0;
int main()
{
ll a=0,b=1,c=1,d=0;
cin>>m>>n>>r;
ra=0,rb=1,mx=r;
while(1)
{
ll e=a+c,f=b+d,k;
if(e>m||f>n)break;
if(1.0*e/f<r)
k=(r*b-a)/(c-r*d),
e=a+=k*c,f=b+=k*d;
else
k=(c-r*d)/(r*b-a),
e=c+=k*a,f=d+=k*b;
if(abs(1.0*e/f-r)==mx)ok=1;
if(abs(1.0*e/f-r)<mx)
{
ra=e,rb=f,mx=abs(1.0*e/f-r),ok=0;
if(mx==0)break;
}
}
if(ok)puts("TOO MANY");
else printf("%lld/%lld",ra,rb);
return 0;
}exCRT
#include<fstream>
#define ll __int128
using namespace std;
int k;
ll a[2]={0},r[2]={0};
bool fg=1;
ll gcd(ll a,ll b)
{
return (!b)?a:gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
return a/gcd(a,b)*b;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b)
{
x=1;y=0;
return a;
}
ll g=exgcd(b,a%b,y,x);
y-=a/b*x;
return g;
}
void check(int i,int j)
{
// if(l==a[i]*a[j])return 0;
ll x=0,y=0;
ll g=exgcd(a[i],a[j],x,y);
ll l=a[i]/g*a[j],c=r[j]-r[i];
// printf("x%%%lld=%lld\n",a[i],r[i]);
if(c%g==0)
{
x*=c/g;
ll K=a[j]/g;
x%=K;
if(x<0)x+=K;
r[i]=r[i]+a[i]*x;
a[i]=l;
}
else fg=0;
}
void input(int k)
{
if(k)
{
scanf("%lld%lld",&a[0],&r[0]);
r[0]%=a[0];
if(r[0]<0)r[0]+=a[0];
}
for(int i=1;i<k;i++)
{
scanf("%lld%lld",&a[1],&r[1]);
r[1]%=a[1];
if(r[1]<0)r[1]+=a[1];
check(0,1);
if(!fg)break;
}
if(fg)
printf("%lld\n",r[0]);
else printf("-1\n");
}
void redo()
{
fg=1;
}
int main()
{
scanf("%d",&k);
redo();
input(k);
return 0;
}模质数二次剩余
#include<fstream>
#include<ctime>
#include<cstdlib>
using namespace std;
long long power(long long a,long long b,long long mod)
{
if(!b)return 1;
if(b==1)return a;
long long ans=power(a,b>>1,mod);
ans=ans*ans%mod;
if(b&1)ans=ans*a%mod;
return ans;
}
void cpower(long long &x,long long &y,long long b,long long a,long long w2,long long mod)//求(a+w)^b
{
if(!b)//(a+w)^0=1
{
x=1;y=0;
return;
}
// if(b==1)//(a+w)^1=a+w
// {
// x=a;y=1;
// return;
// }
long long x1=0,y1=0;
cpower(x1,y1,b>>1,a,w2,mod);
//(x1+y1*w)^2
//x1^2+2*x1*y1w+(y1*w)^2
x=(x1*x1%mod+y1*y1%mod*w2%mod)%mod;
y=x1*y1%mod*2%mod;
//(x+y*w)*(a+w)
//x*a+x*w+y*a*w+y*w2
if(b&1)
{
long long tmpx=(x*a%mod+y*w2%mod)%mod;
long long tmpy=(y*a%mod+x)%mod;
x=tmpx;
y=tmpy;
}
}
bool noroot(long long n,long long mod)
{
return power(n,(mod-1)>>1,mod)==mod-1;
}
void finda(long long &a,long long &w2,long long n,long long mod)
{
do
{
a=rand()%mod;
w2=(a*a-n)%mod;
if(w2<0)w2+=mod;
}
while(!noroot(w2,mod));
}
void solve()
{
long long n,mod;
scanf("%lld%lld",&n,&mod);
n%=mod;
if(mod==2)//0*0=0 1*1=1
printf("%lld\n",n);
else
{
if(!n)
{
printf("0\n");
return;
}
if(noroot(n,mod))
printf("Hola!\n");
else
{
long long a,w2,x,y;
finda(a,w2,n,mod);
// printf("a=%d\n",a);
// printf("w2=%d\n",w2);
cpower(x,y,(mod+1)>>1,a,w2,mod);
// printf("%d+%dw\n",x,y);
if((x<<1)<mod)
printf("%lld %lld\n",x,mod-x);
else
printf("%lld %lld\n",mod-x,x);
}
}
}
int main()
{
srand(time(NULL));
int T;
scanf("%d",&T);
while(T--)
solve();
return 0;
}欧拉函数和莫比乌斯函数杜教筛
#include<fstream>
using namespace std;
const int MAXN=1e7+1,MAXP=664579;
int pr[MAXP],tl,miu[MAXN];
unsigned long long phi[MAXN];
bool np[MAXN];
template <typename T,typename T1>
struct hash_map
{
static const int MOD=1e7+19;
T k[MOD];
T1 v[MOD];
int nm[MOD];
hash_map()
{
for(int i=0;i<MOD;i++)
k[i]=v[i]=nm[i]=0;
}
void insert(T key,T1 value)
{
int i=key%MOD;
if(i<0)i+=MOD;
while(nm[i]>0&&k[i]!=key)i=(i+1)%MOD;
k[i]=key;
v[i]=value;
nm[i]++;
}
bool find(T key,T1 &value)
{
int i=key%MOD;
if(i<0)i+=MOD;
while(k[i]!=key)
{
if(nm[i]==0)return 0;
i=(i+1)%MOD;
}
value=v[i];
return 1;
}
};
hash_map<unsigned,unsigned long long>big_phi;
hash_map<unsigned,int>big_miu;
void linear_sieve(int n)
{
np[0]=np[1]=1;tl=0;miu[1]=phi[1]=1;
for(int i=2;i<=n;++i)
{
if(!np[i])
{
pr[tl]=i;
++tl;
miu[i]=-1;
phi[i]=i-1;
}
for(int j=0;i*pr[j]<=n;++j)
{
np[i*pr[j]]=1;
if(i%pr[j]==0)
{
miu[i*pr[j]]=0;
phi[i*pr[j]]=phi[i]*pr[j];
break;
}
miu[i*pr[j]]=miu[i]*miu[pr[j]];
phi[i*pr[j]]=phi[i]*phi[pr[j]];
}
}
for(int i=1;i<=n;++i)
{
miu[i]+=miu[i-1];
phi[i]+=phi[i-1];
}
}
unsigned long long Dr_Du_sieve_phi(unsigned n)
{
if(n<MAXN)return phi[n];
unsigned long long ans;
if(big_phi.find(n,ans))return ans;
ans=(1ull*n*(n+1))>>1;
for(unsigned l=2;l<=n;)
{
int r=n/(n/l);
ans-=Dr_Du_sieve_phi(n/l)*(r-l+1);
l=r+1;
}
big_phi.insert(n,ans);
return ans;
}
int Dr_Du_sieve_miu(unsigned n)
{
if(n<MAXN)return miu[n];
int ans;
if(big_miu.find(n,ans))return ans;
ans=1;
for(unsigned l=2;l<=n;)
{
int r=n/(n/l);
ans-=(r-l+1)*Dr_Du_sieve_miu(n/l);
l=r+1;
}
big_miu.insert(n,ans);
return ans;
}
int main()
{
linear_sieve(MAXN-1);
int T;
scanf("%d",&T);
while(T--)
{
unsigned n;
scanf("%u",&n);
printf("%llu %d\n",Dr_Du_sieve_phi(n),Dr_Du_sieve_miu(n));
}
return 0;
}数据结构
可持久化并查集
#include<fstream>
const int N=220000,B=26214400;
using namespace std;
int n,m,tl=0,ls[B],rs[B],f[B],dp[B],rt[N];
void build(int l,int r,int &u)
{
u=++tl;
if(l==r)
{
f[u]=l,dp[u]=1;
return;
}
int mid=(l+r)>>1;
build(l,mid,ls[u]),
build(mid+1,r,rs[u]);
}
int select(int l,int r,int u,int x)
{
if(l==r)return u;
int mid=(l+r)>>1;
if(x<=mid)return select(l,mid,ls[u],x);
else return select(mid+1,r,rs[u],x);
}
void change(int l,int r,int u,int &v,int x,int y,int z)
{
if(x<l||r<x)
{
if(!v)v=u;
return;
}
v=++tl;
if(l==r)
{
f[v]=y,dp[v]=z;
return;
}
int mid=(l+r)>>1;
change(l,mid,ls[u],ls[v],x,y,z),
change(mid+1,r,rs[u],rs[v],x,y,z);
}
int fat(int k,int x)
{
int u=select(1,n,rt[k],x);
while(f[u]!=x)
{
x=f[u];
u=select(1,n,rt[k],x);
}
return u;
}
#define sam(k,x,y) (fat(k,x)==fat(k,y))
void tog(int a,int b,int x,int y)
{
int u=fat(a,x),v=fat(a,y);
if(u==v)
{
rt[b]=rt[a];
return;
}
if(dp[u]<dp[v])swap(u,v);
change(1,n,rt[a],rt[b],f[v],f[u],dp[v]);
change(1,n,rt[b],rt[b],f[u],f[u],dp[u]+(dp[u]==dp[v]));//Special
}
int main()
{
scanf("%d%d",&n,&m);
build(1,n,rt[0]);
for(int i=1;i<=m;++i)
{
int op,a,b;
scanf("%d%d",&op,&a);
if(op!=2)scanf("%d",&b);
switch(op)
{
case 3:puts(sam(i-1,a,b)?"1":"0");rt[i]=rt[i-1];break;
case 2:rt[i]=rt[a];break;
case 1:tog(i-1,i,a,b);
}
}
return 0;
} 李超树
#include<fstream>
#include<iostream>
const int N=110000,T=55000;
using namespace std;
int n;
double a[N<<2],b[N<<2];
void Add(int l,int r,int k,double A,double B)
{
if(r<l)return;
int mid=(l+r)>>1;
if(a[k]*mid+b[k]<A*mid+B)
swap(a[k],A),swap(b[k],B);
if(a[k]==A)return;
if(A<a[k])Add(l,mid-1,k<<1,A,B);
if(a[k]<A)Add(mid+1,r,k<<1|1,A,B);
}
double Query(int l,int r,int k,int x)
{
if(x<l||r<x)return 0;
int mid=(l+r)>>1;
if(x<=mid)return max(Query(l,mid-1,k<<1,x),a[k]*x+b[k]);
if(mid<x)return max(Query(mid+1,r,k<<1|1,x),a[k]*x+b[k]);
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;++i)
{
string op;
cin>>op;
if(op=="Project")
{
double a,b;
scanf("%lf%lf",&b,&a);
b-=a;
Add(1,T,1,a,b);
}
if(op=="Query")
{
double x;
scanf("%lf",&x);
printf("%lld\n",(long long)(Query(1,T,1,x)/100));
}
}
return 0;
}LCT
#include<fstream>
#define l sn[0][u]
#define r sn[1][u]
#define dr(u) (sn[1][f[u]]==u)
#define nt(u) (sn[0][f[u]]==u||sn[1][f[u]]==u)
const int N=110000;
using namespace std;
int n,m,f[N],g[N],xm[N],rv[N],sn[2][N];
inline void upd(int u)
{
xm[u]=xm[l]^xm[r]^g[u];
if(l)f[l]=u;if(r)f[r]=u;
}
inline void rev(int u)
{
rv[u]^=1,swap(l,r);
}
inline void down(int u)
{
if(rv[u])
rev(l),rev(r),rv[u]=0;
}
inline void turn(int u)
{
int k=dr(u),v=f[u];
if(nt(v))sn[dr(v)][f[v]]=u;
f[u]=f[v],sn[k][v]=sn[k^1][u];
upd(v),sn[k^1][u]=v;
upd(u);
}
int st[N];
inline void splay(int u)
{
int v=u,tp;
for(tp=0;nt(v);v=f[v])st[++tp]=v;
for(st[++tp]=v;tp;--tp)down(st[tp]);
while(nt(u))
{
if(nt(f[u]))
if(dr(u)==dr(f[u]))turn(f[u]);
else turn(u);
turn(u);
}
}
inline void access(int u)
{
for(int v=0;u;v=u,u=f[u])
{
splay(u);r=v;upd(u);
}
}
inline void make_root(int u)
{
access(u);splay(u);rev(u);
}
inline void split(int u,int v)
{
make_root(u);access(v);splay(v);
}
inline int find_root(int u)
{
access(u);splay(u);
while(l)
{
down(u);u=l;
}
splay(u);return u;
}
inline void link(int u,int v)
{
make_root(u);
if(find_root(v)!=u)
f[u]=v;
}
inline void cut(int u,int v)
{
split(u,v);
if(sn[0][v]==u&&!l&&!r)
sn[0][v]=f[u]=0;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%d",&g[i]);upd(i);
}
for(int i=0,op,u,v;i<m;++i)
{
scanf("%d%d%d",&op,&u,&v);
switch(op)
{
case 0:split(u,v);printf("%d\n",xm[v]);break;
case 1:link(u,v);break;
case 2:cut(u,v);break;
default:splay(u);g[u]=v;upd(u);
}
}
return 0;
}多项式
拉格朗日插值
#include<fstream>
const unsigned N=2200,mod=998244353;
using namespace std;
unsigned n,k,ans,x[N],y[N];
unsigned power(unsigned x,unsigned a)
{
if(a==0)return 1;
unsigned long long res=power(x,a>>1);
res=res*res%mod;
if(a&1)res=res*x%mod;
return res;
}
int main()
{
scanf("%u%u",&n,&k);
for(unsigned i=0;i<n;++i)
scanf("%u%u",&x[i],&y[i]);
for(unsigned i=0;i<n;++i)
{
unsigned long long fz=y[i],fm=1;
for(unsigned j=0;j<i;++j)fz=fz*(k+mod-x[j])%mod,fm=fm*(x[i]+mod-x[j])%mod;
for(unsigned j=i+1;j<n;++j)fz=fz*(k+mod-x[j])%mod,fm=fm*(x[i]+mod-x[j])%mod;
ans=(ans+fz*power(fm,mod-2)%mod)%mod;
}
printf("%u",ans);
return 0;
}快速沃尔什变换
#include<fstream>
const int N=17,mod=998244353;
#define input(f) for(int S=0;S<(1<<n);++S)scanf("%d",&f[S]);
#define add(a,b) a+b>=mod?a+b-mod:a+b
#define mus(a,b) a>=b?a-b:a+mod-b
#define div2(a) (a&1)?(a+mod>>1):(a>>1)
#define cup(a,b) b=add(a,b)
#define ncup(a,b) b=mus(b,a)
#define cap(a,b) a=add(a,b)
#define ncap(a,b) a=mus(a,b)
inline void oplus(int &a,int &b)
{
int x=a,y=b;
a=add(x,y);b=mus(x,y);
}
inline void noplus(int &a,int &b)
{
oplus(a,b);
a=div2(a);b=div2(b);
}
#define FMT(f,c)\
do\
{\
for(int k=1;k<(1<<n);k<<=1)\
for(int S=0;S<(1<<n);S+=k)\
for(int i=0;i<k;++i,++S)\
c(f[S],f[S+k]);\
}\
while(0);
int n,A[1<<N],B[1<<N],a[1<<N],b[1<<N];
#define in for(int i=0;i<(1<<n);++i)a[i]=A[i],b[i]=B[i];
#define times for(int i=0;i<(1<<n);++i)a[i]=1ll*a[i]*b[i]%mod;
#define out for(int i=0;i<(1<<n);++i)printf("%d ",a[i]);puts("");
int main()
{
scanf("%d",&n);
input(A) input(B)
in FMT(a,cup) FMT(b,cup) times FMT(a,ncup) out
in FMT(a,cap) FMT(b,cap) times FMT(a,ncap) out
in FMT(a,oplus) FMT(b,oplus) times FMT(a,noplus) out
return 0;
}子集卷积
#include<fstream>
const int N=22,U=1048576,mod=1000000009;
using namespace std;
int n,a[N][U],b[N][U],c[N][U];
#define pp(x) __builtin_popcount(x)
#define add(x,y) x+y>=mod?x+y-mod:x+y
#define mus(x,y) x>=y?x-y:x+mod-y
int main()
{
scanf("%d",&n);
int Au=1<<n;
for(int S=0;S<Au;++S)
scanf("%d",&a[pp(S)][S]);
for(int k=0;k<=n;++k)
for(int i=0;i<n;++i)
for(int S=0;S<Au;++S)
if((S>>i)&1)a[k][S]=add(a[k][S],a[k][S^(1<<i)]);
for(int S=0;S<Au;++S)
scanf("%d",&b[pp(S)][S]);
for(int k=0;k<=n;++k)
for(int i=0;i<n;++i)
for(int S=0;S<Au;++S)
if((S>>i)&1)b[k][S]=add(b[k][S],b[k][S^(1<<i)]);
for(int k=0;k<=n;++k)
for(int i=0;i<=k;++i)
for(int S=0;S<Au;++S)
c[k][S]=add(c[k][S],1ll*a[i][S]*b[k-i][S]%mod);
for(int k=0;k<=n;++k)
for(int i=0;i<n;++i)
for(int S=0;S<Au;++S)
if((S>>i)&1)c[k][S]=mus(c[k][S],c[k][S^(1<<i)]);
for(int S=0;S<Au;++S)
printf("%d ",c[pp(S)][S]);
return 0;
} FFT
#include<bits/stdc++.h>
const int N=1<<21,mod=998244353;
using namespace std;
int n,m,L,sw[N],a[N],b[N];
long long w[N];
void dft(int *a)
{
for(int i=0;i<L;++i)if(i<sw[i])swap(a[i],a[sw[i]]);
for(int i=1;i<L;i<<=1)
for(int j=0;j<L;j+=i)
for(int k=0;k<i;++k,++j)
{
int x=a[j],y=1ll*a[j+i]*w[L/i/2*k]%mod;
a[j]=x+y>=mod?x+y-mod:x+y,
a[j+i]=x>=y?x-y:x+mod-y;
}
}
int pw(long long x,int a)
{
long long res=1;
for(;a;a>>=1,x=x*x%mod)
if(a&1)res=res*x%mod;
return res;
}
void idft(int *a)
{
long long ni=pw(L,mod-2);
for(int i=0;i<L;++i)a[i]=a[i]*ni%mod;
dft(a);
for(int i=1;i<(L>>1);++i)swap(a[i],a[L-i]);
}
int main()
{
scanf("%d%d",&n,&m);
L=1<<int(log(n+m)/log(2)+1);
w[1]=pw(3,(mod-1)/L),w[0]=1;
for(int i=1;i<L;++i)
w[i]=1ll*w[i-1]*w[1]%mod,
sw[i]=(i&1?sw[i>>1]|L:sw[i>>1])>>1;
for(int i=0;i<=n;++i)scanf("%d",&a[i]);
dft(a);
for(int i=0;i<=m;++i)scanf("%d",&b[i]);
dft(b);
for(int i=0;i<L;++i)a[i]=1ll*a[i]*b[i]%mod;
idft(a);
for(int i=0;i<=n+m;++i)printf("%d ",a[i]);
return 0;
}特殊类型
大整数类
#include<bits/stdc++.h>
using namespace std;
namespace modint {
struct mdu {
int mod;
unsigned long long help;
mdu(int x=1) {
mod=x,help=(__int128(1)<<64)/x;
}
} mod=998244353;//g=3
inline int operator % (const long long &a,const mdu &b) {
int r=a-(__int128(b.help)*a>>64)*b.mod;
return {r>=b.mod?r-b.mod:r};
}
struct mint {
//It is suggest that don't use it in the Speed-needed place
//建议不要在需要追求时间效率的地方使用这个模板
int w;
mint(long long x=0) {
x=x%mod;
if(x<0)x+=mod.mod;
w=x;
}
bool operator == (const mint &b) const {
return w==b.w;
}
};
mint operator + (const mint &a,const mint &b) {
int x=a.w+b.w;
return {x>=mod.mod?x-mod.mod:x};
}
mint operator += (mint &a,const mint &b) {
return a=a+b;
}
mint operator - (const mint &a,const mint &b) {
int x=a.w-b.w;
return {x>=0?x:x+mod.mod};
}
mint operator -= (mint &a,const mint &b) {
return a=a-b;
}
mint operator * (const mint &a,const mint &b) {
return {1ll*a.w*b.w%mod};
}
mint operator *= (mint &a,const mint &b) {
return a=a*b;
}
mint pw(mint a,int b) {
mint res=1;
for(; b; a*=a,b>>=1)
if(b&1)res*=a;
return res;
}
int exgcd(int a,int b,int &x,int &y) {
if(!b) {
x=1,y=0;
return a;
}
int g=exgcd(b,a%b,y,x);
y-=a/b*x;
return g;
}
mint inv(mint x) {
//assert that a and mod are relatively prime
//假定 a 与模数互质
int ni,nt;
assert(exgcd(x.w,mod.mod,ni,nt)==1);
return ni;
}
mint operator / (const mint &a,const mint &b) {
return a*inv(b);
}
mint operator /= (mint &a,const mint &b) {
return a=a/b;
}
};
namespace biginteger {
using namespace modint;
struct bint {
short tp;
vector<int>s;
bint(long long x=0) {
s.clear();
if(x>0)tp=1;
if(!x)tp=0;
if(x<0)tp=-1,x=-x;
while(x) {
s.push_back(int(x%10));
x/=10;
}
reverse(s.begin(),s.end());
}
void read() {
s.clear();
int c=getchar();
tp=1;
while(!isdigit(c)) {
if(c=='-')tp=-1;
c=getchar();
}
while(isdigit(c)) {
if(!s.empty()||c!='0')s.push_back({c^'0'});
c=getchar();
}
if(s.empty())tp=0;
}
void write() {
if(!tp)putchar('0');
else {
if(tp==-1)putchar('-');
for(auto z:s)putchar(z^'0');
}
}
bool operator < (const bint &b) const {
return tp==b.tp?s.size()==b.s.size()?s<b.s:s.size()<b.s.size():tp<b.tp;
}
bool operator > (const bint &b) const {
return b<*this;
}
bool operator <= (const bint &b) const {
return !(b<*this);
}
bool operator >= (const bint &b) const {
return !(*this<b);
}
bool operator == (const bint &b) const {
return tp==b.tp&&s==b.s;
}
bool operator != (const bint &b) const {
return !(*this==b);
}
};
bint operator - (bint a) {
a.tp=-a.tp;
return a;
}
bint operator + (bint a,bint b) {
if(!a.tp)return b;
if(!b.tp)return a;
bint c;
reverse(a.s.begin(),a.s.end());
reverse(b.s.begin(),b.s.end());
if(a.tp==b.tp) {
c.tp=b.tp,c.s.resize(max(a.s.size(),b.s.size()));
int ad=0;
for(unsigned i=0; i<c.s.size(); ++i) {
if(i<a.s.size())c.s[i]+=a.s[i];
if(i<b.s.size())c.s[i]+=b.s[i];
c.s[i]+=ad;
if(c.s[i]>=10)c.s[i]-=10,ad=1;
else ad=0;
}
while(ad>0)c.s.push_back(ad%10),ad/=10;
} else {
c.tp=a.tp,c.s.resize(max(a.s.size(),b.s.size()));
for(unsigned i=0; i<c.s.size(); ++i) {
if(i<a.s.size())c.s[i]+=a.s[i];
if(i<b.s.size())c.s[i]-=b.s[i];
}
while(!c.s.empty()&&c.s.back()==0)c.s.pop_back();
if(!c.s.empty()) {
if(c.s.back()<0) {
c.tp=-c.tp;
for(auto &z:c.s)z=-z;
}
int ad=0;
for(auto &z:c.s) {
z+=ad;
if(z<0)ad=-1,z+=10;
else ad=0;
}
while(!c.s.empty()&&c.s.back()==0)c.s.pop_back();
}
if(c.s.empty())c.tp=0;
}
reverse(c.s.begin(),c.s.end());
return c;
}
bint operator += (bint &a,const bint &b) {
return a=a+b;
}
bint operator - (const bint &a,const bint &b) {
return a+-b;
}
bint operator -= (bint &a,const bint &b) {
return a=a-b;
}
static void dft(vector<mint>&a,vector<int>&sw,int L,int tp) {
//In the speed-needed place we expand the mint type
//这里在瓶颈处我们展开了 mint 类
for(int i=0; i<L; ++i)
if(i<sw[i])swap(a[i],a[sw[i]]);
for(int i=1; i<L; i<<=1) {
int g=pw(3,tp==1?(mod.mod-1)/i/2:mod.mod-1-(mod.mod-1)/i/2).w;
for(int j=0; j<L; j+=i) {
int bf=1;
for(int k=0; k<i; ++j,++k,bf=1ll*bf*g%mod) {
int x=a[j].w,y=1ll*a[j+i].w*bf%mod;
a[j]=x+y,a[j+i]=x-y;
}
}
}
if(tp==-1) {
mint ivn=inv(L);
for(int i=0; i<L; ++i)a[i]*=ivn;
}
}
bint operator * (bint a,bint b) {
if(a==0||b==0)return 0;
int L=1<<int(log(a.s.size()+b.s.size()-2)/log(2)+1);
bint c;
c.tp=a.tp*b.tp;
reverse(a.s.begin(),a.s.end());
reverse(b.s.begin(),b.s.end());
c.s.resize(a.s.size()+b.s.size()-1);
if(min(a.s.size(),b.s.size())<4*log(L))
for(unsigned i=0; i<a.s.size(); ++i)
for(unsigned j=0; j<b.s.size(); ++j)
c.s[i+j]+=a.s[i]*b.s[j];
else {
assert(L<=8388608);
//assert that L is no longer than 8388608
//假定 L 不大于 8388608
vector<mint>x(L),y(L);
vector<int>sw(L);
for(unsigned i=0; i<a.s.size(); ++i)x[i]=a.s[i];
for(unsigned i=0; i<b.s.size(); ++i)y[i]=b.s[i];
for(int i=1; i<L; ++i)sw[i]=(i&1?sw[i>>1]|L:sw[i>>1])>>1;
dft(x,sw,L,1),dft(y,sw,L,1);
for(int i=0; i<L; ++i)x[i]*=y[i];
dft(x,sw,L,-1);
for(unsigned i=0; i<c.s.size(); ++i)c.s[i]=x[i].w;
}
int ad=0;
for(auto &z:c.s)z+=ad,ad=z/10,z%=10;
while(ad>0)c.s.push_back(ad%10),ad/=10;
reverse(c.s.begin(),c.s.end());
return c;
}
bint operator *= (bint &a,const bint &b) {
return a=a*b;
}
static bint pw(bint a,int b) {
bint res=1;
for(; b; a*=a,b>>=1)
if(b&1)res*=a;
return res;
}
bint operator << (bint a,int b) {
for(int i=0; i<b; ++i)a.s.push_back(0);
return a;
}
bint operator <<= (bint &a,const int &b) {
return a=a<<b;
}
bint operator >> (bint a,int b) {
for(int i=0; i<b; ++i)
if(!a.s.empty())a.s.pop_back();
else {
a.tp=0;
break;
}
return a;
}
bint operator >>= (bint &a,const int &b) {
return a=a>>b;
}
bint barret(bint a) {
int n=a.s.size();
if(n==1)return 100/a.s[0];
if(n==2)return 10000/(10*a.s[0]+a.s[1]);
int m=n/2+1;
bint b=barret(a>>(n-m))<<(n-m);
b=(b*((bint(2)<<(n<<1))-a*b))>>(n<<1);
return b;
}
bint operator / (bint a,bint b) {
assert(b.tp);
if(!a.tp)return 0;
int m=a.s.size()-2*b.s.size();
if(m>0)a<<=m,b<<=m;
int x=a.tp*b.tp;a.tp=b.tp=1;
bint n=bint(1)<<(b.s.size()<<1),k=barret(b);
k=(k*a)>>(b.s.size()<<1);
bint g=k*b;
while(g<a)k+=1,g+=b;
while(g>a)k-=1,g-=b;
k.tp=x;
if(k.s.empty())k.tp=0;
return k;
}
bint operator /= (bint &a,const bint &b) {
return a=a/b;
}
bint operator % (const bint &a,const bint &b) {
return a-a/b*b;
}
bint operator %= (bint &a,const bint &b) {
return a=a%b;
}
bint pw(bint a,bint b,bint c) {
bint res=1;
for(; b!=0; a=a*a%c,b=b/2)
if(b.s.back()&1)res=res*a%c;
return res;
}
};
int main() {
using namespace biginteger;
srand(time(NULL));
bint a,b;
a.read(),b.read();
(a+b).write();puts("");
(a-b).write();puts("");
(a*b).write();puts("");
(a/b).write();puts("");
(a%b).write();puts("");
return 0;
}