数论

快速乘：

ll qmul(ll x,ll y,ll mod){	ll ans=0;	while(y)	{		if(y&1) (ans+=x)%=mod;		y>>=1;		(x+=x)%=mod;	}	return ans;}

快速幂：

ll qpow(ll x,ll y,ll mod){	ll ans=1;	while(y)	{		if(y&1) (ans*=x)%=mod;		y>>=1;		(x*=x)%=mod;	}	return ans;}

Gcd：

ll gcd(ll a,ll b){	return b?gcd(b,a%b):a;}

Exgcd：

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

 Lucas：

void init(){	f[0]=v[0]=1; for(int i=1;i<=mod;i++) f[i]=f[i-1]*i%mod;	v[mod-1]=mod-1; for(int i=mod-2;i;i--) v[i]=v[i+1]*(i+1)%mod;}ll lucas(ll a,ll b){    if(a

ExLucas：

ll num(ll x,ll p){	ll re=0;	while(x)	{		re+=x/p;		x/=p;	}	return re;}ll fac(ll n,ll p,ll pc){	if(!n) return 1ll;	ll sum=1ll;	for(int i=1;i

BSGS：

map
     
      MP;ll bsgs(ll A,ll B,ll C) // x^A \equiv B (mod\ C){	ll m=ceil(sqrt(C+0.5));	MP.clear();	ll now=1;	for(int i=1;i<=m;i++)	{		(now*=A)%=C;		if(!MP[now]) MP[now]=i;	}	A=qpow(A,m,C);	now=1;	for(int i=0;i<=m;i++)	{		ll x,y;		exgcd(now,C,x,y);		x=(x*B%C+C)%C;		if(MP.count(x)) return i*m+MP[x];		(now*=A)%=C;	}	return 0;}
     

求原根：

ll get_ori(ll p,ll phi){	int c=0;	for(int i=2;1ll*i*i<=phi;i++) if(phi%i==0)	{		f[++c]=i; f[++c]=phi/i;	}	for(int g=2;;g++)	{		int j;		for(j=1;j<=c;j++) if(qpow(g,f[j],p)==1) break;		if(j==c+1) return g;	}	return 0;}

线性基：

for(i=1<<30;i;i>>=1){	for(j=1;j<=n;j++) if(!vis[j]&&a[j].v&i) break;	if(j>n) continue;	sum-=a[j].num; vis[j]=true;	for(k=1;k<=n;k++) if(!vis[k]&&a[k].v&i) a[k].v^=a[j].v;}

 图论

tarjan：

void tarjan(int p){	st[++top]=p; ins[p]=true;	dep[p]=low[p]=++cnt;	for(int i=head[p];i;i=nxt[i])	{		if(!dep[to[i]) tarjan(to[i]),low[p]=min(low[p],low[to[i]]);		else if(ins[to[i]]) low[p]=min(low[p],dep[to[i]]);	}	if(dep[p]==low[p])	{		Number++;		int t;		do		{			t=st[top--]; ins[t]=false;			f[Number][++f[Number][0]]=t;		}while(t!=p);	}}

堆优化Dijkstra：

priority_queue
     
      
        >q;void Dijkstra(){	while(!q.empty()) q.pop();	memset(dis,0x3f,sizeof dis); dis[S]=0; q.push(mp(0,S));	while(!q.empty())	{		while(!q.empty()&&-q.top().first>dis[q.top().second]) q.pop();		if(q.empty()) return;		int x=q.top().second; q.pop();		for(int i=head[x];i;i=nxt[i]) if(dis[to[i]]>dis[x]+val[i])		{			dis[to[i]]=dis[x]+val[i];			q.push(mp(-dis[to[i]],to[i]));		}	}}
      
     

 spfa：

queue
     
      q;void spfa(){	while(!q.empty()) q.pop();	memset(dis,0x3f,sizeof dis); dis[S]=0; q.push(S);	vis[x]=true;	while(!q.empty())	{		int x=q.front(); q.pop(); vis[x]=false;		for(int i=head[x];i;i=nxt[i]) if(dis[to[i]]>dis[x]+val[i])		{			dis[to[i]]=dis[x]+val[i];			if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=true;		}	}}
     

倍增lca

void dfs(int p, int fa) {    f[0][p] = fa;    dep[p] = dep[fa] + 1;    for (int i = 1; i <= 20; i ++ )        f[i][p] = f[i-1][f[i-1][p]];    for (int i = head[p]; i; i = nxt[i]) {        if(to[i] != fa) {            dfs(to[i], p);        }    }}int lca(int x, int y) {    if (dep[x] < dep[y]) swap(x, y);    for (int i = 20; ~i; i -- ) {        if (dep[f[i][x]] >= dep[y]) {            x = f[i][x];        }    }    if (x == y) return x;    for (int i = 20; ~i; i -- ) {        if (f[i][x] != f[i][y]) {            x = f[i][x];            y = f[i][y];        }    }    return f[0][x];}

 

 数据结构

非旋转Treap

int merge(int x, int y) {    if (!x || !y) return x | y;    pushdown(x); pushdown(y);    if (a[x].key > a[y].key) {        a[x].rs = merge(a[x].rs, y);        pushup(x);        return x;    }    else {        a[y].ls = merge(x, a[y].ls);        pushup(y);        return y;    }}par split(int x, int k) {    if(!k)        return (par) {0, x};    pushdown(x);    int ls = a[x].ls, rs = a[x].rs;    if (k == a[ls].size) {        a[x].ls = 0;        pushup(x);        return (par) {ls, x};    }    else if (k == a[ls].size + 1) {        a[x].rs = 0;        pushup(x);        return (par) {x, rs};    }    else if (k < a[ls].size) {        par t = split(ls, k);        a[x].ls = t.y;        pushup(x);        return (par) {t.x, x};    }    else {        par t = split(rs, k - a[ls].size - 1);        a[x].rs = t.x;        pushup(x);        return (par) {x, t.y};    }}