算法板子[updating]

板子

数据结构

单调栈/队列

并查集

ST表

线段树

珂朵莉树

图论

存储

链式前向星

vec型

1
2
3
4
5
6
7
vector<int> nxt,head,to;
//初始化 head.resize(n+1,-1)
void add(int u,int v){
    nxt.push_back(head[u]);
    head[u] = to.size();
    to.push_back(v);
}

数组型

1
2
3
4
5
6
7
8
const int N=1e5;
int nxt[N],head[N],to[N];
int cnt = 0;
void add(int u,int v){
    nst[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
}

判断二分图

数学

高精度

快速幂

若无需模，请无视 \(p\)

1
2
3
4
5
6
7
8
9
int qpow(int a,int b,int p){
    int res = 1;
    while(b){
        if(b&1) res = res*a %p;
        a = a*a %p;
        b >>= 1;
    }
    return res;
}

分解质因数

朴素做法

1
2
3
4
5
6
7
8
9
10
11
vector<int> breakdown(int n){
    vector<int> res;
    for(int i=2;i*i<=n;i++){
        while(n%i==0){
            n/=i;
            res.push_back(i);
        }
    }
    if(n!=1) res.push_back(n); //经过操作后留下了一个素数
    return res;
}

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<bool> isPrime;
vector<int> prime;
int n,q;
void seive(){
    isPrime.assign(n+1,true);
    for(int i=2;i<=n;i++){
        if(isPrime[i]){
            prime.push_back(i);
        }
        for(auto j:prime){
            if(i*j > n) break;
            isPrime[i*j] = false;
            if(i % j == 0) break;
        }
    }
}

欧拉函数

模逆元

当模数是素数 \(p\) 时

单个乘法逆元使用快速幂 \(qpow(a,p-2,p)\) 即可 （ \(a^{p-1} \equiv1 \pmod p\)）