【算法】算法基础课模板大全——第二篇

由于本文章内容太长，导致文章不能以一篇博客形式发布出来，所以我将分为两篇博客进行发布。
【算法】算法基础课模板大全——第一篇
【算法】算法基础课模板大全——第二篇

此笔记适用于AcWing网站的算法基础课，所有的资源链接、代码模板全部来源于网络，这个文档只是做了一些收集和整理，感谢文档中的所有资源原作者们！

笔记作者QQ：2468197060

笔记QQ群聊：1021549627

欢迎一起交流技术

四、数学知识

算法的数学知识定理证明可以在这里查阅：[数学部分简介 - OI Wiki (oi-wiki.org)]：https://oi-wiki.org/math/

试除法判定质数

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}

试除法分解质因数

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

埃氏筛法求质数

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

线性筛法求质数

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

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[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

试除法求所有约数

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;
}

约数个数

约数个数定理和约数和定理公式推导：https://www.bilibili.com/video/BV13R4y1o777

约数个数定理推导：https://www.bilibili.com/video/BV1NY41187GM

using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int main()
{
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    while (n -- )
    {
        int x;
        cin >> x;
        for (int i = 2; i <= x / i; i ++ )
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++ ;
            }
        if (x > 1) primes[x] ++ ;
    }
    LL res = 1;
    for (auto p : primes) res = res * (p.second + 1) % mod;
    cout << res << endl;
    return 0;
}

约数之和

约数个数定理和约数和定理公式推导：https://www.bilibili.com/video/BV13R4y1o777

using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int main()
{
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    while (n -- )
    {
        int x;
        cin >> x;
        for (int i = 2; i <= x / i; i ++ )
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++ ;
            }
        if (x > 1) primes[x] ++ ;
    }
    LL res = 1;
    for (auto p : primes)
    {
        LL a = p.first, b = p.second;
        LL t = 1;
        while (b -- ) t = (t * a + 1) % mod;//遍历b次后得到t=p^b+p^(b-1)+...+p+1
        res = res * t % mod;
    }
    cout << res << endl;
    return 0;
}

代码第26行解释：

约数个数、约数之和的数学公式

$ N = \prod\limits_{i=1}^k p_i^{a_i}=p_1{a_1}\cdot p_2^{a_2}… p_k^{a_k} $

$ 约数个数：\prod\limits_{i=1}^k(a_i+1)=(a_1+1)(a_2+1)…(a_k+1) $

$\begin{array}{rl}约数之和：\prod _{i=1}^k\sum _{j=0}^{a_i}{p}_i^j& =\prod _{i=1}^k(p_i^0+p_i^1+...+p_i^{a_i})\\ & \\ & =(p_1^0+p_1^1+...+p_1^{a_1})(p_2^0+p_2^1+...+p_2^{a_2})...(p_k^0+p_k^1+...+p_k^{a_k})\end{array}$

欧几里得算法(求最大公约数)

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

最小公倍数

int lcm(int a, int b)
{
    return abs(a * b) / gcd(a, b);
}

求欧拉函数

前置知识

互质：互质是公约数只有1的两个整数，叫做互质整数。

欧拉函数定义

$1\sim N-1$中与N互质的数的个数被称为欧拉函数，记为$\varphi (N)$。

若在算数基本定理中，$N=p_1^{a_1}{p}_2^{a_2}...p_m^{a_m}$，则：

$\varphi (N)=N\cdot \frac{p_1-1}{p_1}\cdot \frac{p_2-1}{p_2}\cdot ...\cdot \frac{p_m-1}{p_m}$

欧拉函数推导

首先我们要知道$1,2,\mathrm{3...}N-1,N$与$N$互质的个数是$1\sim N$数列去除N的质因子的倍数。

例如$N=10,即1,2,3,4,5,6,7,8,9,10$去除$N$的质因子的倍数$,则1,\bcancel{2},3,\bcancel{4},\bcancel{5},\bcancel{6},7,\bcancel{8},9,\bcancel{10}.$

显然，$1,3,7,9$与$10$互质。

由上方结论使用容斥原理进行数学推导如下：

$\because N=p_1^{a_1}{p}_2^{a_2}...p_m^{a_m}$

①.从1~n中去掉$p_1,p_2,...,p_k$的所有倍数的个数，即

$n\leftarrow n-\frac{n}{p_1}-\frac{n}{p_2}-...-\frac{n}{p_k}$

②.由容斥原理，$p_i\cdot p_j$的倍数被①减了两次，所以加上所有$p_i\cdot p_j$的倍数的个数（其中$p_i,p_j$是$p_1\sim p_k$的组合），即

$n\leftarrow n+\frac{n}{p_1\cdot p_2}+\frac{n}{p_1\cdot p_3}+...+\frac{n}{p_{k-1}\cdot p_k}$

③.减去所有$p_i\cdot p_j\cdot p_k$的倍数个数，即

$n\leftarrow n-\frac{n}{p_1\cdot p_2\cdot p_3}-\frac{n}{p_1\cdot p_2\cdot p_4}-...-\frac{n}{p_{k-2}\cdot p_{k-1}\cdot p_k}$

④.同理，加上所有$p_i\cdot p_j\cdot p_k\cdot p_l$的倍数个数，即

$n\leftarrow n+\frac{n}{p_1\cdot p_2\cdot p_3\cdot p_4}+\frac{n}{p_1\cdot p_2\cdot p_3\cdot p_5}+...+\frac{n}{p_{k-3}\cdot p_{k-2}\cdot p_{k-1}\cdot p_k}$
KaTeX parse error: Can't use function '\mathord' in text mode at position 1: \̲m̲a̲t̲h̲o̲r̲d̲{\varvdots\rule…
因此，
$$\begin{gathered} \varphi (n)=n-\frac{n}{p_1}-\frac{n}{p_2}-...-\frac{n}{p_k} \\ +\frac{n}{p_1\cdot p_2}+\frac{n}{p_1\cdot p_3}+...+\frac{n}{p_{k-1}\cdot p_k} \\ -\frac{n}{p_1\cdot p_2\cdot p_3}-\frac{n}{p_1\cdot p_2\cdot p_4}-...-\frac{n}{p_{k-2}\cdot p_{k-1}\cdot p_k} \\ +\frac{n}{p_1\cdot p_2\cdot p_3\cdot p_4}+\frac{n}{p_1\cdot p_2\cdot p_3\cdot p_5}+...+\frac{n}{p_{k-3}\cdot p_{k-2}\cdot p_{k-1}\cdot p_k} \\ -... \end{gathered}$$
也就是n减去奇数个质因子的倍数个数，加上偶数个质因子的倍数个数，循环往复。

将上式等价变形，得到

$\varphi (n)=n\cdot (1-\frac{1}{p_1})\cdot (1-\frac{1}{p_2})...\cdot (1-\frac{1}{p_k})$

证必。

代码模板

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;
}

线性筛法求欧拉函数

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

void get_eulers(int n)  // 线性筛法求1~n的欧拉函数
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 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];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

快速幂

快速幂公式证明：[快速幂 - OI Wiki (oi-wiki.org)]：https://oi-wiki.org/math/binary-exponentiation/

// 求 m^k mod p，时间复杂度 O(logk)。
// m为底数，k为幂
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;
}

扩展欧几里得算法

**扩展欧几里得算法讲解：**https://www.bilibili.com/video/BV1KU4y1a7E2/

**优秀题解：**https://www.acwing.com/solution/content/1393

**优秀博客：**https://blog.csdn.net/mango114514/article/details/121048335

x的第一个正解就是(x%k+k)%k

其中，k=b/gcd(a,b)

// 求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;
}

中国剩余定理

**中国剩余定理讲解：**https://www.bilibili.com/video/BV1AN4y1N7Su/

LL exgcd(LL a,LL b,LL &x,LL &y){
    if(b==0){
        x=1,y=0; 
        return a;
    }
    LL d=exgcd(b,a%b,y,x);
    y -= (a/b) * x;
    return d;
}
LL CRT(LL m[],LL r[]){
    LL m=1,ans=0;
    for(int i=1;i<=n;i++)M*=m[i];
    for(int i=1;i<=n;i++){
        LL c=M/m[i],x,y;
        exgcd(c,m[i],x,y);
        ans=(ans+r[i]*c*x%M)%M;
    }
    return (ans%M+M)%M;
}

扩展中国剩余定理

**扩展中国剩余定理讲解：**https://www.bilibili.com/video/BV1Ut4y1F7HG/

LL exgcd(LL a,LL b,LL &x,LL &y){
    if(b==0){
        x=1,y=0; 
        return a;
    }
    LL d=exgcd(b,a%b,y,x);
    y -= (a/b) * x;
    return d;
}
LL EXCRT(LL m[],LL r[]){
    LL m1,m2,r1,r2,p,q;
    m1=m[1],r1=r[1];
    for(int i=2;i<=n;i++){
        m2=m[i],r2=r[i];
        LL d = exgcd(m1,m2,p,q);
        if((r2-r1)%d){
            return -1;
        }
        p=p*(r2-r1)/d;//特解
        p=(p%(m2/d)+m2/d)%(m2/d);
        r1=m1*p+r1;
        m1=m1*m2/d;
    }
    return (r1%m1+m1)%m1;
}

高斯消元法

高斯消元 $O(n^3)$

求解例如下面方程组
KaTeX parse error: Can't use function '\mathord' in text mode at position 1: \̲m̲a̲t̲h̲o̲r̲d̲{\varvdots\rule…
**高斯消元讲解：**https://www.bilibili.com/video/BV1Kd4y127vZ/

模板

// 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 (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; // 有唯一解
}

应用

using namespace std;

const int N = 110;
const double eps = 1e-6;

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

int gauss()
{
    int c, r;// c 代表 列 col ， r 代表 行 row
    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;// 如果当前这一列的最大数都是 0 ，那么所有数都是 0，就没必要去算了，因为它的约束方程，可能在上面几行

        for (int i = c; i < n + 1; i ++ ) swap(a[t][i], a[r][i]); 把当前这一行，换到最上面（不是第一行，是第 r 行）去
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];// 把当前这一行的第一个数，变成 1， 方程两边同时除以 第一个数，必须要到着算，不然第一个数直接变1，系数就被篡改，后面的数字没法算
        for (int i = r + 1; i < n; i ++ )// 把当前列下面的所有数，全部消成 0
            if (fabs(a[i][c]) > eps)// 如果非0 再操作，已经是 0就没必要操作了
                for (int j = n; j >= c; j -- )// 从后往前，当前行的每个数字，都减去对应列 * 行首非0的数字，这样就能保证第一个数字是 a[i][0] -= 1*a[i][0];
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;// 这一行的工作做完，换下一行
    }

    if (r < n)// 说明剩下方程的个数是小于 n 的，说明不是唯一解，判断是无解还是无穷多解
    {// 因为已经是阶梯型，所以 r ~ n-1 的值应该都为 0
        for (int i = r; i < n; i ++ )// 
            if (fabs(a[i][n]) > eps)// a[i][n] 代表 b_i ,即 左边=0，右边=b_i,0 != b_i, 所以无解。
                return 2;
        return 1;// 否则， 0 = 0，就是r ~ n-1的方程都是多余方程
    }
    // 唯一解 ↓，从下往上回代，得到方程的解
    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[j][n] * a[i][j];//因为只要得到解，所以只用对 b_i 进行操作，中间的值，可以不用操作，因为不用输出

    return 0;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n + 1; j ++ )
            cin >> a[i][j];

    int t = gauss();

    if (t == 0)
    {
        for (int i = 0; i < n; i ++ ) printf("%.2lf\n", a[i][n]);
    }
    else if (t == 1) puts("Infinite group solutions");
    else puts("No solution");
    return 0;
}

求组合数

递推法求组合数

**排列组合详细讲解：**https://www.bilibili.com/video/BV1e7411J7SC/

1. 左右两侧斜线都是1，$C_n^0=C_n^n=1$
2. 其他数等于其左上角和右上角两数之和$C_n^{m-1}+C_n^m=C_{n+1}^m$

// c[a][b] 表示从a个苹果中选b个的方案数
int c[N][N];
for (int i = 0; i < N; i ++ )
    for (int j = 0; j <= i; j ++ )
        if (!j) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
//本质上杨辉三角

通过预处理逆元的方式求组合数

模板

// 首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
// 如果取模的数是质数，可以用费马小定理求逆元
int qmi(int a, int k, int p)    // 快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
    fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}

应用

using namespace std;

typedef long long LL;

const int N = 100010,mod=1e9+7;//1e9+7是质数所以与[1,1e9+7)中的数互质

int fact[N],infact[N];

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

int main()
{
    fact[0]=infact[0]=1;
    for (int i = 1; i <= N; i ++ ){
        fact[i]=(LL)fact[i-1]*i%mod;
        infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod;
    }
    
    int n;
    scanf("%d",&n);
    while (n -- ){
        int a,b;
        scanf("%d%d", &a, &b);
        printf("%d\n",(LL)fact[a]*infact[b]%mod*infact[a-b]%mod);
    }
    return 0;
}

Lucas定理求组合数

**Lucas定理证明：**https://blog.csdn.net/Qiuker_jl/article/details/109528164

模板

// 若p是质数，则对于任意整数 1 <= m <= n，有：
// C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)

int qmi(int a, int k, int p)  // 快速幂模板
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int C(int a, int b, int p)  // 通过定理求组合数C(a, b)
{
    if (a < b) return 0;

    LL x = 1, y = 1;  // x是分子，y是分母
    for (int i = a, j = 1; j <= b; i --, j ++ )
    {
        x = (LL)x * i % p;
        y = (LL) y * j % p;
    }

    return x * (LL)qmi(y, p - 2, p) % p;
}

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

应用

using namespace std;

typedef long long LL;

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

int C(int a,int b,int p)//自变量类型int
{
    if(b>a)return 0;//漏了边界条件
    int res = 1;
    // a!/(b!(a-b)!) = (a-b+1)*...*a / b! 分子有b项
    for(int i=1,j=a;i<=b;i++,j--)//i<=b而不是<
    {
        res = (LL)res*j%p;
        res = (LL)res*qmi(i,p-2,p)%p;
    }
    return res;
}
//对公式敲
int lucas(LL a,LL b,int p)
{
    if(a<p && b<p)return C(a,b,p);//lucas递归终点是C_{bk}^{ak}
    return (LL)C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;//a%p后肯定是<p的,所以可以用C(),但a/p后不一定<p 所以用lucas继续递归
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        LL a,b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a,b,p) << endl;
    }
    return 0;
}

分解质因数法求组合数

模板

当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
    1. 筛法求出范围内的所有质数
    2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...
    3. 用高精度乘法将所有质因子相乘

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[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}


int get(int n, int p)       // 求n！中的次数
{
    int res = 0;
    while (n)
    {
        res += n / p;
        n /= p;
    }
    return res;
}


vector<int> mul(vector<int> a, int b)       // 高精度乘低精度模板
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++ )
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }

    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }

    return c;
}

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> res;
res.push_back(1);

for (int i = 0; i < cnt; i ++ )     // 用高精度乘法将所有质因子相乘
    for (int j = 0; j < sum[i]; j ++ )
        res = mul(res, primes[i]);

应用

using namespace std;

const int N = 5010;
int primes[N],cnt=0;
// v[i] 记录数字 i 为素数还是合数，v[i]=true时 i 为合数，否则 i 为素数
bool v[N];
// sum[i]=c 表示质数 i 的个数为 c
int sum[N];

// 线性筛法
void get_primes(int n)
{
    for(int i=2;i<=n;++i)
    {
        // i为质数，则存在primes中
        if(!v[i])primes[cnt++]=i;
        // 给当前数i乘上一个质因子pj
        for(int j=0;primes[j]<=n/i;++j)
        {
            v[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
}

// 计算 n 里面含有质数 p 的个数，这里的计算是不重不漏的。
// p^k的倍数会被计算k次：第一次算p的倍数时，被加一次；第二次算p^2的倍数时，被加一次；第三次算p^3的倍数时，被加一次...第k次算p^k的倍数时，被加一次。总共被加了k次，是不重不漏的。
int get(int n,int p)
{
    int res=0;
    while(n)
    {
        res+=n/p;
        n/=p;
    }
    return res;
}

// A * b：把 b 看成一个整体，然后与 A 中每一位相乘，A中的数字采用小端存储，即低位数字存储在数组的前面，高位数字存储在数组的后面
vector<int> mul(const vector<int>& A,const int b)
{
    if(b==0)return {0};
    vector<int> res;
    // t 表示乘法进位，这里的进位不限于0 1，可以为任意数字
    for(int i=0,t=0,n=A.size();i<n||t>0;++i)
    {
        // 获得当前位的乘积和
        if(i<n)t+=A[i]*b;
        // 添加个位数字
        res.push_back(t%10);
        // 保留进位
        t/=10;
    }

     // 如 1234 * 0 = 0000，需要删除前导0
    while(res.size()>1&&res.back()==0)res.pop_back();
    return res;
}

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

    // 将 a 分解质因数
    get_primes(a);

    for(int i=0;i<cnt;++i)
    {
        // 当前的质数为 p
        int p=primes[i];
        // 用分子里面 p 的个数减去分母里面 p 的个数。这里的计算组合数的公式为a!/(b!*(a-b)!)，因此用 a 里面 p 的个数减去 b 里面 p 的个数和 (a-b) 里面 p 的个数。
        sum[i]=get(a,p)-get(b,p)-get(a-b,p);
    }

    // 使用高精度乘法把所有质因子乘到一块去就好了
    vector<int> res={1};
    for(int i=0;i<cnt;++i)
        // res*p^k，这里是k个p相乘，不是k*p，所以需要使用一个循环
        for(int j=0;j<sum[i];++j)
            res=mul(res,primes[i]);

    // 倒序打印 res 即可，由于采用小端存储，所以高位在后，从后往前打印即可
    for(int i=res.size()-1;i>=0;i--)printf("%d",res[i]);
    return 0;
}

容斥原理应用

经典例题：[890. 能被整除的数 - AcWing题库]：https://www.acwing.com/problem/content/892/

AC代码：

 using namespace std;
 typedef long long LL;
 
 const int N = 20;
 int p[N], n, m;
 
 int main() {
 cin >> n >> m;
 for(int i = 0; i < m; i++) cin >> p[i];
 
 int res = 0;
 //枚举从1 到 1111...(m个1)的每一个集合状态, (至少选中一个集合)
 for(int i = 1; i < 1 << m; i++) {
   int t = 1;             //选中集合对应质数的乘积
   int s = 0;             //选中的集合数量
 
   //枚举当前状态的每一位
   for(int j = 0; j < m; j++){
       //选中一个集合
       if(i >> j & 1){
           //乘积大于n, 则n/t = 0, 跳出这轮循环
           if((LL)t * p[j] > n){    
               t = -1;
               break;
           }
           s++;                  //有一个1，集合数量+1
           t *= p[j];
       }
   }
 
   if(t == -1) continue;  
 
   if(s & 1) res += n / t;              //选中奇数个集合, 则系数应该是1, n/t为当前这种状态的集合数量
   else res -= n / t;                      //反之则为 -1
 }
 
 cout << res << endl;
 return 0;
 }

详细题解：[AcWing 890. 能被整除的数 - AcWing]：https://www.acwing.com/solution/content/29702/

博弈论

NIM游戏

定理1：必胜态的后继状态至少存在一个必败态

定理2：必败态的后继状态均为必胜态

NIM游戏科普：[尼姆游戏（学霸就是这样欺负人的）_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV1ek4y1q7JD/

[再看nim游戏_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV1nt4y1C7Sk/

经典例题：[P2197 【模板】nim 游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)]：https://www.luogu.com.cn/problem/P2197

AC代码：

 using namespace std;
 int T;
 
 int main() {
     cin >> T;
     while (T--) {
         int n;
         scanf("%d", &n);
         int ans = 0;
         for (int i = 0; i < n; i++) {
             int k;
             scanf("%d", &k);
             ans ^= k;
         }
         if (ans)
             puts("Yes");
         else
             puts("No");
     }
     return 0;
 }

结论：

若初态为必胜态($a_1\oplus a_2\oplus ...\oplus a_n\ne 0$).则先手必胜

若初态为必败态($a_1\oplus a_2\oplus ...\oplus a_n=0$).则先手必败

视频讲解：[581 尼姆（Nim）游戏【博弈论】_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV1ns4y1D7dg/

台阶型NIM游戏

经典例题：[892. 台阶-Nim游戏 - AcWing题库]：https://www.acwing.com/problem/content/894/

AC代码：

 using namespace std;
 
 const int N = 100010;
 
 int main()
 {
      int n;
      scanf("%d", &n);
   int res = 0;
      for (int i = 1; i <= n; i ++ )
      {
          int x;
          scanf("%d", &x);
          if (i & 1) res ^= x;
      }
      if (res) puts("Yes");
   else puts("No");
 
      return 0;
 }

**结论：**若奇数台阶上的$a_1\oplus a_3\oplus a_5\oplus ...\ne 0$，则先手必胜，反之先手必败。

视频讲解：[582 台阶型 Nim游戏【博弈论】_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV18M411M7TC/

集合型NIM游戏

经典例题：[893. 集合-Nim游戏 - AcWing题库]：https://www.acwing.com/problem/content/895/

AC代码：

 using namespace std;
 
 const int N=110,M=10010;
 int n,m;
 int f[M],s[N];//s存储的是可供选择的集合,f存储的是所有可能出现过的情况的sg值
 
 int sg(int x)
 {
      if(f[x]!=-1) return f[x];
      //因为取石子数目的集合是已经确定了的,所以每个数的sg值也都是确定的,如果存储过了,直接返回即可
      unordered_set<int> S;
      //set代表的是有序集合(注:因为在函数内部定义,所以下一次递归中的S不与本次相同)
      for(int i=0;i<m;i++)
      {
          int sum=s[i];
          if(x>=sum) S.insert(sg(x-sum));
          //先延伸到终点的sg值后,再从后往前排查出所有数的sg值
      }
      for(int i=0;;i++)
      //循环完之后可以进行选出最小的没有出现的自然数的操作
       if(!S.count(i))
        return f[x]=i;
 }
 
 int main()
 {
      cin>>m;
      for(int i=0;i<m;i++)
      cin>>s[i];
 
      cin>>n;
      memset(f,-1,sizeof(f));//初始化f均为-1,方便在sg函数中查看x是否被记录过
 
      int res=0;
      for(int i=0;i<n;i++)
      {
          int x;
          cin>>x;
          res^=sg(x);
          //观察异或值的变化,基本原理与Nim游戏相同
      }
 
      if(res) printf("Yes");
      else printf("No");
 
      return 0;
 }

思路：转换成有向图游戏

视频讲解：[583 有向图游戏 SG函数【博弈论】_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV1eT411B7A8/

五、动态规划

动态规划三大特征：最优子结构、无后效性、重复子问题

无后效性：现在决定未来，未来与过去无关。

背包问题

01背包每件物品只能装一次
完全背包每件物品可以装无限次
多重背包每件物品只能装有限次（多次）
分组背包每组只能选择一件物品装入（01背包升级）
相关链接：https://zhuanlan.zhihu.com/p/166439661

01背包问题

01背包每件物品只能装一次

视频讲解：[408 背包DP【模板】01背包_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV1kp4y1e794/

using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];//v代表体积，w代表价值
int f[N][N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)//i代表这n件物品
    {
        for(int j=1;j<=m;j++){//j代表背包容量
            if(v[i]>j)//如果v[i]的容量大于当前的背包容量则不装进行下一个
                f[i][j]=f[i-1][j];
            else f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);//如果v[i]的容量小于当前背包容量则可以选择装与不装得到最大值 
        }
    }

    cout<<f[n][m]<<endl;//输出最后的一个一定是最大的
    return 0;
}

01背包，使用滚动数组，倒序遍历

using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];//v代表体积，w代表价值
int dp[N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)//
        
        
        i代表这n件物品
    {
        cin>>v[i]>>w[i];//在线算法
        for(int j=m;j>=v[i];j--){//j代表背包容量，滚动数组必须倒序遍历
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//滚动数组
        }
    }
    cout<<dp[m]<<endl;//输出最后的一个一定是最大的
    return 0;
}

状态转移方程：dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

完全背包问题

完全背包每件物品可以装无限次

视频讲解：[409 背包DP 完全背包【动态规划】_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV15v411y7Qz/

using namespace std;
int v[N],w[N];
int dp[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){//遍历物品
        cin>>v[i]>>w[i];//在线算法
        for(int j=v[i];j<=m;j++){//正序遍历背包容量
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//滚动数组
        }
    }
    cout<<dp[m]<<endl;//输出答案
    return 0;
}

完全背包问题和01背包优化版的区别在于第二重循环的v[i]和m做交换

状态转移方程：dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

多重背包问题1

多重背包每件物品只能装有限次（多次）

using namespace std;
int n,m;
int v[N],w[N],s[N];
int dp[N][N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++)//物品
        for(int j=0;j<=m;j++)//背包容量
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
                dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]*k]+w[i]*k);
    cout<<dp[n][m]<<endl;
    return 0;
}

状态转移方程：dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]*k]+w[i]*k);k为第i个物品的个数

多重背包问题2(二进制优化)

**思路：**转换成2进制，再用01背包求解

视频讲解：[410 背包DP 多重背包 二进制优化【动态规划】_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV1MA41177cg/

using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[M];

int main()
{
    cin >> n >> m;

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s)
        {
            cnt ++ ;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0)
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }//二进制优化操作

    n = cnt;

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

分组背包问题

分组背包每组只能选择一件物品装入

视频讲解：[416 背包DP 分组背包【动态规划】_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV16a411w77X/

using namespace std;
const int N=110;
int f[N];
int v[N][N],w[N][N],s[N];
int n,m,k;

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s[i];
        for(int j=0;j<s[i];j++){
            cin>>v[i][j]>>w[i][j];
        }
    }

    for(int i=0;i<n;i++){
        for(int j=m;j>=0;j--){
            for(int k=0;k<s[i];k++){    //for(int k=s[i];k>=1;k--)也可以
                if(j>=v[i][k])
                    f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);  
            }
        }
    }
    cout<<f[m]<<endl;
}

状态转移方程：f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);

线性DP

数字三角形

视频讲解：[402 线性DP 数字三角形【动态规划】_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV1Rk4y1173p/

using namespace std;
const int N=510,INF=1e9;
int n;
int a[N][N];
int f[N][N];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=i+1;j++){
            f[i][j]=-INF;
        }
    }
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);//状态转移方程
    int res=-INF;
    for(int i=1;i<=n;i++)res=max(res,f[n][i]);
    printf("%d",res);
    return 0;
}

状态转移方程：f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);

最长上升子序列1(LIS)

视频讲解：[403 线性DP 最长上升子序列【动态规划】_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV1KK4y1e7t7/

using namespace std;
const int N = 1010;

int n;
int a[N],f[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )scanf("%d",&a[i]);
    for (int i = 1; i <= n; i ++ ){
        f[i]=1;//只有a[i]一个数
        for (int j = 1; j <= i; j ++ )
            if(a[j]<a[i])
                f[i]=max(f[i],f[j]+1);
    }
    int res=0;
    for (int i = 1; i <= n; i ++ )res=max(res,f[i]);
    printf("%d\n",res);
    return 0;
}

状态转移方程：if(a[j]<a[i])f[i]=max(f[i],f[j]+1);

最长上升子序列2(LIS二分优化)

视频讲解：[404 线性DP 最长上升子序列 二分优化_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV1Kp4y1e77H/

using namespace std;

const int N = 100010;

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

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    int len = 0;
    for (int i = 0; i < n; i ++ )
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];//替换或添加
    }

    printf("%d\n", len);

    return 0;
}

最长公共子序列(LCS)

视频讲解：[405 线性DP 最长公共子序列【动态规划】_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV1EK411K7Eb/

using namespace std;
const int N=1010;
int n,m;
char a[N],b[N];
int f[N][N];

int main()
{
    cin>>n>>m>>a+1>>b+1;
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= m; j ++ ){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

状态转移方程：

f[i][j]=max(f[i-1][j],f[i][j-1]);
if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);

最短编辑距离

给定两个字符串 A和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：

1. 删除–将字符串 A中的某个字符删除。

2. 插入–在字符串 A 的某个位置插入某个字符。

3. 替换–将字符串 A中的某个字符替换为另一个字符。

   现在请你求出，将 A变为 B 至少需要进行多少次操作。

视频讲解：[407 线性DP 编辑距离【动态规划】_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV1gk4y1177j/

using namespace std;
const int N = 1010;
int n,m;
char a[N],b[N];
int f[N][N];

int main()
{
    scanf("%d%s", &n, a+1);
    scanf("%d%s", &m, b+1);

    for (int i = 0; i <= m; i ++ )f[0][i]=i;
    for (int i = 0; i <= n; i ++ )f[i][0]=i;//初始化字符串的编辑操作
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= m; j ++ ){
            f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
            if(a[i]==b[j])f[i][j]=min(f[i][j],f[i-1][j-1]);
            else f[i][j]=min(f[i][j],f[i-1][j-1]+1);//状态转移方程
        }
    }
    printf("%d\n",f[n][m]);
    return 0;
}

状态转移方程:

f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
if(a[i]==b[j])f[i][j]=min(f[i][j],f[i-1][j-1]);
else f[i][j]=min(f[i][j],f[i-1][j-1]+1);//状态转移方程

区间DP

石子合并

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

视频讲解：[428 区间DP【模板】石子合并_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV1gz4y1y7Rv/

using namespace std;
const int N = 310;

int n;
int s[N];
int f[N][N];// 状态表示：集合f[l][r]为[l,r]区间；属性：所堆成的最小值
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )scanf("%d",&s[i]);
    for (int i = 1; i <= n; i ++ )s[i]+=s[i-1];// 前缀和用来求一段区间的和

    for (int len = 2; len <= n; len ++ )// 区间长度为len//枚举长度
        for (int i = 1; i+len-1 <= n; i ++ ){// 意思就是i在区间[1,n-len+1]中去//枚举区间
            int l=i,r=i+len-1;// 区间在[i,i+len-1]中间长度为len//设置l和r的区间
            f[l][r]=1e9;// 初始化最大值
            for (int k = l; k < r; k ++ )// 枚举分界点// 不取r
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);// 找到最小值状态转移方程为f[l][k]+f[k+1][r]+s[r]-s[l-1];
        }
    printf("%d\n",f[1][n]);// 输出区间[1,n]的最小值
    return 0;
}

状态转移方程找到最小值状态转移方程为f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1])

计数类DP

整数划分

一个正整数 n 可以表示成若干个正整数之和，我们将这样的一种表示称为正整数 n 的一种划分。

现在给定一个正整数 n，请你求出 n共有多少种不同的划分方法。

完全背包写法

//完全背包的写法
using namespace std;
const int M=1e9+7;
int f[1010],n;

int main()
{
    cin>>n;
    f[0]=1;
    for (int i = 1; i <= n; i ++ )
        for (int j = i; j <= n; j ++ ){
            f[j]=(f[j-i]+f[j])%M;
        }
    cout<<f[n]<<endl;
    return 0;
}

状态转移方程：f[j]=f[j-i]+f[j]

数位统计DP

计数问题

题目链接：[338. 计数问题 - AcWing题库]：https://www.acwing.com/problem/content/340/

using namespace std;

//因为我们举的分类中，有需要求一串数字中某个区间的数字，例如abcdefg有一个分类需要求出efg+1
int get(vector<int> num,int l,int r){
    int res=0;
    for(int i=l;i>=r;i--)res=res*10+num[i];//这里从小到大枚举的是因为下面count的时候读入数据是从最低为读到最高位，那么此时在num里，最高位存的就是数字的最低位，那么假如我们要求efg，那就是从2算到0
    return res;
}

int power10(int i)//这里有power10是因为有一个分类需要求得十次方得值
{
    int res=1;
    while(i--)res*=10;
    return res;
}

int count(int n,int x){
    if(!n)return 0;//n=0则返回0
    vector<int> num;//num用来存储数中的每一位数字
    while(n){
        num.push_back(n%10);
        n/=10;
    }
    n=num.size();//得出它的长度
    int res=0;
    for (int i = n-1-!x; i >=0; i -- )
    //这里需要注意，我们的长度需要减一，是因为num是从0开始存储，而长度是元素的个数，因此需要减1才能读到正确的数值，而!x出现的原因是因为我们不能让前导零出现，如果此时需要我们列举的是0得出现的次数，那么我们自然不能让他们出现第一位，而是从第二位开始枚举
    {
        if(i<n-1)//其实这里可以不同if判断，因为for循环里面实际上就已经达成了if得判断，但为了方便理解还是加上if来理解，这里i要小于n-1的原因是因为我们不能越界只有7位数就最高从七位数开始读起
        {
            res+=get(num,n-1,i+1)*power10(i);//这里就是第一个分类，000~abc-1，那么此时情况个数就会是abc*103,这里的3取决于后面的efg的长度，假如他是efgh，那么就是4
            //这里的n-1,i+1,自己将数组列出然后根据分类标准就可以得出为什么l是n-1,r=i+1
            if(!x)res-=power10(i);//假如此时我们要列举的是0出现的次数，因为不能出现前导零，这样是不合法也不符合我们的分类情况，例如abcdefg我们列举d，那么他就得从001~abc-1，这样就不会直接到efg，而是会到0efg，因为前面不是前导零，自然就可以列举这个时候0出现的次数，所以要减掉1个power10
        }
        if(num[i]==x)res+=get(num,i-1,0)+1;
        else if(num[i]>x)res+=power10(i);
    }
    return res;//返回res，即出现次数
}

int main()
{
    int a,b;
    while(cin>>a>>b,a||b){
        if(a>b)swap(a,b);//a大于b则交换a，b使得变成合法参数
        for(int i=0;i<10;i++)
            cout<<count(b,i)-count(a-1,i)<<' ';//使用前缀和思想解决[a,b]的i出现的次数
        cout<<endl;
    }
    return 0;
}

状态压缩DP

蒙德里安的梦想

题目链接：[U204941 蒙德里安的梦想 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)]：https://www.luogu.com.cn/problem/U204941

视频讲解：[431 状态压缩DP 蒙德里安的梦想【动态规划】_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV1cv411b7EG/

using namespace std;

const int N = 12,M=1<<N;

int n,m;
long long f[N][M];
bool st[M];

int main()
{
    int n,m;
    while(cin>>n>>m,n||m){
        memset(f, 0, sizeof f);
        //预处理：判断合并列的状态i是否合法
        //如果合并列的某行是1表示横放，是0表示竖放
        //如果合并列不存在连续的奇数个0，即为合法状态
        for (int i = 0; i < 1<<n; i ++ ){
            st[i]=true;
            int cnt=0;//记录合并列中连续0的个数
            for (int j = 0; j < n; j ++ ){
                if(i>>j&1){//如果是1
                    if(cnt&1){//如果连续0的个数是奇数
                        st[i]=false;//记录i不合法
                        break;
                    }
                }else cnt++;//如果是0，记录0的个数
            }
            if(cnt&1)st[i]=false;//处理高位0的个数
        }
        //状态计算
        f[0][0]=1;//第0列不横放是一种合法的方案
        for (int i = 1; i <= m; i ++ )//阶段：枚举列
            for (int j = 0; j < 1<<n; j ++ )//状态：枚举i列的状态
                for (int k = 0; k < 1<<n; k ++ )//状态：枚举i-1列的状态
                    //两列状态兼容：不出现重叠的1，不出现连续奇数个0
                    if((j&k)==0&&st[j|k])
                        f[i][j]+=f[i-1][k];
        cout<<f[m][0]<<endl;//第m列不横放，既答案
    }
    return 0;
}

状态转移方程：

if((j&k)==0&&st[j|k])
 f[i][j]+=f[i-1][k];

最短Hamilton路径

题目链接：[U122241 最短Hamilton路径 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)]：https://www.luogu.com.cn/problem/U122241

using namespace std;

const int N = 20,M = 1 << N;

int n;
int w[N][N];
int f[M][N];//第一维表示是否访问到该点的压缩状态，第二维是走到点j
            //f[i][j]表示状态为i并且到j的最短路径

int main(){
    cin>>n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )//读入i到j的距离
            cin>>w[i][j];
    memset(f, 0x3f, sizeof f);
    f[1][0]=0;
    for (int i = 0; i < 1 << n; i ++ )//枚举压缩的状态
        for (int j = 0; j < n; j ++ )//枚举到0~j的点
            if(i >> j & 1)//该状态存在j点
                for (int k = 0; k < n; k ++ )//枚举从j倒数第二个点k
                    if(i >> k & 1)//倒数点k存在
                        f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);//状态转移方程，在f[i][j]和状态去掉j的点f[i-(i<<j)][k]+w[k][j]取最小值
    cout<<f[(1<<n)-1][n-1]<<endl;//输出状态全满也就是所有点都经过且到最后一个点的最短距离
    return 0;
}

状态转移方程：

f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);

树形DP

没有上司的舞会

题目：[P1352 没有上司的舞会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)]：https://www.luogu.com.cn/problem/P1352

视频讲解：[417 树形DP 没有上司的舞会【动态规划】_哔哩哔哩_bilibili]：https://www.bilibili.com/video/BV1eK411N7Ly/

using namespace std;

const int N = 6010;

int n;
int w[N];//每个节点的高兴度
int h[N], e[N], ne[N], idx;//邻接表存储树

bool st[N];//判断是否有父节点
int f[N][2];

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u){
    f[u][0]=0;
    f[u][1]=w[u];//初始化f[u][1]，当第二维是0则不选该点即高兴度为0，同理f[u][1]=w[u];
    for (int i = h[u]; i!=-1 ; i =ne[i] ){//遍历u的子节点进行深度优先遍历
        int j=e[i];
        dfs(j);
        //状态转移方程
        f[u][0]+=max(f[j][0],f[j][1]);//f[u][0]表示不选择父节点u，所以在f[j][0]和f[j][1]取最大值
        f[u][1]+=f[j][0];//f[u][1]表示选择根节点u，所以累加不选择子节点的f[j][0]
    }
}

int main()
{
    cin>>n;
    for (int i = 1; i <= n; i ++ )cin>>w[i];
    memset(h, -1, sizeof h);
    for (int i = 0; i < n-1; i ++ ){
        int a,b;
        cin>>a>>b;
        add(b,a);
        st[a]=true;//存储是否存在父节点
    }
    int root=1;
    while(st[root])root++;//判断是否是根节点
    dfs(root);//dfs对f[i][j]进行状态转移计算
    cout<<max(f[root][0],f[root][1])<<endl;//取选与不选根节点的最大值
    return 0;
}

状态转移方程：

f[u][0]+=max(f[j][0],f[j][1]);
f[u][1]+=f[j][0];

记忆化搜索

滑雪

题目链接：[P1434 [SHOI2002] 滑雪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)]：https://www.luogu.com.cn/problem/P1434

using namespace std;
const int N = 310;

int n,m;
int h[N][N];
int f[N][N];

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int dp(int x,int y){
    int &v=f[x][y];
    if(v!=-1)return v;//记忆化搜索核心
    v=1;
    for (int i = 0; i < 4; i ++ ){
        int a=x+dx[i],b=y+dy[i];
        if(a>=1&&a<=n&&b>=1&&b<=m&&h[a][b]<h[x][y])//判断是否越界且上一个经过的点的高度是否大于当前高度
            v=max(v,dp(a,b)+1);
    }
    return v;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &h[i][j]);
    memset(f, -1, sizeof f);
    int res=0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            res=max(res,dp(i,j));
    printf("%d\n",res);
    return 0;
}

状态转移方程：v=max(v,dp(a,b)+1);

六、贪心

一个贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择从而得到全局最优的解决方案。—《算法导论》

区间问题

区间选点

给定 N个闭区间$[a_i,b_i]$，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点

输出选择的点的最小数量。

using namespace std;

const int N = 100010;

int n;
struct Range{
    int l,r;
    bool operator <(const Range& W)const{
        return r<W.r;
    }//重载小于号
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ){
        int l,r;
        scanf("%d%d", &l, &r);
        range[i]={l,r};//读入l,r
    }
    sort(range,range+n);//按右端点进行排序
    int res=0,ed=-2e9;//ed代表上一个点的右端点
    for (int i = 0; i < n; i ++ ){
        if(range[i].l>ed){
            res++;//点的数量加一
            ed=range[i].r;
        }
    }
    printf("%d\n",res);
    return 0;
}

最大不相交区间数量

给定 $N$ 个闭区间 $[a_i,b_i]$，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。

输出可选取区间的最大数量。

**结论：**最大不相交区间数量=最少覆盖区间点数

为什么最大不相交区间数=最少覆盖区间点数呢？

因为如果几个区间能被同一个点覆盖
说明他们相交了，所以有几个点就是有几个不相交区间

using namespace std;

const int N = 100010;

int n;
struct Range{
    int l,r;
    bool operator <(const Range& W)const{
        return r<W.r;
    }
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ){
        int l,r;
        scanf("%d%d", &l, &r);
        range[i]={l,r};
    }
    sort(range,range+n);
    int res=0,ed=-2e9;
    for (int i = 0; i < n; i ++ ){
        if(range[i].l>ed){
            res++;
            ed=range[i].r;
        }
    }
    printf("%d\n",res);
    return 0;
}

区间分组

using namespace std;

const int N = 1e5+10;

int n;
struct Range{
    int l,r;
    bool operator<(const Range &W)const{
        return l<W.l;
    }//按左端点排序
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ){
        int l,r;
        scanf("%d%d", &l, &r);
        range[i]={l,r};
    }
    sort(range,range+n);//sort排序
    priority_queue<int,vector<int>,greater<int>> heap;//小根堆维护所有组的右端点最小值
    for (int i = 0; i < n; i ++ ){//从左往右枚举
        auto r=range[i];//选择当前区间
        if(heap.empty()||heap.top()>=r.l)heap.push(r.r);
        else{
            heap.pop();
            heap.push(r.r);
        }
    }
    printf("%d\n",heap.size());
    return 0;
}

Huffman树

合并果子

在果园里，达达把打下的果子按种类分好堆后，打算将它们合成一堆。每次合并两堆果子，消耗的体力是这两堆果子重量之和，经过 n - 1 次合并就能只剩一堆。达达合并果子时消耗的总体力是每次合并耗体力的总和，由于还要搬果子回家，所以要尽量节省体力。已知果子种类数和每种果子的数量，要设计出合并次序方案，让达达耗费体力最少，并输出这个最小体力耗费值。比如有 3 种果子，数量分别是 1、2、9，先合并数量为 1 和 2 的两堆，新堆数量是 3，耗体力 3，再把新堆和数量为 9 的那堆合并，新堆数量变成 12，耗体力 12，总共耗费体力就是 15，且能证明 15 是最小体力耗费值。

#include <iostream>
#include <queue>
#include <functional> // for greater<int>

using namespace std;

int main() {
    // 读取果子的种类数
    int n;
    cin >> n;

    // 使用小顶堆存储每种果子的数量，使用greater<int>确保堆顶元素最小
    priority_queue<int, vector<int>, greater<int>> pq;

    // 读取每种果子的数量，并将其加入小顶堆
    for (int i = 0; i < n; ++i) {
        int ai;
        cin >> ai;
        pq.push(ai);
    }

    // 用于存储总体的体力消耗
    long long total_cost = 0;

    // 当堆中的果子数量大于1时，继续合并
    while (pq.size() > 1) {
        // 取出堆顶的两个最小元素
        int first = pq.top();
        pq.pop();
        int second = pq.top();
        pq.pop();

        // 合并两个最小堆，计算体力消耗
        int merged = first + second;
        total_cost += merged;

        // 将合并后的结果放回堆中
        pq.push(merged);
    }
    // 输出最终的体力消耗值
    cout << total_cost << endl;
    return 0;
}

排序不等式

排队打水

有 $n$个人排队到 $1$ 个水龙头处打水，第 $i$ 个人装满水桶所需的时间是 $t_i$，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？

t[i]从小到大排序

计算公式：$t[0]\times (n-1)+t[1]\times (n-2)+t[2]\times (n-3)...+t[n]\times 0$

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int t[N];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &t[i]);
	sort(t, t + n);//排序
	LL  ans = 0;
	for (int i = 0; i < n; i++) {
		ans += t[i] * (n - i - 1);//计算
	}
	printf("%lld", ans);
	return 0;
}

七、杂项

提高课模板

这里为算法提高课的模板内容，算法提高课的模板较少不好整理，所以专门放在杂项里面。

高级数据结构—AC自动机

[AcWing 1282. 搜索关键词----AC自动机模板题(KMP + trie) - AcWing]：https://www.acwing.com/solution/content/50169/

视频讲解：[F08【模板】AC自动机——信息学竞赛算法]：https://www.bilibili.com/video/BV1tF41157Dy/

模板

void insert(char str[])  // 将str插入Trie中
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!tr[p][u]) tr[p][u] = ++ idx;
        p = tr[p][u];
    }
    cnt[p] ++ ;  // 记录单词出现次数
}

void build()  // 创建AC自动机
{
    int hh = 0, tt = -1;
    for (int i = 0; i < 26; i ++ )
        if (tr[0][i])
            q[ ++ tt] = tr[0][i];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = 0; i < 26; i ++ )
        {
            int p = tr[t][i];
            if (!p) tr[t][i] = tr[ne[t]][i];
            else
            {
                ne[p] = tr[ne[t]][i];
                cnt[p] += cnt[ne[p]];
                q[ ++ tt] = p;
            }
        }
    }
}

应用

题目：[1282. 搜索关键词 - AcWing题库]:https://www.acwing.com/problem/content/1284/

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10010, S = 55, M = 1000010;
int trie[N * S][26], cnt[N * S], idx; //cnt[i]表示以i + 'a'为结尾的个数   idx为当前树节点的指针
char str[M]; //以"/0"为结尾，所以不用每次都更新
int que[N * S], fail[N * S]; //que[]表示队列  ， fail[]为失配指针(下标表示树节点的指针)  
int n;

void insert() {
    int p = 0;
    for (int i = 0; str[i]; ++i) {
        int u = str[i] - 'a';
        if (!trie[p][u]) trie[p][u] = ++idx;
        p = trie[p][u];
    }
    cnt[p]++;
}

void build() { //构造fail数组，bfs
    int hh = 0, tt = -1; //队头和队尾指针
    //根节点是第0层
    for (int i = 0; i < 26; ++i) { //第一层的元素全部入队
        if (trie[0][i]) que[++tt] = trie[0][i];
    }
    while (hh <= tt) {
        int ans = que[hh++];
        //枚举当前队头的26个分支
        for (int i = 0; i < 26; ++i) {
            if (trie[ans][i]) { //如果存在我们就让它的fail指针指向他父亲节点 a 的 fail 指针指向的那个节点（根）的具有相同字母的子节点
                fail[trie[ans][i]] = trie[fail[ans]][i];
                que[++tt] = trie[ans][i]; //当前节点入队
            } else { //就算不存在，不跳，他的值等于父节点的fail只想的具有相同字母的子节点
                trie[ans][i] = trie[fail[ans]][i];
            }
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        memset(cnt, 0, sizeof cnt);
        memset(trie, 0, sizeof trie);
        memset(fail, 0, sizeof fail);
        idx = 0;
        cin >> n;
        for (int i = 0; i < n; ++i) {
            scanf("%s", str);
            insert();
        }
      
        build();
        scanf("%s", str);
      
        int res = 0;
        //j记录当前树节点的指针，初始是根节点 
        for (int i = 0, j = 0; str[i]; ++i) { //枚举总串str的每一个字母
            int u = str[i] - 'a';
            j = trie[j][u]; //跳到下一个树节点
            int p = j; //每次从当前树节点开始

            //fail[p]所指向的树节点如果有结尾标记可以直接算上，因为当前模式串后缀和fail指针指向的模式串部分前缀相同，所以是包含在里面的
            while (p) { //假如模式串"she"可以匹配上，那么匹配到"e"的时候，用fail指针跳到模式串"he"的"e"，那么也一定能够匹配"he"
                res += cnt[p];
                cnt[p] = 0; //去除标记
                p = fail[p];
            }
        }
        cout << res << endl;
    }
    return 0;
}

高级数据结构—树状数组

[楼兰图腾题解 - AcWing]：https://www.acwing.com/solution/content/13818/

视频讲解：[C81【模板】树状数组 点修+区查 区修+点查]：https://www.bilibili.com/video/BV17N4y1x7c6/

模板

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

void update(int x, int c)  // 位置x加c
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int query(int x)  // 返回前x个数的和
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

应用

[241. 楼兰图腾 - AcWing题库]：https://www.acwing.com/problem/content/243/

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 2000010;

typedef long long LL;

int n;
//t[i]表示树状数组i结点覆盖的范围和
int a[N], t[N];
//Lower[i]表示左边比第i个位置小的数的个数
//Greater[i]表示左边比第i个位置大的数的个数
int Lower[N], Greater[N];

//返回非负整数x在二进制表示下最低位1及其后面的0构成的数值
int lowbit(int x)
{
    return x & -x;
}

//将序列中第x个数加上k。
void update(int x, int k)
{
    for(int i = x; i <= n; i += lowbit(i)) t[i] += k;
}
//查询序列前x个数的和
int query(int x)
{
    int sum = 0;
    for(int i = x; i; i -= lowbit(i)) sum += t[i];
    return sum;
}

int main()
{

    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    //从左向右，依次统计每个位置左边比第i个数y小的数的个数、以及大的数的个数
    for(int i = 1; i <= n; i++)
    {
        int y = a[i]; //第i个数

        //在前面已加入树状数组的所有数中统计在区间[1, y - 1]的数字的出现次数
        Lower[i] = query(y - 1); 

        //在前面已加入树状数组的所有数中统计在区间[y + 1, n]的数字的出现次数
        Greater[i] = query(n) - query(y);

        //将y加入树状数组，即数字y出现1次
        update(y, 1);
    }

    //清空树状数组，从右往左统计每个位置右边比第i个数y小的数的个数、以及大的数的个数
    memset(t, 0, sizeof t);

    LL resA = 0, resV = 0;
    //从右往左统计
    for(int i = n; i >= 1; i--)
    {
        int y = a[i];
        resA += (LL)Lower[i] * query(y - 1);
        resV += (LL)Greater[i] * (query(n) - query(y));

        //将y加入树状数组，即数字y出现1次
        update(y, 1);
    }

    printf("%lld %lld\n", resV, resA);

    return 0;
}

高级数据结构—线段树

[浅谈线段树 - AcWing]：https://www.acwing.com/file_system/file/content/whole/index/content/6505356/

[AcWing 1275. 最大数题解 - AcWing]：https://www.acwing.com/solution/content/61919/

视频讲解：[C02【模板】线段树+懒标记 Luogu P3372 线段树]：https://www.bilibili.com/video/BV1G34y1L7b3/

模板

struct Node
{
    int l, r;
    // TODO: 需要维护的信息和懒标记
}tr[N * 4];

void pushup(int u)
{
    // TODO: 利用左右儿子信息维护当前节点的信息
}

void pushdown(int u)
{
    // TODO: 将懒标记下传
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void update(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        // TODO: 修改区间
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, d);
        if (r > mid) update(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return ;  // TODO 需要补充返回值
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        int res = 0;
        if (l <= mid ) res = query(u << 1, l, r);
        if (r > mid) res += query(u << 1 | 1, l, r);
        return res;
    }
}

应用

[1275. 最大数 - AcWing题库]：https://www.acwing.com/problem/content/1277/

#include<iostream>
using namespace std;

const int N = 2e5 + 5;
typedef long long LL;

//线段树的结点, 最大空间开4倍
struct Node{
    int l, r;
    int v;   //最大值
}tr[N * 4];

int m, p;

//u为当前线段树的结点编号
void build(int u, int l, int r) {
    tr[u] = {l, r};
    if(l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

//查询以u为根节点，区间[l, r]中的最大值
int query(int u, int l, int r) {
    //      Tl-----Tr
    //   L-------------R   
    //1.不必分治，直接返回
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;

    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;
    //     Tl----m----Tr
    //        L-------------R 
    //2.需要在tr的左区间[Tl, m]继续分治
    if(l <= mid) v = query(u << 1, l, r);

    //     Tl----m----Tr
    //   L---------R 
    //3.需要在tr的右区间(m, Tr]继续分治
    if(r > mid) v = max(v, query(u << 1 | 1, l, r));

    //     Tl----m----Tr
    //        L-----R 
    //2.3涵盖了这种情况
    return v;
}

//u为结点编号，更新该结点的区间最大值
void modify(int u, int x, int v) {
    if(tr[u].l == tr[u].r) tr[u].v = v;  //叶节点，递归出口
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        //分治处理左右子树, 寻找x所在的子树
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        //回溯，拿子结点的信息更新父节点, 即pushup操作
        tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
    }
}

int main()
{
    //n表示树中的结点个数, last保存上一次查询的结果
    int n = 0, last = 0;  
    cin >> m >> p;

    //初始化线段树, 结点的区间最多为[1, m]。
    build(1, 1, m);  

    while(m--) 
    {
        char op;
        cin >> op;
        if(op == 'A')       //添加结点
        {
            int t;
            cin >> t;
            //在n + 1处插入
            modify(1, n + 1, ((LL)t + last) % p);
            //结点个数+1
            n++;
        }
        else
        {
            int L;
            cin >> L;
            //查询[n - L + 1, n]内的最大值，u = 1，即从根节点开始查询
            last = query(1, n - L + 1, n);
            cout << last << endl;
        }
    }

    return 0;
}

图论—倍增求LCA(最近公共祖先)

[AcWing 1172. 祖孙询问(树上倍增LCA)题解 - AcWing]：https://www.acwing.com/solution/content/20554/

视频讲解：

[D09 倍增算法 P3379【模板】最近公共祖先（LCA）]：https://www.bilibili.com/video/BV1vg41197Xh/

[动画讲解速通LCA|倍增思想|最近公共祖先]：https://www.bilibili.com/video/BV18B66Y6E3T

模板

void bfs(int root)  // 预处理倍增数组
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;  // depth存储节点所在层数
    int hh = 0, tt = 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;
                q[ ++ tt] = j;
                fa[j][0] = t;  // j的第二次幂个父节点
                for (int k = 1; k <= 15; k ++ )
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b)  // 返回a和b的最近公共祖先
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 15; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 15; k >= 0; k -- )
        if (fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}

应用

[1172. 祖孙询问 - AcWing题库]：https://www.acwing.com/problem/content/description/1174/

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 40010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][16];//往上跳2^k步后的父亲节点
int q[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void bfs(int root)//宽搜不容易因为递归层数过多爆栈
{
    memset(depth,0x3f,sizeof depth);
    // 哨兵depth[0] = 0: 如果从i开始跳2^j步会跳过根节点 
    // fa[fa[j][k-1]][k-1] = 0
    // 那么fa[i][j] = 0 depth[fa[i][j]] = depth[0] = 0
    depth[0] = 0,depth[root] = 1;
    queue<int> q;
    q.push(root);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j = e[i];
            if(depth[j]>depth[t]+1)//说明j还没被搜索过
            {
                depth[j] = depth[t]+1;
                q.push(j);//把第depth[j]层的j加进队列
                fa[j][0] = t;//j往上跳2^0步后就是t
                for(int k=1;k<=15;k++)
                {
                    fa[j][k] = fa[fa[j][k-1]][k-1];
                }
            }
        }
    }
}

int lca(int a, int b)
{
    // 为方便处理 当a在b上面时 把a b 互换  
    if (depth[a] < depth[b]) swap(a, b);
    //把深度更深的a往上跳到b
    for (int k = 15; k >= 0; k -- )
        //当a跳完2^k依然在b下面 我们就一直跳
        //二进制拼凑法
        //这里因为
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    //如果跳到了b
    if (a == b) return a;
    //a,b同层但不同节点
    for (int k = 15; k >= 0; k -- )
        // 假如a,b都跳出根节点,fa[a][k]==fa[b][k]==0 不符合更新条件
        if (fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    //循环结束 到达lca下一层
    //lca(a,b) = 再往上跳1步即可
    return fa[a][0];
}

int main()
{
    cin >> n;
    int root = 0;
    memset(h, -1, sizeof h);

    for (int i = 0; i < n; i ++ )
    {
        int a, b;
        cin >> a >> b;
        if (b == -1) root = a;
        else add(a, b), add(b, a);
    }

    bfs(root);//建fa[i][j]

    scanf("%d", &m);
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        int p = lca(a, b);
        if (p == a) cout << "1" << endl;
        else if (p == b) cout << "2" << endl;
        else cout << "0" << endl;
    }
    return 0;
}

洛谷题单

能力全面提升综合题单 - 题单https://www.luogu.com.cn/training/9391

李煜东《算法竞赛进阶指南》题单https://www.luogu.com.cn/training/400

由数据范围反推算法复杂度以及算法内容

一般ICPC或者笔试题的时间限制是1秒或2秒。
在这种情况下，C++代码中的操作次数控制在 $10^7\sim 10^8$ 为最佳。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

1. $n\le 30$, 指数级别, dfs+剪枝，状态压缩dp
2. $n\le 100$ => $O(n^3)$，floyd，dp，高斯消元
3. $n\le 1000$ => $O(n^2)$，$O(n^{2}logn)$，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
4. $n\le 10000$ => $O(n\ast \sqrt{n})$，块状链表、分块、莫队
5. $n\le 100000$ => $O(nlogn)$ => 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
6. $n\le 1000000$ => $O(n)$, 以及常数较小的 $O(nlogn)$ 算法 => 单调队列、 hash、双指针扫描、BFS、并查集，kmp、AC自动机，常数比较小的 $O(nlogn)$ 的做法：sort、树状数组、heap、dijkstra、spfa
7. $n\le 10000000$ => $O(n)$，双指针扫描、kmp、AC自动机、线性筛素数
8. $n\le 10^9$ => $O(\sqrt{n})$，判断质数
9. $n\le 10^{18}$ => $O(logn)$，最大公约数，快速幂，数位DP
10. $n\le 10^{1000}$ => $O((logn{)}^2)$，高精度加减乘除
11. $n\le 10^{100000}$ => $O(logk\times loglogk)，k表示位数$​​，高精度加减、FFT/NTT