数论
快速乘：
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<b)
return 0;
if(a<mod&&b<mod)
return 1ll*f[a]*v[b]%mod*v[a-b]%mod;
return 1ll*lucas(a%mod,b%mod)*lucas(a/mod,b/mod)%mod;
}
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<pc;i++) if(i%p) (sum*=i)%=pc;
ll ans=qpow(sum,n/pc,pc);
for(int i=1;i<=n%pc;i++) if(i%p) (ans*=i)%=pc;
return ans*fac(n/p,p,pc)%pc;
}
ll inv(ll n,ll p)
{
ll x,y;
exgcd(n,p,x,y);
((x%=p)+=p)%=p;
return x;
}
ll C(ll x,ll y,ll p,ll pc)
{
if(x<y) return 0ll;
int cnt=num(x,p)-num(y,p)-num(x-y,p);
return fac(x,p,pc)*inv(fac(y,p,pc),pc)%pc*inv(fac(x-y,p,pc),pc)%pc*qpow(p,cnt,pc)%pc;
}
BSGS：
map<ll,ll>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<pair<int,int> >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<int>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};
}
}