搜索

剪枝

1. 优化搜索顺序：我们应该选择首先搜索分支较少的点
2. 排除等效冗余
3. 可行性剪枝：有些明显搜下去没结果的，直接剪枝
4. 最优化剪枝：有些已经不可能是最优解的，直接剪枝
5. 记忆化搜索

图论

求负环常用方法（基于SPFA）

1. 统计每个点入队的次数，如果有点入队 $n$ 次，说明有负环
2. 统计当前每个点的最短路边数，如果有最短路边数大于等于 $n$ ，则说明有负环

差分约束

求不等式的可行解

源点需要满足的条件：从源点出发，一定可以走到所有的边。

步骤：

1. 先将每个不等式 $x_i\le x_i+c_k$ 转化成一条从 $x_j$ 到 $x_i$ 长度为 $c_k$ 的边
2. 找一个超级源点，使得该源点可以遍历到图中所有的边
3. 从源点求一次单源最短路
4. 结果1：如果存在负环，原不等式一定无解
5. 结果2：如果没有负环，则 $dist[i]$ 就是原不等式的一个可行解

求最大值，最小值

结论：如果求的是最小值，则应该求最长路；如果求最大值，应该求最短路。

问题：如何转化 $x_i\le c$ 其中 $c$ 是一个常数，这类不等式

方法：建立一个超级源点0，让0指向 $x_i$ ，并且边的长度为 $c$

以求 $x_i$ 最大值为例：求所有从 $x_i$ 出发，构成不等式链 $x_i\le x_j+c_1\le x_k+c_1+c_2\le···\le \sum c_i$ , 所计算出的上界。最终 $x_i$ 的最大值等于所有上界的最小值。

求最近公共祖先

倍增（在线做法）

时间复杂度 $O((n+m)logn)$

$fa[i,j]$ 表示从 $i$ 开始，向上走 $2^j$ 步所能走到的节点。$0\le j\le logn$

$depth[i]$ 表示节点的深度

这两个数组初始化使用 $dfs$ 或 $bfs$ ，每次使用二进制拼凑的思想。

哨兵：如果从 $i$ 向上走 $2^j$ 步会跳过根节点，那么 $fa[i,j]=0$ ；

步骤：

1. 先将两个点跳到同一层
2. 让两个点一起跳，直到跳到它们最近公共祖先的下一层。

预处理$O(nlogn)$ $+$ 查询$O(logn)$

void bfs(int root){//预处理fa数组和depth数组
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[root]=1;//哨兵和根节点
    int tt=0,hh=0;
    q[0]=root;
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(depth[j]>depth[t]+1){
                depth[j]=depth[t]+1;
                fa[j][0]=t;
                q[++tt]=j;
                for(int k=1;k<=15/*log(N)上取整*/;k++)
                    fa[j][k]=fa[fa[j][k-1]][k-1];
            }
        }
    }
}

int lca(int x,int y){//倍增法过程
    if(depth[x]<depth[y])swap(x,y);
    for(int i=15;i>=0;i--){
        if(depth[fa[x][i]]>=depth[y])
            x=fa[x][i];
    }
    if(x==y)return x;
    for(int i=15;i>=0;i--){
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}

Tarjan（离线做法）

时间复杂度 $O(n+m)$

在进行深度优先搜索的时候，把所有点分为三类：

1. 已经搜索过，并且已经回溯的点，标记为 $2$
2. 正在搜索，还未回溯，标记为 $1$
3. 没有搜索到的点，标记为 $0$

每次遍历到一个新点，把它合并到它的父节点。遍历询问时，当另外一个点已经回溯之后，那么最近公共祖先就是另一个点被合并到的点。

void tarjan(int u){
    st[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(!st[j]){
            tarjan(j);
            p[j]=u;
        }
    }

    for(auto item:query[u]){
        int y=item.first,id=item.second;
        if(st[y]==2){
            fa[id]=find(y);
        }
    }
    st[u]=2;
}

强连通分量

连通分量： 对于一个有向图，分量中任意两个点都可以相互到达。

强连通分量： 极大联通分量

边的分类：

• 树枝边：向遍历方向正向走一步的边
• 前向边：向遍历方向正向连的边
• 后向边：向遍历方向的反向连的边
• 横插边：当前遍历节点指向已经回归的节点的边

判断某点是否处于强连通分量中：

• 情况一：存在后向边指向某个祖先节点
• 情况二：存在横插边，能够从横插边再后向指向某个祖先节点

tarjan算法求强连通分量（SCC）

时间复杂度 $O(n+m)$

对每个点定义两个时间戳：

• $dfn(u)$ 表示遍历到 $u$ 的时间戳
• $low(u)$ 表示从 $u$ 遍历，能走到的时间戳最小的点
• $u$ 是当前所在强连通分量的最高点，等价于 $dfn(u)==low(u)$

dfs生成树和强连通分量之间的关系：

如果结点 $u$ 是强连通分量中第一个被遍历到的结点，那么这个强连通分量的其他结点一定是在以 $u$ 为结点的子树中。

搜索过程中考虑相邻的两个点 $u$ 和 $v$ 的关系：

• $v$ 未被访问，对 $v$ 进行搜索，并且在回溯的时候用 $low[v]$ 更新 $low[u]$，因为 $u$ 和 $v$ 之间存在直接路径，所以 $v$ 可以回溯到的点，$u$ 也可以回溯到。
• $v$ 已经被访问，而且在栈里面，用 $dfn[v]$ 更新 $low[u]$ ，因为当前情况就是横插边的情况。
• $v$ 已经被访问，但是不在栈里面，说明不在当前强连通分量中，不考虑。

对一个有向图，加几条边可以让整张图变成一个强连通分量：$max(p,q)$ 缩点后出度为0和入度为0的点的较大值

int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, sz[N];

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } 
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int y;
        do {
            y = stk[top--];
            stk[y] = false;
            id[y] = scc_cnt;
            sz[scc_cnt]++;
        } while (y != u)
    }
}

双连通分量

桥：如果存在一条无向边，去掉这条无向边，图被分成两部分

割点： 如果存在一个结点，去掉这个结点，图被分成两个及以上部分，两者没有决定关系

边双连通分量（$e-DCC$）： 极大的不含桥的子图

点双连通分量（$v-DCC$）：

tarjan算法求边双连通分量

$dfn(u)$, $low(u)$, $timestamp$ 含义和强连通分量中的一样。

• 如何找到一个桥（x作为父结点，y作为子结点）：$dfn(x)>low(y)$
• 如何找到所有边双连通分量
• 删去所有桥
• 用栈储存，然后输出（和强连通分量一样）

对一个无向图，最少加几条边可以让整张图变成一个双连通分量： $\dfrac{cnt+1}{2}$ 其中 $cnt$ 表示叶节点的个数

数据结构

Trie数（字典树）

高效的存储和查找字符串集合的数据结构。有查询和添加两个操作。

int son[N][26], cnt[N], idx;

void insert(char *str)//插入操作
{
    int p = 0;//从0开始找
    for (int i = 0; str[i]; i ++ )//遍历字符串每一位
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;//如果没有，那么添加一个点
        p = son[p][u];//到下一位
    }
    cnt[p] ++ ;//当前字符串数量加一
}

int query(char *str)//查询操作
{
    int p = 0;//从0开始找
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;//没有直接返回
        p = son[p][u];
    }
    return cnt[p];
}

树状数组

首先树状数组是用来维护前缀和的数据结构，可以在 $O(logn)$ 的时间内完成对前缀和的查询和单点修改

int tr[N];

int lowbit(int x) {
    return x & -x;
}

int add(int x, int d) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += d;
}

int query(int x) {
    int sum = 0;
    for (int i = x; i; i -= lowbit(i)) sum += tr[i];
    return sum;
}

线段树

下面用一个维护区间和的线段树来举例。

概况

作用： 线段树可以维护满足加法原则的任何属性（即可以通过左右两个区间的属性得到当前属性）。并且可以区间修改，区间查询，每个操作的时间复杂度都是 $O(logn)$ 的

大致结构： 线段树除了最后一层，其他都是一棵完美二叉树。按照堆的方式来存储，每个结点是一个结构体，结构体存储了一个区间和需要维护的属性。并且一共有 $4\times N$ 个结点。

struct Node {
    int l, r;
    LL sum, add;
} tr[N * 4];

懒标记： 相当于把修改操作先放在上面的结点上，需要下载的时候再用懒标记一起更新下面的结点。

操作

pushup

这个操作可以用子结点的属性更新父节点，一般在递归返回的时候进行。

void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

pushdown

这个操作是用父结点的信息去更新子结点的信息，详细的说，用父结点的懒标记更新子结点的属性和子结点的懒标记，并且把父结点的懒标记清零，从而进行懒标记的实现。一般在递归开始的时候使用。

void pushdown(int u) {
    Node &root = tr[u];
    Node &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add) {
        left.add += root.add;
        left.sum += (LL)(left.r - left.l + 1) * root.add;
        right.add += root.add;
        right.sum += (LL)(right.r - right.l + 1) * root.add;
        root.add = 0;
    }
}

build： 初始化线段树

void build(int u, int l, int r) {
    if (l == r) { // 如果到了叶节点，把属性和区间两个端点输入。
        tr[u] = {l, r, a[l], 0};
    }
    else { // 这是非叶节点的设置
        tr[u] = {l, r}; // 不要忘记把区间端点赋值，否则会SF
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); // 递归处理左右儿子
        pushup(u); // 这里pushup的原因，为了把在叶节点的具体属性值上传给所有的结点
    }
}

modify：区间修改

void modify(int u, int l, int r, int c) {
    if (tr[u].l >= l && tr[u].r <= r) { // 如果待修改区间完全包含当前递归区间，那么直接在这一层进行修改（懒标记和属性）
        tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * c;
        tr[u].add += c;
    }
    else {
        pushdown(u); // 这里pushdown的原因，在pushup之前把树上的属性下载到叶节点上，否则懒标记会被pushup覆盖
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, c); // 如果当前递归区间左半边有待修改区间的一部分，就递归
        if (r > mid) modify(u << 1 | 1, l, r, c); // 同理
        pushup(u); // 这里pushup的原因，修改了叶结点，所有要上传到每个结点
    }
}

query： 区间查询

int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) { // 如果待修改区间完全包含当前递归区间，那么直接返回当前层的属性值
        return tr[u].sum;
    }
    else {
        pushdown(u); // 这里要pushdown的原因，查询区间的时候是返回精确的当前层数据。
        //其上面的懒标记如果不清空的话，得到的答案就是没有用当前懒标记修改的
        int mid = tr[u].l + tr[u].r >> 1;
        int sum = 0;
        if (l <= mid) sum = query(u << 1, l, r); // 同区间修改
        if (r > mid) sum = (sum + query(u << 1 | 1, l, r)) % p; // 同区间修改
        return sum;
    }
}

并查集

简单并查集

int p[N];
int find (int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

$p[x]$ 数组表示每个元素的父结点，但是由于 $find$ 函数可以压缩路径，所以在使用过一次 $find$ 函数之后，$p[x]$ 就会更新为结点 $x$ 的根节点的下标。

维护每个集合元素个数

维护元素个数的并查集只需要添加一个 $size$ 数组，并且在每次合并操作的时候，更新一下即可。

int pa = find(a), pb = find(b);
if (pa != pb) {
    p[pa] = pb;
    size[pb] += size[pa];
}

维护每个元素到根节点的距离

首先我们需要知道并查集实际上是一个树结构。由于路径压缩，我们不能直接得到每个元素到根节点的距离，所以我们用一个数组来维护和存储。

int find (int x) {
    if (p[x] != x) {
        int t = find(p[x]); // 首先递归，从最后一层回归开始执行下面的操作。
        d[x] += d[p[x]];
        // 由于这一步是从最后一层开始的，所以p[x]都还是当前的p[x]，没有指向根节点。但是d[p[x]]已经更新为到根节点的距离
        p[x] = t; // 把find(p[x])的值赋给p[x]更新当前父结点为根节点下标
    }
    return p[x];
}

哈希

哈希表

哈希表是一种把大的数据范围离散化到小的数据范围的一种方法，由于是大的数据范围映射到小的数据范围，所以会出现多个数对应同一个数的情况，称为冲突。根据处理冲突的方法，分为开放寻址法和拉链法

开放寻址法

int h[N];

// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x)
    {
        t ++ ;
        if (t == N) t = 0;
    }
    return t;
}

拉链法

把哈希值一样的值全部连哈希表数组的某一个元素的后面

int h[N], e[N], ne[N], idx;

// 向哈希表中插入一个数
void insert(int x)
{
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++ ;
}

// 在哈希表中查询某个数是否存在
bool find(int x)
{
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i])
        if (e[i] == x)
            return true;

    return false;
}

字符串哈希

字符串哈希是对字符串的每个前缀做哈希，如果要求每个字串的哈希值，需要用前缀和的思想去求。这里的哈希函数是把字符串的前缀看成一个P进制的数字，字符串的从前往后分别是这个数字的高位到低位。而P的大小是一个经验值，一般是131或者13331，同时由于哈希值过大，我们把哈希值模Q储存，Q的大小也是一个经验值，就用 unsigned long long 的范围来表示，所以我们只需要用这个数据类型来存储哈希值即可，数据范围的溢出直接用来代替取模的过程

初始化前缀数组和P的幂

p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + (int)str[i];
    p[i] = p[i - 1] * P;
}

获取每个字串的哈希值

ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

基础算法

二分

模板1：从左到右找，返回第一个满足check函数要求的下标。

int l = 0, r = n - 1;
while (l < r) {
    int mid = l + r >> 1;
    if (check(mid)) r = mid;
    else l = mid + 1;
}

模板2：从右到左找，返回第一个满足check函数要求的下标。

int l = 0, r = n - 1;
while (l < r) {
    int mid = l + r + 1 >> 1;
    if (check(mid)) l = mid;
    else r = mid - 1;
}

数学

数论

筛质数

普通筛法 $O(nlogn)$

每次用当前数的整数倍去筛（质数或者合数）

void get_primes2(){
    for(int i = 2; i <= n; i++){
        if(!st[i]) primes[cnt++] = i;//把素数存起来
        for(int j = i;j <= n;j += i){//不管是合数还是质数，都用来筛掉后面它的倍数
            st[j] = true;
        }
    }
}

埃氏筛 $O(nloglogn)$

每次用质数的整数倍去筛

void get_primes1(){
    for(int i = 2; i <= n; i++){
        if(!st[i]){
            primes[cnt++]=i;
            for(int j = i;j <= n;j += i) st[j] = true;//可以用质数就把所有的合数都筛掉；
        }
    }
}

线性筛 $O(n)$

每次用 $i$ 的质数倍去筛，加上最后一行的优化后，可以保证每次都是用最小质因数去筛

void get_primes(){
    //外层从2~n迭代，因为这毕竟算的是1~n中质数的个数，而不是某个数是不是质数的判定
    for(int i = 2; i <= n; i++){
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] <= n / i; j++){
        //primes[j]<=n/i:变形一下得到——primes[j]*i<=n,把大于n的合数都筛了就没啥意义了
            st[primes[j] * i] = true;//用最小质因子去筛合数
            //1)当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子，那么只可能是此时的primes[j]<i的
            //最小质因子,所以primes[j]*i的最小质因子就是primes[j];
            //2)当有i%primes[j]==0时,说明i的最小质因子是primes[j],因此primes[j]*i的最小质因子也就应该是
            //prime[j]，之后接着用st[primes[j+1]*i]=true去筛合数时，就不是用最小质因子去更新了,因为i有最小
            //质因子primes[j]<primes[j+1],此时的primes[j+1]不是primes[j+1]*i的最小质因子，此时就应该
            //退出循环，避免之后重复进行筛选。
            if(i%primes[j]==0) break; // 记住是为了每次都让最小质因子更新
        }
    }

}

分解质因数

每次 $x$ 里都已经不存在比 $i$ 小的质数，所以当 $x$ 能整除i的时候，$i$ 一定不是合数，所以每次分解出的都是质因数

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

分解因数

vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}

约数个数，约数之和

如果 $N = p_1^{c_1} + p_2^{c_2} + \cdots + p_k^{c_k}$

约数个数 $(c_1 + 1) \times (c_2 + 1) \times \cdots \times (c_i + 1)$

约数之和 $(p_1^0 + p_1^1 + \cdots +p_1^{c_1})\times (p_2^0 + p_2^1 + \cdots +p_2^{c_2})\times \cdots \times (p_k^0 + p_k^1 + \cdots +p_k^{c_k})$

欧几里得算法

$gcd(a, b) = gcd(b, a \% b)$

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

同余的性质

1. $a \equiv a \mod p$
2. 若 $a \equiv b \mod p$ ，则 $b \equiv a \mod p$
3. 若 $a \equiv b \mod p$，$b \equiv c \mod p$ ，则 $a \equiv c \mod p$
4. 若 $a \equiv b \mod p$ ，$c \equiv d \mod p$ ，则 $a\pm c \equiv b\pm c \mod p$
5. f若 $a \equiv b \mod p$ ，$c \equiv d \mod p$ ，则 $a\times c \equiv b\times c \mod p$
6. 若 $a \equiv b \mod p$ ，则 $a\times n \equiv b\times n \mod p$ ，其中 $n$ 为自然数
7. 若 $ac \equiv bc \mod p$ ，$(c, m)=1$ ，那么 $a \equiv b \mod p$
8. 若 $a \equiv b \mod p$ ，则 $a^t \equiv b^t \mod p$
9. 若 $a \equiv b \mod p_1$，$a \equiv b \mod p_2$ ，则 $a \equiv b \mod [p_1,p_2]$

欧拉函数

$\varphi(n)$ 表示从 $1$ 到 $n$ 中与 $n$ 互质数的个数

令 $n = p_1^{c_1} + p_2^{c_2} + \cdots + p_k^{c_k}$

则 $\varphi(n)=n\times \sum\limits_{i=1}^{k} (1-\frac{1}{p_i})$

（可用容斥原理证明）

朴素方法

int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

筛法

1. 质数 $i$ 的欧拉函数 $\varphi(i) = i - 1$

2. $i\%p_j=0$时，$p_j$是 $i$ 的最小质因数，也是 $p_j\times i$ 的最小质因数，而 $i$ 的其他质因数也在 $p_j\times i$ 中，所以可以知道
   $$\varphi(i) = i \times \sum\limits_{j = 1}^{k} (1-\frac{1}{p_j})$$

$$\varphi(i\times p_j) = p_j \times i \times \sum\limits_{j = 1}^{k} (1-\frac{1}{p_j}) = \varphi(i) \times p_j$$

1. $i\%p_j\not= 0$时，$p_j$ 不是 $i$ 的质因数，但是是 $p_j\times i$ 的最小质因数，而 $i$ 的其他质因数在 $p_j\times i$ 中，但是 $p_j$ 不在其中，所以可以知道
   $$\varphi(i) = i \times \sum\limits_{j = 1}^{k} (1-\frac{1}{p_j})$$

$$\varphi(i\times p_j) = p_j \times (1 - \frac{1}{p_j})\times i \times \sum\limits_{j = 1}^{k} (1-\frac{1}{p_j}) = \varphi(i) \times (p_j - 1)$$

int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉


void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1; // 1
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j]; // 2
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1); // 3
        }
    }
}

欧拉公式

当 $a$ 和 $p$ 互质时
$$a^{\varphi(p)} \equiv 1 \mod p$$
费马定理

当 $n$ 为质数，且当 $a$ 和 $n$ 互质（$a$ 不是 $n$ 的倍数）时
$$a^{p-1} \equiv 1 \mod p$$

快速幂

$$m^k=\prod\limits_{i=0}^{[log_2(m)]} m^{(m>>i\&1)\times 2^i}$$

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

逆元

若 $b$ 和 $p$ 互质，逆元就是下面这个式子中 $x$ 的值，记为 $b^{-1}$
$$b\times x\equiv 1 \mod p$$
当 $p$ 为质数时，且 $b$ 不是 $p$ 的倍数时，由费马小定理，
$$b^{p - 1} \equiv 1\mod p$$

$$b^{p-2}\times b\equiv 1\mod p$$

由于质数 $p$ 一定大于等于 $2$ ，所以此处 $b^{p-2}$ 一定存在且等于逆元的值，即可直接使用快速幂计算逆元

拓展欧几里得算法

裴蜀定理

有一对正整数 $a$ ，$b$ ，那么一定存在整数 $x$ 和 $y$ ，使得
$$ax+by=(a, b)$$
拓展欧几里得算法

拓展欧几里得算法就是求出上述方程的一组解

通过递归的方法处理，递归到底部时，$b$ 的值为 $0$，则 $a$ 的值和 $(a,b)$ 的值一样，所以 $y$ 的值可以为任意值，我们取 $1$ ，$x$ 的值我们取 $0$
$$by +(a \% b)x=d$$

$$by+(a-[\frac{a}{b}]\times b)x=d$$

$$ax+b(y-[\frac{a}{b}]\times x)=d$$

所以两次递归 $exgcd(a,b)$ 和 $exgcd(b,a\%b)$ 之间 $x_1$ 和 $x_2$ ，$y_1$ 和 $y_2$ 之间的关系为
$$x_1 = x_2$$

$$y_1=y_2 - [\frac{a}{b}]\times x$$

// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;
    return d;
}

中国剩余定理

对于整数 $x$ ，满足下列等式，其中 $m_1,m_2\dots,m_k$ 两两互质，
$${\begin{cases} x\equiv a_1\mod m_1 \\ x\equiv a_2\mod m_2 \\ \dots \\ x\equiv a_k\mod m_k \\ \end{cases}}$$
令 $M=\prod\limits_{k}^{1} m_i$ ，$M_i = \frac{M}{m_i}$，$M_i^{-1}$ 为 $M_i$ 在 $\mod m_i$ 意义下的逆元，则，
$$x = \sum\limits_{i=1}^{k} a_i \times M_i\times M_i^{-1}$$

线性代数

高斯消元法解线性方程组

int n;
double a[N][N];

int gauss()  // 高斯消元，答案存于a[i][n]中，0 <= i < n
{
    int c, r;
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;
        for (int i = r; i < n; i ++ )  // 找绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        if (fabs(a[t][c]) < eps) continue;

        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);  // 将绝对值最大的行换到最顶端
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];  // 将当前行的首位变成1
        for (int i = r + 1; i < n; i ++ )  // 用当前行将下面所有的列消成0
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;
    }

    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps)
                return 2; // 无解
        return 1; // 有无穷多组解
    }

    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] * a[j][n];

    return 0; // 有唯一解
}

高斯消元法求异或方程组

int n;
int a[N][N];

int gauss()
{
    int c, r;
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;
        for (int i = r; i < n; i ++ )
            if (a[i][c])
                t = i;

        if (!a[t][c]) continue;

        for (int i = c; i <= n; i ++ ) swap(a[r][i], a[t][i]);
        for (int i = r + 1; i < n; i ++ )
            if (a[i][c])
                for (int j = n; j >= c; j -- )
                    a[i][j] ^= a[r][j];

        r ++ ;
    }

    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (a[i][n])
                return 2;
        return 1;
    }

    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] ^= a[i][j] * a[j][n];

    return 0;
}

组合数学

递推求组合数

求组合数模一个数，数据范围 $0 \le a,b\le 2000$ ，$1\le n\le 10000$ 。

其中 $a,b$ 分别是组合数的下标和上标 $C_a^b$ ，$n$ 表示询问次数。

递推式
$$C_a^b=C_{a-1}^b+C_{a-1}^{b-1}$$
可以理解为第 $a$ 个元素选择或者不选择，两者相加。

const int N = 2010, mod = 1e9 + 7;
int f[N][N];

void init () {
    for (int i = 0; i < N; i++) 
        for (int j = 0; j <= i; j++) 
            if (!j) f[i][j] = 1;
            else f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % mod;
}

预处理阶乘和逆元，求组合数

const int N = 100010, mod = 1e9 + 7;

int fact[N], infact[N];

int qmi(int a, int b, int p) {
    int t = 1;
    while (b) {
        if (b & 1) t = (i64)a * t % p;
        a = (i64)a * a % p;
        b >>= 1;
    }
    return t;
}

void init() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = (i64)fact[i - 1] * i % mod;
        infact[i] = (i64)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

lucas定理求组合数

lucas 定理如下
$$C_a^b\equiv C_{a\%p}^{b\%p} \times C_{a/p}^{b/p}\mod p$$

using i64 = long long;

int qmi(int a, int b, int c) {
    int t = 1;
    while (b) {
        if (b & 1) t = (i64)t * a % c;
        a = (i64)a * a % c;
        b >>= 1;
    }
    return t;
}

int C(int a, int b, int p) {
    if (b > a) return 0;

    int res = 1;
    for (int i = 1, j = a; i <= b; i++, j--) {
        res = (i64)res * j % p;
        res = (i64)res * qmi(i, p - 2, p) % p;
    }
    return res;
}

int lucas(i64 a, i64 b, int p) {
    if (a < p && b < p) return C(a, b, p);
    return (i64)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

高精度组合数

1. 首先把小于等于 $a$ 的自然数筛质数
2. 得到最终结果中每个质因数的个数
3. 用高精度乘法计算出最后结果

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

const int N = 5010;

int primes[N], cnt;
int sum[N];
bool st[N];

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int get(int a, int p) {
    int res = 0;
    while (a) {
        res += a / p;
        a /= p;
    }
    return res;
}

vector<int> mul(vector<int> a, int b) {
    vector<int> res;
    int t = 0;
    for (int i = 0; i < a.size(); i++) {
        t += a[i] * b;
        res.push_back(t % 10);
        t /= 10;
    }
    while (t) {
        res.push_back(t % 10);
        t /= 10;
    }
    return res;
}

int main () {
    int a, b;
    cin >> a >> b;
    get_primes(a);

    for (int i = 0; i < cnt; i++) {
        int p = primes[i];
        sum[i] = get(a, p) - get(b, p) - get(a - b, p);
    }

    vector<int> t;
    t.push_back(1);
    for (int i = 0; i < cnt; i++)
        for (int j = 0; j < sum[i]; j++)
            t = mul(t, primes[i]);

    for (int i = t.size() - 1; i >= 0; i--) cout << t[i];
    cout << endl;

}

容斥原理

$$|\bigcup\limits_{i=1}^{n} A_i|=\sum\limits_{k=1}^{n}(-1)^{k-1}\times\sum\limits_{1\le i_1< i_2<\cdots< i_k\le n}|A_{i_1} \cup A_{i_2}\cup \cdots\cup A_{i_k}|$$

博弈论

nim游戏

先手必胜状态： 可以走到某个先手必败状态

先手必败状态： 无法走到到任意一个先手必败状态

nim游戏： 给定 $n$ 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。假设每堆石子的个数为 $a_1,a_2,\cdots,a_n$ 那么先手必胜当且仅当
$$a_1 \land a_2 \land \cdots \land a_n \not=0$$
证明：

先证明，

状态 $a_1 \land a_2 \land \cdots \land a_n \not=0$ 存在一种方法可以转化为先手必败状态。

首先假设
$$a_1 \land a_2 \land \cdots \land a_n =x \not= 0$$
设 $x$ 二进制表示中最高位 $1$ 为第 $k$ 位，可以知道，在 $a_1$ 到 $a_n$ 中一定有一个数 $a_i$ 满足 $a_i$ 的二进制表达的第 $k$ 位是 $1$，此时，
$$a_i\land x <a_i$$
所以我们可以从第 $i$ 堆中取走 $a_i-(a_i\land x)$ 个，那么 $a_i$ 的值变为 $a_i\land x$，原式，
$$a_1 \land a_2 \land \cdots a_i\land x\land\cdots \land a_n =x \land x=0$$
证明完毕，下证状态 $a_1 \land a_2 \land \cdots \land a_n =0$ 只能转化为先手必胜状态，

容易知道从任意一堆拿走任意个石子，原状态都将变成 $a_1 \land a_2 \land \cdots \land a_n =x \not= 0$

证明完毕。

公平组合游戏ICG

若一个游戏满足：

1. 由两名玩家交替行动；
2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
3. 不能行动的玩家判负；

则称该游戏为一个公平组合游戏。
NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算

设 $S$ 表示一个非负整数集合。定义 $mex(S)$ 为求出不属于集合 $S$ 的最小非负整数的运算，即：
$mex(S) = min(x)$ , $x$ 属于自然数，且 $x$ 不属于 $S$

SG函数

在有向图游戏中，对于每个节点 $x$，设从 $x$ 出发共有 $k$ 条有向边，分别到达节点 $y_1, y_2, …, y_k$，定义 $SG(x)$ 为 $x$ 的后继节点 $y_1, y_2, …, y_k$ 的SG函数值构成的集合再执行 $mex(S)$ 运算的结果，即：
$SG(x) = mex({SG(y_1), SG(y_2), …, SG(y_k)})$
特别地，整个有向图游戏 $G$ 的 $SG$ 函数值被定义为有向图游戏起点 $s$ 的 $SG$ 函数值，即 $SG(G) = SG(s)$。

有向图游戏的和

设 $G_1, G_2, …, G_m$ 是 $m$ 个有向图游戏。定义有向图游戏 $G$，它的行动规则是任选某个有向图游戏 $G_i$，并在 $G_i$ 上行动一步。$G$ 被称为有向图游戏 $G_1, G_2, …, G_m$ 的和。
有向图游戏的和的SG函数值等于它包含的各个子游戏 $SG$ 函数值的异或和，即：
$SG(G) = SG(G_1) \land SG(G_2) \land … \land SG(G_m)$ （我们假设有向图游戏的终点 $SG$ 值为 $0$，每个点的 $SG$ 函数值通过记忆化搜索寻找）