ACM常用模板

这里不讨论原理或题目，只给出能直接使用的模板。

字符串

字典树 Trie

//用来查询前缀是否出现过
/*
trie tree的储存方式：将字母储存在边上，边的节点连接与它相连的字母
trie[rt][x]=tot:rt是上个节点编号，x是字母，tot是下个节点编号
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define maxn 2000010
using namespace std;
int tot=1,n;
int trie[maxn][26];
//bool isw[maxn];查询整个单词用
void insert(char *s,int rt)
{
    for(int i=0;s[i];i++)
    {
        int x=s[i]-'a';
        if(trie[rt][x]==0)      //现在插入的字母在之前同一节点处未出现过
        {
            trie[rt][x]=++tot;  //字母插入一个新的位置，否则不做处理
        }
        rt=trie[rt][x];         //为下个字母的插入做准备  
    }
    /*isw[rt]=true;标志该单词末位字母的尾结点，在查询整个单词时用到*/
}
bool find(char *s,int rt)
{
    for(int i=0;s[i];i++)
    {
        int x=s[i]-'a';
        if(trie[rt][x]==0)return false;//以rt为头结点的x字母不存在，返回0
        rt=trie[rt][x];         //为查询下个字母做准备
    }
    return true;
    //查询整个单词时，应该return isw[rt]
}
char s[22];
int main()
{
    tot=0;
    int rt=1;
    scanf("%d",&n);         //字典单词
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        insert(s,rt);
    }
        scanf("%d",&n);     //查询单词（前缀）
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        if(find(s,rt))printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

//查询出现了多少次
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int trie[400001][26],len,root,tot,sum[400001];
bool p;
int n,m;
char s[11];
void insert()
{
    len=strlen(s);
    root=0;
    for(int i=0;i<len;i++)
    {
        int id=s[i]-'a';
        if(!trie[root][id]) trie[root][id]=++tot;
        sum[trie[root][id]]++;//前缀保存
        root=trie[root][id];
    }
}
int search()
{
    root=0;
    len=strlen(s);
    for(int i=0;i<len;i++)
    {
        int id=s[i]-'a';
        if(!trie[root][id]) return 0;
        root=trie[root][id];
    }//root经过此循环后变成前缀最后一个字母所在位置
    return sum[root];
}
int main()
{
    ios::sync_with_stdio(false);
    scanf("%d",&n); //输入单词数
    for(int i=1;i<=n;i++)
    {
        cin>>s;     //输入单词
        insert();
    }
    scanf("%d",&m); //查询数
    for(int i=1;i<=m;i++)
    {
        cin>>s;
        printf("%d\n",search());
    }
}

单模式串字符匹配 Kmp

//KMP T中S的个数
//next数组值2就表示最大公共前后缀长为2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdio.h>
using namespace std;
const int maxn = 1000005;
char S[maxn], T[maxn];
int KMP_next[maxn];
void Getnext()
{
    int j = 0;
    int k = -1;
    KMP_next[0] = -1;
    int Plen = strlen(S);
    while(j < Plen)
    {
        if(k==-1 || S[j]==S[k])
        {
            k++;
            j++;
            KMP_next[j] = k;
        }
        else
            k = KMP_next[k];
    }
}

int KMP()
{
    int i = 0;
    int j = 0;
    int ans = 0;
    Getnext();
    int Slen = strlen(T);
    int Plen = strlen(S);
    while(i<Slen && j<Plen)
    {
        if(j==-1 || T[i]==S[j])
        {
            i++;
            j++;
        }
        else
            j = KMP_next[j];
        if(j == Plen)
        {
            ans++;
            j = KMP_next[j];
        }
    }
    return ans;
}
int main()
{
    int n, KMP_re;
    scanf("%d", &n);
    while(n--)
    {
        scanf("%s%s", T, S);
        //show T, S
        // cout << "T:" << T << endl;
        // cout << "S:" << S << endl;
        KMP_re = KMP();
        printf("%d\n", KMP_re);
        //show next
        // int i;
        // for(i = 0 ; i < 10 ; i++){
        //     cout << KMP_next[i] << ' ';
        // }
        // cout << endl;
    }

    return 0;
}

多模式串字符匹配 AC自动机

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
struct Tree{        //字典树
    int fail;       //失配指针
    int vis[26];    //子节点的位置
    int end;        //标记有几个单词以这个节点结尾
}AC[1000000];       //Trie树
int cnt=0;          //Trie的指针
inline void Build(string s){
    int l=s.length();
    int now=0;      //字典树的当前指针
    for(int i=0;i<l;++i){               //构造Trie树
        if(AC[now].vis[s[i]-'a']==0)    //Trie树没有这个子节点
            AC[now].vis[s[i]-'a']=++cnt;//构造出来
        now=AC[now].vis[s[i]-'a'];      //向下构造
    }
    AC[now].end+=1;                     //标记单词结尾
}
void Get_fail(){    //构造fail指针
    queue<int> Q;   //队列
    for(int i=0;i<26;++i){              //第二层的fail指针提前处理一下
        if(AC[0].vis[i]!=0){
            AC[AC[0].vis[i]].fail=0;    //指向根节点
            Q.push(AC[0].vis[i]);       //压入队列
        }
    }
    while(!Q.empty()){                  //BFS求fail指针
        int u=Q.front();
        Q.pop();
        for(int i=0;i<26;++i){          //枚举所有子节点
            if(AC[u].vis[i]!=0){        //存在这个子节点
                AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
                //子节点的fail指针指向当前节点的
                //fail指针所指向的节点的相同子节点
                Q.push(AC[u].vis[i]);   //压入队列
            }
            else                        //不存在这个子节点
            AC[u].vis[i]=AC[AC[u].fail].vis[i];
                //当前节点的这个子节点指向当
                //前节点fail指针的这个子节点
        }
    }
}
int AC_Query(string s){                 //AC自动机匹配
    int l=s.length();
    int now=0,ans=0;
    for(int i=0;i<l;++i){
        now=AC[now].vis[s[i]-'a'];      //向下一层
        for(int t=now;t&&AC[t].end!=-1;t=AC[t].fail){   //循环求解
            ans+=AC[t].end;
            AC[t].end=-1;
        }
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    string s;
    cnt = 0;
    memset(AC,0,sizeof(AC));
    cin>>n;                 //模式串数量
    for(int i=1;i<=n;++i){  //输入模式串
            cin>>s;
            Build(s);
    }
    AC[0].fail=0;           //结束标志
    Get_fail();             //求出失配指针
    cin>>s;                 //输入文本串
    cout<<AC_Query(s)<<endl;
    return 0;
}

二分

二分快速幂

#include <cmath>
#include <cstdio>
#include <iostream>
#define ll long long
using namespace std;
ll quickpow(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans *= a;
        a *= a;
        b >>= 1;
    }
    return ans;
}
int main() {
    ll n, m;
    cin >> n >> m;
    cout << quickpow(n, m) << endl;
    return 0;
}

矩阵快速幂

//矩阵快速幂
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int modn;           //模数
int n;              //使用的矩阵大小
const int matr=50;  //开的矩阵最大大小
int c[matr][matr];
int w[matr][matr];
int d[matr][matr];  //下面用到的矩阵
void multi(int a[][matr],int b[][matr],int n)//使c = a * b
{
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++){
               c[i][j]+=a[i][k]*b[k][j];
               c[i][j] %= modn;
            }
    return;
}
void quickpow(int re[][matr],int b, int n){//使re = re ^ b
    b--;
    memcpy(w, re, sizeof(w));
    while(b){
        if(b & 1){
            multi(re, w, n);
            memcpy(re, c, sizeof(c));
        }
        multi(w, w, n);
        memcpy(w, c, sizeof(c));
        b >>=1;
    }
    return;
}

int main(){
    std::ios::sync_with_stdio(false);
    int n = 4, i, j, k;
    int A[matr][matr];
    cin >> n >> k >> modn;  //n阶矩阵，k次幂，modn模数

    //输入矩阵
    for(i = 1 ; i <= n ; i++)
        for(j = 1 ; j <= n ; j++)
            cin >> A[i][j];

    //计算
    quickpow(A, k, n);

    //输出矩阵
    for(i = 1 ; i <= n ; i++){
        for(j = 1 ; j <= n ; j++)
            cout << A[i][j] << ' ';
        cout << endl;
    }

    return 0;
}

数论

素数筛

//预先处理好约5800000个素数
//还没加计数用的函数
//时间空间占用都不大
//例题是http://codeforces.com/contest/113/problem/C
//思路参考https://blog.csdn.net/qq_24451605/article/details/48270501
#include <algorithm>
#include <cstdio>
#include <iostream>
#define maxp 5800000           //最多处理素数个数
#define N_for_prime 100000007  //素数筛要用
using namespace std;
int visit[N_for_prime / 32 + 50];
unsigned int pdata[maxp];
int prime[maxp], np = 0;

void init_prime()  //筛素数,数组从0开始
{
    prime[0] = pdata[0] = 2;
    np = 1;
    for(int i = 3; i < N_for_prime; i += 2)  //扫所有奇数
        if(!(visit[i / 32] & (1 << ((i / 2) % 16)))) {
            prime[np] = i;
            pdata[np] = pdata[np - 1] * i;  //预处理
            np++;
            for(int j = 3 * i; j < N_for_prime; j += 2 * i)  //改成i*i会超int范围
                visit[j / 32] |= (1 << ((j / 2) % 16));
        }
}

int main() {
    init_prime();
    // printf("%d\n", prime[78000]);
    // 993121

    int i, j, l, r, count = 0;
    cin >> l >> r;
    for(i = 0; i < maxp - 1; i++) {
        if(prime[i] > r) break;
        if(prime[i] < l || (prime[i] - 1) % 4 != 0) continue;
        count++;
        // printf("%-3d ", prime[i]);
    }
    cout << count << endl;
}

Gcd Lcm ExtGcd

最大公因数、最小公倍数、扩展gcd算法（求ax+by=gcd(x,y)的解）。

#include<iostream>
#include<stdio.h>
using namespace std;
int gcd(int a,int b){
    return b == 0 ? a : gcd(b, a % b);
}

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

int exgcd_t;
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int r = exgcd(b,a%b,x,y);
    exgcd_t = x; x = y;
    y = exgcd_t-a/b*y;
    return r;
}
int main(){
    int x, y;
    // cin >> x >> y;
    x = 12;
    y = 16;
    //gcd
    printf("gcd(%d, %d)\n", x, y);
    cout << gcd(x, y) << endl;

    //lcm
    printf("lcm(%d, %d)\n", x, y);
    cout << lcm(x, y) << endl;

    //solve ax+by=gcd(x, y)
    int a, b;
    // cin >> a >> b;
    a = 4;
    b = 6;
    //solve!!!
    exgcd(a, b, x, y);
    printf("solution of %dx+%dy=gcd(x, y)\n", a, b);
    cout << x << ' ' << y << endl;
    //ax+by=c
    //c % gcd(a, b) == 0
    int c = 8;
    int x2,y2;
    x2 = c / gcd(a, b) * x;
    y2 = c /gcd(a, b) * y;
    printf("solution of %dx+%dy=%d\n", a, b, c);
    cout << x2 << ' ' << y2 << endl;
    //more solution
    int x3 , y3 , i, gg;
    gg = gcd(a, b);
    cout << "more solution" << endl;
    for(i = -5 ; i <= 5 ; i++){
        x3 = x2 + b / gg * i;
        y3 = y2 - a / gg * i;
        printf("%3d %3d\n", x3, y3);
    }
    return 0;
}

大步小步算法 BSGS

// 修改版的扩展BSGS，带一个系数
// 解a^x=b (mod m)， 其中a、m不必互质

ll BSGS(ll a, ll b, ll m, ll k = 1) {
    unordered_map<ll, ll> hs;
    ll cur = b * a % m, t = sqrt(m) + 1;
    for(int B = 1; B <= t; ++B) {
        hs[cur] = B;
        (cur *= a) %= m;
    }
    ll at = qpow(a, t, m), now = at * k % m;
    for(int A = 1; A <= t; ++A) {
        if(hs[now])
            return A * t - hs[now];
        (now *= at) %= m;
    }
    return -100;  // 这里返回一个稍微小一点的负数，确保多次加1后仍然是负数（负数表示无解）
}
// 先把a,b模一下再传参，方便特判也不容易溢出
ll exBSGS(ll a, ll b, ll m, ll k = 1) {
    if(b == 1)  // 特判1
        return 0;
    if(a == 0 && b == 0)  // 特判2
        return 1;
    ll d = gcd(a, m);
    if(b % d)  // 无解
        return -100;
    else if(d == 1)
        return BSGS(a, b, m, k % m);  // 递归出口
    else
        return exBSGS(a, b / d, m / d, k * a / d % m) + 1;  // 递归
}

// 在主函数中应用拓展欧拉定理
ll phiP = phi(p);
ll ans = exBSGS(a % p, b % p, p);
if(ans > phiP)
    ans = ans % phiP + phiP;
if(ans < 0)
    cout << "No Solution" << endl;

//注：上面phi、gcd、qpow这几个函数均省略未写，请自行添加。

欧拉函数

//求单个值
int euler(int x)
{
    int rs = x, a = x;
    for (int i = 2; i * i <= a; i++)
        if (a % i == 0) // 最开始先 a%i == 0 进去马上执行 rs 操作，是因为确保了 i 肯定是素数
        {
            rs = rs / i * (i - 1); // 先进行除法是为了防止中间数据的溢出
            while (a % i == 0)
                a /= i; // 确保下一个 i 是素数
        }
    if (a > 1)
        rs = rs / a * (a - 1);

    return rs;
}

//筛法
const int maxn = 100;
int phi[maxn + 5];
void euler()
{
    for (int i = 1; i <= maxn; i++)
        phi[i] = i;

    for (int i = 2; i <= maxn; i += 2)
        phi[i] /= 2;

    for (int i = 3; i <= maxn; i += 2)
        if (phi[i] == i) // 保证了此时的 i 一定是第一次使用，避免重复 *(1-1/pi)
            for (int j = i; j < maxn; j += i)
                phi[j] = phi[j] / i * (i - 1); // 先进行除法是为了防止中间数据的溢出
}

快速傅里叶变换 FFT

//FFT模板
//最高次为n、m次的多项式相乘
//系数为正整数，若有负数注意最后结果的取整方式
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define N 3000005
typedef complex<double> cplx;
int n, m, l, lim, r[N];
cplx a[N], b[N];
//_basic

void init() {
    //lim为点值表达式项的数量
    for(lim = 1; lim <= m + n; lim <<= 1)
        l++;
    for(int i = 0; i < lim; i++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
}

void fft(cplx *a, int flag) {
    for(int i = 0; i < lim; i++)
        if(i < r[i])
            swap(a[i], a[r[i]]);
    for(int i = 1; i < lim; i <<= 1) {
        cplx wn(cos(pi / i), flag * sin(pi / i));
        for(int p = i << 1, j = 0; j < lim; j += p) {
            cplx w(1, 0);
            for(int k = 0; k < i; k++, w *= wn) {
                cplx x = a[j + k], y = w * a[j + k + i];
                a[j + k] = x + y;
                a[j + k + i] = x - y;
            }
        }
    }
    //逆变换自己除lim,范围0~(n+m)
    if(flag == -1)
        for(int i = 0; i <= n + m; i++)
            a[i] /= lim;
}

int main() {
    //多项式最高n、m次
    scanf("%d%d", &n, &m);
    //注意这里是多项式形式，两式次数为n、m，项数为(n+1)、(m+1)
    int inpt;
    for(int i = 0; i <= n; i++) scanf("%d", &inpt), a[i].real(inpt);
    for(int i = 0; i <= m; i++) scanf("%d", &inpt), b[i].real(inpt);

    //初始化r[]，并将n、m变为点值表示法、系数表示法的最高次数
    init();

    //DFT
    fft(a, 1);
    fft(b, 1);
    //点值相乘
    for(int i = 0; i < lim; i++)
        a[i] = a[i] * b[i];
    //IDFT
    fft(a, -1);

    for(int i = 0; i <= n + m; i++) {
        printf("%d%c", (int)(a[i].real() + 0.5), i == (n + m) ? '\n' : ' ');
        //注意取整方式，fft精度损失略大
    }
    return 0;
}

逆元

//求逆元模板

#define modn (int)(1e9+7)
#define maxn (int)(1e5+5)
//线性递推，modn为质数
//O(N)，求1~(maxn-1)的逆元
long long inv[maxn];
void init_inv(){
    inv[1] = 1;
    for(int i = 2 ; i < maxn ; ++ i)
        inv[i] = (modn - modn / i) * inv[modn % i] % modn;
}

//快速幂法，求单个数的逆元
long long qpow_inv(long long x, long long y = (modn - 2)){
    long long ans = 1;
    while (y > 0){
        if (y & 1)
            (ans *= x) %= modn;
        (x *= x) %= modn;
        y >>= 1;
    }
    return ans;
}

//ext_gcd求法，gcd(a,b)==1
//O(logN)，x（取为正）为a模b的逆元
//求单个数的逆元
void exgcd(int a,int b,int &x,int &y){
    if(!b)return x=1,y=0,void();
    exgcd(b,a%b,y,x);y-=x*(a/b);
}
int inv(int a){
    int x,y;exgcd(a,modn,x,y);
    return (x+modn)%modn;
}

高斯消元

//高斯消元模板，逆矩阵
#include <bits/stdc++.h>
#define p 1000000007
#define ll long long
using namespace std;

ll n;

//定义矩阵及其初等变换
struct matrix {
    ll a[400][400];

    //矩阵第x行和第y行交换
    void change1(ll x, ll y) {
        for(int i = 0; i < n; i++)
            swap(a[x][i], a[y][i]);
    }

    //矩阵第x行乘以k
    void change2(ll x, ll k) {
        for(int i = 0; i < n; i++)
            (((a[x][i] *= k) %= p) += p) %= p;
    }

    //矩阵第x行加上第y行乘以k
    void change3(ll x, ll y, ll k) {
        for(int i = 0; i < n; i++)
            (((a[x][i] += a[y][i] * k % p) %= p) += p) %= p;
    }

    void print() {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                printf("%lld%c", a[i][j], j == n - 1 ? '\n' : ' ');
    }
} a, b;

long long qpow_inv(long long x, long long y = (p - 2)) {
    long long ans = 1;
    while(y > 0) {
        if(y & 1)
            (ans *= x) %= p;
        (x *= x) %= p;
        y >>= 1;
    }
    return ans;
}

int matrix_inv() {
    //把B赋值为单位矩阵
    for(int i = 0; i < n; i++)
        b.a[i][i] = 1;

    //把A消为上三角矩阵
    for(int i = 0; i < n; i++) {
        if(a.a[i][i] == 0)
            for(int j = i; j < n; j++)
                if(a.a[j][i] != 0) {
                    b.change1(i, j);
                    a.change1(i, j);
                    break;
                }
        if(a.a[i][i] == 0)  //矩阵不是满秩的
        {
            // printf("No Solution\n");
            return 0;
        }
        b.change2(i, qpow_inv(a.a[i][i]));
        a.change2(i, qpow_inv(a.a[i][i]));
        for(int j = i + 1; j < n; j++) {
            b.change3(j, i, -a.a[j][i]);
            a.change3(j, i, -a.a[j][i]);
        }
    }

    //把A消为单位矩阵
    for(int i = n - 2; i >= 0; i--)
        for(int j = i + 1; j < n; j++) {
            b.change3(i, j, -a.a[i][j]);
            a.change3(i, j, -a.a[i][j]);
        }

    // b.print();
    return 1;
}

int main() {
    //输入n，A
    scanf("%lld", &n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            scanf("%lld", &a.a[i][j]);

    //输入A，逆矩阵输入到B
    if(matrix_inv() == 0)
        printf("No Solution\n");
    else
        b.print();

    return 0;
}

莫比乌斯函数

//https://www.luogu.com.cn/problem/P3455
//AC
//mobius mode
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 100005;
long long vis[maxn], prime[maxn], mu[maxn], sum[maxn], ww[maxn];
void init(int n) {
    int cnt = 0;
    mu[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(!vis[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= cnt && prime[j] * i <= n; j++) {
            vis[prime[j] * i] = 1;
            if(i % prime[j] == 0)
                break;
            else
                mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + mu[i];
    }
}

int main() {
    int T, n, m, lim, d;
    long long re;
    init(maxn);
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d", &n, &m, &d);
        re = 0;
        n = n / d;
        m = m / d;
        for(int l = 1, r; l <= min(n, m); l = r + 1) {
            r = min(n / (n / l), m / (m / l));
            re += (long long)1 * (n / l) * (m / l) * (sum[r] - sum[l - 1]);
        }
        printf("%lld\n", re);
    }
    return 0;
}

二次剩余

//二次剩余模板
//https://www.luogu.com.cn/problem/P5491
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll qpow(ll a, ll n, ll p) {
    ll ans = 1;
    a %= p;
    while(n) {
        if(n & 1)
            ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}
ll mod(ll a, ll p) {
    return (a % p + p) % p;
}
namespace Qresidue {
    ll legendre(ll a, ll p)  // 勒让德符号
    {
        return qpow(mod(a, p), (p - 1) / 2, p);
    }
    ll find_a(ll n, ll p)  // 找到a满足a^2-n是二次非剩余
    {
        for(ll a = 0; a < p; ++a)
            if(legendre(a * a - n, p) == p - 1)
                return a;
        return -1;
    }
    ll a, p, n;
    struct expnum  // 扩张后的代数结构中的数
    {
        ll a, b;  // a+bi, i^2=a^2-n
    };
    expnum mul(expnum i1, expnum i2) {
        ll c = a * a - n;
        return expnum{(i1.a * i2.a + i1.b * i2.b % p * c) % p,
                      (i1.b * i2.a + i1.a * i2.b) % p};
    }
    expnum qpow(expnum a, int n)  // 在扩张后的代数结构上进行快速幂
    {
        expnum ans{1, 0};
        while(n) {
            if(n & 1)
                ans = mul(ans, a);
            a = mul(a, a);
            n >>= 1;
        }
        return ans;
    }
    ll cul(ll n, ll p) {
        if(n % p == 0)  // 不互质的情形
            return 0;
        if(legendre(n, p) != 1)
            return -1;  // 返回-1表示无解
        Qresidue::n = n, Qresidue::p = p;
        a = find_a(n, p);
        return mod(qpow(expnum{a, 1}, (p + 1) / 2).a, p);
    }
};
// namespace Qresidue

int main() {
    int T;
    ll a, p, re;
    scanf("%d", &T);
    while(T--) {
        scanf("%lld%lld", &a, &p);
        re = Qresidue::cul(a, p);
        if(re == -1) {  //无解
            printf("Hola!\n");
        } else {
            if(re == p - re) {  //两个相等的解
                printf("%lld\n", re);
            } else {  //两个不等的解
                re = min(re, p - re);
                printf("%lld %lld\n", re, p - re);
            }
        }
    }

    return 0;
}

n次剩余

//n次剩余模板
//解x^A=B(mod m)
//可能报错，用c++11可运行

#include <bits/stdc++.h>
typedef long long LL;
int A, B, mod;
int pow(int x, int y, int mod = 0, int ans = 1) {
    if(mod) {
        for(; y; y >>= 1, x = (LL)x * x % mod)
            if(y & 1) ans = (LL)ans * x % mod;
    } else {
        for(; y; y >>= 1, x = x * x)
            if(y & 1) ans = ans * x;
    }
    return ans;
}
struct factor {
    int prime[20], expo[20], pk[20], tot;
    void factor_integer(int n) {
        tot = 0;
        for(int i = 2; i * i <= n; ++i)
            if(n % i == 0) {
                prime[tot] = i, expo[tot] = 0, pk[tot] = 1;
                do ++expo[tot], pk[tot] *= i;
                while((n /= i) % i == 0);
                ++tot;
            }
        if(n > 1) prime[tot] = n, expo[tot] = 1, pk[tot++] = n;
    }
    int phi(int id) const {
        return pk[id] / prime[id] * (prime[id] - 1);
    }
} mods, _p;
int p_inverse(int x, int id) {
    assert(x % mods.prime[id] != 0);
    return pow(x, mods.phi(id) - 1, mods.pk[id]);
}
void exgcd(int a, int b, int &x, int &y) {
    if(!b)
        x = 1, y = 0;
    else
        exgcd(b, a % b, y, x), y -= a / b * x;
}
int inverse(int x, int mod) {
    assert(std::__gcd(x, mod) == 1);
    int ret, tmp;
    exgcd(x, mod, ret, tmp), ret %= mod;
    return ret + (ret >> 31 & mod);
}
std::vector<int> sol[20];
void solve_2(int id, int k) {
    int mod = 1 << k;
    if(k == 0) {
        sol[id].emplace_back(0);
        return;
    } else {
        solve_2(id, k - 1);
        std::vector<int> t;
        for(int s : sol[id]) {
            if(!((pow(s, A) ^ B) & mod - 1))
                t.emplace_back(s);
            if(!((pow(s | 1 << k - 1, A) ^ B) & mod - 1))
                t.emplace_back(s | 1 << k - 1);
        }
        std::swap(sol[id], t);
    }
}
int BSGS(int B, int g, int mod) {  // g^x = B (mod M) => g^iL = B*g^j (mod M) : iL - j
    std::unordered_map<int, int> map;
    int L = std::ceil(std::sqrt(mod)), t = 1;
    for(int i = 1; i <= L; ++i) {
        t = (LL)t * g % mod;
        map[(LL)B * t % mod] = i;
    }
    int now = 1;
    for(int i = 1; i <= L; ++i) {
        now = (LL)now * t % mod;
        if(map.count(now)) return i * L - map[now];
    }
    assert(0);
}
int find_primitive_root(int id) {
    int phi = mods.phi(id);
    _p.factor_integer(phi);
    auto check = [&](int g) {
        for(int i = 0; i < _p.tot; ++i)
            if(pow(g, phi / _p.prime[i], mods.pk[id]) == 1)
                return 0;
        return 1;
    };
    for(int g = 2; g < mods.pk[id]; ++g)
        if(check(g)) return g;
    assert(0);
}
void division(int id, int a, int b, int mod) {  //  ax = b (mod M)
    int M = mod, g = std::__gcd(std::__gcd(a, b), mod);
    a /= g, b /= g, mod /= g;
    if(std::__gcd(a, mod) > 1) return;
    int t = (LL)b * inverse(a, mod) % mod;
    for(; t < M; t += mod) sol[id].emplace_back(t);
}
void solve_p(int id, int B = ::B) {
    int p = mods.prime[id], e = mods.expo[id], mod = mods.pk[id];
    if(B % mod == 0) {
        int q = pow(p, (e + A - 1) / A);
        for(int t = 0; t < mods.pk[id]; t += q)
            sol[id].emplace_back(t);
    } else if(B % p != 0) {
        int phi = mods.phi(id);
        int g = find_primitive_root(id), z = BSGS(B, g, mod);
        division(id, A, z, phi);
        for(int &x : sol[id]) x = pow(g, x, mod);
    } else {
        int q = 0;
        while(B % p == 0) B /= p, ++q;
        int pq = pow(p, q);
        if(q % A != 0) return;
        mods.expo[id] -= q, mods.pk[id] /= pq;
        solve_p(id, B);
        mods.expo[id] += q, mods.pk[id] *= pq;
        if(!sol[id].size()) return;

        int s = pow(p, q - q / A);
        int t = pow(p, q / A);
        int u = pow(p, e - q);
        std::vector<int> res;
        for(int y : sol[id]) {
            for(int i = 0; i < s; ++i)
                res.emplace_back((i * u + y) * t);
        }
        std::swap(sol[id], res);
    }
}
std::vector<int> allans;
void dfs(int dep, int ans, int mod) {
    if(dep == mods.tot) {
        allans.emplace_back(ans);
        return;
    }
    int p = mods.pk[dep], k = p_inverse(mod % p, dep);
    for(int a : sol[dep]) {
        int nxt = (LL)(a - ans % p + p) * k % p * mod + ans;
        dfs(dep + 1, nxt, mod * p);
    }
}
void solve() {
    std::cin >> A >> mod >> B;  //输入参数A,mod,B
    mods.factor_integer(mod);
    allans.clear();
    for(int i = mods.tot - 1; ~i; --i) {
        sol[i].clear();
        mods.prime[i] == 2 ? solve_2(i, mods.expo[i]) : solve_p(i);
        if(!sol[i].size()) {
            return std::cout << 0 << '\n', void(0);
        }
    }
    dfs(0, 0, 1), std::sort(allans.begin(), allans.end());
    std::cout << allans.size() << '\n';  //输出解的个数和解
    for(int i : allans) std::cout << i << ' ';
    std::cout << '\n';
}
int main() {
    std::ios::sync_with_stdio(0), std::cin.tie(0);
    int tc;
    std::cin >> tc;
    while(tc--) solve();
    return 0;
}

区间查询

树状数组

//如何使用树状数组板子
//数组a[maxn],节点C[maxn]
//对C操作：
//修改change(i ,k)——在a[i]加k
//求前缀和sum(x)
//求l到r的和sum(r) - sum(l - 1)
//树状数组用途：单点修改，区间查询（前缀和）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
# define maxn 1000005
using namespace std;
long long int n, q, C[maxn], a[maxn];
inline int lowbit(int x){
    return x & (-x);
}
void change(int i, int k){
    while(i <= n)
        C[i] += k, i += lowbit(i);
}
long long int sum(int x){
    long long int ret = 0;
    while(x)
        ret += C[x], x -= lowbit(x);
    return ret;
}
int main(){
    int type, i, j;
    long long int ques, l, r, x;
    scanf("%d%d", &n, &q);
    for(i = 1 ; i <= n ; i++)
        scanf("%lld", &a[i]);

    memset(C, 0, sizeof(C));//C初始化
    for(x = 1 ; x <= n ; x++)
        for(i = x - lowbit(x) + 1 ; i <= x ; i++)
                C[x] += a[i];

    for(ques = 0 ; ques < q ;ques++){
        scanf("%d%d%d", &type, &l, &r);
        if(type == 1){
            change(l, r);
            continue;
        }
        printf("%lld\n", sum(r) - sum(l - 1));
    }
    return 0;
}

二维树状数组

//二维树状数组模板
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
# define maxn 5000
long long C[maxn][maxn];
int n, m;
inline int lowbit(int x){
    return x & (-x);
}
void update(int x, int y, int z){
    int i = x;
    while(i <= n){
        int j = y;
        while(j <= m){
            C[i][j] += z;
            j += lowbit(j);
        }
        i += lowbit(i);
    }
    return;
}
long long sum(int x, int y){
    long long res = 0, i = x;
    while(i > 0){
        int j = y;
        while(j > 0){
            res += C[i][j];
            j -= lowbit(j);
        }
        i -= lowbit(i);
    }
    return res;
}
int main(){
    int i, j, type;
    long long x, y, a, b, c, d, k;
    memset(C, 0, sizeof(C));
    scanf("%d%d", &n, &m);
    while(scanf("%d", &type) != EOF){
        if(type == 1){
            scanf("%lld%lld%lld", &x, &y, &k);
            update(x, y, k);
            continue;
        }
        scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
        printf("%lld\n",sum(c, d) + sum(a - 1, b - 1) - sum(c, b - 1) - sum(a - 1, d));
        //矩阵按ij从左上往右下排（i行j个）
    }
    return 0;
}

线段树

//线段树模板
#include<iostream>
#include<cstdio>
# define ll long long int           //简化long long
# define maxn (ll)(1e6+5)           //需要的数组a大小
# define lc (x << 1)                //左节点
# define rc (x << 1 | 1)            //右节点
using namespace std;
ll a[maxn];                         //一般数组

//树结构体
struct Segment_Tree{                //线段树(结构体形式)
    long long sum;                  //需要的操作或数据类型
    long long lazy;                 //懒标记
};
Segment_Tree tree[maxn<<2];         //要开四倍maxn大

//向上维护                           //用子节点更新父节点
inline void push_up(ll x){
    tree[x].sum = tree[lc].sum + tree[rc].sum;
    return;
}

//建树                               //输入依次为序号x，左标记l，右标记r
void build(ll x, ll l, ll r){
    if(l == r){
        tree[x].sum = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(lc, l, mid);               //左子树
    build(rc, mid + 1, r);           //右子树 mid + 1防重叠
    push_up(x);                      //把子树信息更新到x节点
    return;
}

//单点更新                             //序号x，维护范围(l, r)，数列编号i，增量k (a[i]加k)
inline void update_point(ll x, ll l, ll r, ll i, ll k){
    if(l == r){
        tree[x].sum += k;
        return;
    }
    ll mid = (l + r) >> 1;
    if(i <= mid){
        update_point(lc, l, mid, i, k);
    }else{
        update_point(rc, mid + 1, r, i, k);
    }
    push_up(x);
}

//修改懒标记                           //修改节点x->(l,r),使其懒标记值加k
inline void free(ll x, ll l, ll r, ll k){
    tree[x].lazy += k;
    tree[x].sum += k * (r - l + 1);
    return;
}

//向下维护
inline void push_down(ll x, ll l, ll r){
    ll mid = (l + r) >> 1;
    free(lc, l, mid, tree[x].lazy);    //向左子树传递
    free(rc, mid + 1, r, tree[x].lazy);//向右子树传递
    tree[x].lazy = 0;
    return;
}

//区间更新                               //维护范围(l,r)；修改区间(q_l,q_r)，使其数据加k
inline void update(ll x, ll l, ll r, ll q_l, ll q_r, ll k){
    if(q_l <= l && q_r >= r){           //需要维护的(l,r)完全在范围内
        free(x, l, r, k);
        return;
    }
    push_down(x, l, r);
    ll mid = (l + r) >> 1;
    if(q_l <= mid){                      //左子树有节点在范围内
        update(lc, l, mid, q_l, q_r, k);
    }
    if(q_r > mid){                       //右子树有节点在范围内
        update(rc, mid + 1, r, q_l, q_r, k);
    }
    push_up(x);                           //日常更新节点x
    return;
}

//区间查询
inline ll query(ll x, ll l, ll r, ll q_l, ll q_r){
    ll res = 0;
    if(q_l <= l && q_r >= r){
        return tree[x].sum;
    }
    ll mid = (l + r) >> 1;
    push_down(x, l, r);                    //释放懒标记
    if(q_l <= mid){
        res += query(lc, l, mid, q_l, q_r);
    }
    if(q_r > mid){
        res += query(rc, mid + 1, r, q_l, q_r);
    }
    return res;
}

int main()
{
    int n, q, i, cmd, ql, qr, k;
    scanf("%d%d", &n, &q);
    for(i = 1 ; i <= n ; i++)
        scanf("%lld", &a[i]);
    build(1, 1, n);
    while(q--){
        scanf("%d", &cmd);
        if(cmd == 1){
            scanf("%d%d%d", &ql, &qr, &k);
            update(1, 1, n, ql, qr, k);
        }else{
            scanf("%d%d", &ql, &qr);
            printf("%lld\n", query(1, 1, n, ql, qr));
        }
    }
    return 0;
}

可持久化线段树

//可持久化线段树模板
#include<iostream>
#include<cstdio>
#define maxn (int)1e5+5
using namespace std;
int a[maxn], rt[maxn], total, now;  //rt[]储存了每个版本的根节点

struct Segment_Tree{
    long long sum, lazy;
    int ls, rs;
}tree[maxn*20];

void build(int &now, int l, int r){
    now = ++total;
    if(l == r){
        tree[now].sum = a[l];
        return;
    }
    int mid = (l+r) / 2;
    build(tree[now].ls, l, mid);
    build(tree[now].rs, mid+1, r);

    //push_up
    tree[now].sum = tree[tree[now].ls].sum + tree[tree[now].rs].sum;
    return;
}

void update(int &now, int l, int r, int q_l, int q_r, int k){
    total++;
    tree[total].ls = tree[now].ls;
    tree[total].rs = tree[now].rs;
    tree[total].sum = tree[now].sum;
    tree[total].lazy = tree[now].lazy;
    now = total;

    tree[now].sum += 1LL * k * (q_r-q_l+1);

    if(q_l == l && r == q_r){
        tree[now].lazy += k;
        return;
    }
    int mid = (l+r) / 2;
    if(q_r <= mid){                             //右子树有节点在范围内
        update(tree[now].ls, l, mid, q_l, q_r, k);
    }else if(q_l > mid){                        //左子树有节点在范围内
        update(tree[now].rs, mid+1, r, q_l, q_r, k);
    }else{
        update(tree[now].ls, l, mid, q_l, mid, k);
        update(tree[now].rs, mid+1, r, mid+1, q_r, k);
    }
    return;
}

//区间查询
long long query(int &now, int l, int r, int q_l, int q_r){
    if(q_l == l && r == q_r){
        return tree[now].sum;
    }

    //巧妙，不用下推了，直接算就对了！
    long long res = 1LL * (q_r-q_l+1) * tree[now].lazy;

    int mid = (l+r) / 2;
    if(q_r <= mid){
        return res + query(tree[now].ls, l, mid, q_l, q_r);
    }
    if(q_l > mid){
        return res + query(tree[now].rs, mid+1, r, q_l, q_r);
    }
    return res + query(tree[now].ls, l, mid, q_l, mid) + query(tree[now].rs, mid+1, r, mid+1, q_r);
}

int main(){
    ios::sync_with_stdio(false);
    int n, q, i, cmd, ql, qr, k, edit;

    total = now = 0;
    cin >> n >> q;
    for(i = 1 ; i <= n ; i++)
        cin >> a[i];
    build(rt[0], 1, n);

    while(q--){
        cin >> cmd;
        if(cmd == 1){           //修改
            cin >> ql >> qr >> k;
            now++;
            update(rt[now]=rt[now-1], 1, n, ql, qr, k);
        }else if(cmd == 2){     //查询现在,用rt[edit]即可查询历史版本
            cin >> ql >> qr;
            cout << query(rt[now], 1, n, ql, qr) << endl;
        }else if(cmd == 3){
            cin >> edit;        //打印历史版本edit
            for(i = 1 ; i <= n ; i++){
                cout << query(rt[edit], 1, n, i, i);
                if(i == n)
                    cout << endl;
                else
                    cout << ' ';
            }
        }else if(cmd == 4){     //回滚到某个版本
            cin >> now;
        }
    }
    return 0;
}

/*
样例
7 10
0 0 0 0 0 0 0
1 2 4 2
1 3 5 1
1 1 7 1
1 4 6 3
1 1 4 3
3 1
3 2
3 3
3 4
3 5
*/

ST表

//http://www.mamicode.com/info-detail-2473899.html
//ST表模板
//快速查询区间最大最小值

#include <iostream>
#include <cstdio>
#include <cmath>
#define maxn 100005
using namespace std;

int ST_N, ST_Q, ST_logMax, ST_P;//ST_N项数字，ST_Q次查询，logMax、ST_P要用的
int a[maxn];                    //原始数列a[n]
int ST_F[maxn][31];             //st表ST_F

void init_ST_F(){               //a[n]输入完以后使用,初始化st表
    int i, j;
    for(int i=1;i<=ST_N;i++) ST_F[i][0]=a[i];
    for(int j=1;j<=ST_logMax;j++)
        for(int i=1;i<=ST_N-(1<<j)+1;i++){
            ST_F[i][j]=max(ST_F[i][j-1], ST_F[i+(1<<(j-1))][j-1]);      //最大值
            // ST_F[i][j]=min(ST_F[i][j-1], ST_F[i+(1<<(j-1))][j-1]);      //最小值
        }
    return;
}

int ST_findm(int l, int r){     //查询
    ST_P=(int)log2(r-l+1);
    return max(ST_F[l][ST_P], ST_F[r-(1<<ST_P)+1][ST_P]);
}

int main()
{
    cin>>ST_N>>ST_Q;            //输入数列项数ST_N和查询次数ST_Q
    ST_logMax=(int)log2(ST_N);  //初始化ST_logMax

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

    init_ST_F();                //初始化ST表

    for(int i=1;i<=ST_Q;i++){   //查询（l到r之间的最值）
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n",ST_findm(l, r));
    }
    return 0;
}

图论、最短路

SPFA 贝尔曼福特算法

//来自百度百科
//福利：这个函数没有调用任何全局变量，可以直接复制！
#include<iostream>
#include<vector>
#include<list>
using namespace std;
struct Edge
{
    int to,len;
};
bool spfa(const int &beg,                           //出发点
          const vector<list<Edge> > &adjlist,       //邻接表，通过传引用避免拷贝
          vector<int> &dist,                        //出发点到各点的最短路径长度
          vector<int> &path)                        //路径上到达该点的前一个点
                                                    //没有负权回路返回0，有返回1
{
    const int INF=0x7FFFFFFF,NODE=adjlist.size();   //用邻接表的大小传递顶点个数，减少参数传递
    dist.assign(NODE,INF);                          //初始化距离为无穷大
    path.assign(NODE,-1);                           //初始化路径为未知
    list<int> que(1,beg);                           //处理队列
    vector<int> cnt(NODE,0);                        //记录各点入队次数，用于判断负权回路
    vector<bool> flag(NODE,0);                      //标志数组，判断是否在队列中
    dist[beg]=0;                                    //出发点到自身路径长度为0
    cnt[beg]=flag[beg]=1;                           //入队并开始计数
    while(!que.empty())
    {
        const int now=que.front();
        que.pop_front();
        flag[now]=0;                                //将当前处理的点出队
        for(list<Edge>::const_iterator              //用常量迭代器遍历邻接表
                i=adjlist[now].begin(); i!=adjlist[now].end(); ++i)
            if(dist[i->to]>dist[now]+i->len)        //不满足三角不等式
            {
                dist[i->to]=dist[now]+i->len;       //更新
                path[i->to]=now;                    //记录路径
                if(!flag[i->to])                    //若未在处理队列中
                {
                    if(NODE==++cnt[i->to])return 1; //计数后出现负权回路
                    if(!que.empty()&&dist[i->to]<dist[que.front()])//队列非空且优于队首（SLF）
                        que.push_front(i->to);      //放在队首
                    else que.push_back(i->to);      //否则放在队尾
                    flag[i->to]=1;                  //入队
                }
            }
    }
    return 0;
}
int main()
{
    int n_num,e_num,beg;                            //含义见下
    cout<<"输入点数、边数、出发点：";
    cin>>n_num>>e_num>>beg;
    vector<list<Edge> > adjlist(n_num + 1,list<Edge>());//默认初始化邻接表
    for(int i=0,p; i!=e_num; ++i)
    {
        Edge tmp;
        cout<<"输入第"<<i+1<<"条边的起点、终点、长度：";
        cin>>p>>tmp.to>>tmp.len;
        adjlist[p].push_back(tmp);
    }
    vector<int> dist,path;                          //用于接收最短路径长度及路径各点
    if(spfa(beg,adjlist,dist,path))cout<<"图中存在负权回路\n";
    else for(int i=1; i<=n_num; ++i)
        {
            cout<<beg<<"到"<<i<<"的最短距离为"<<dist[i]<<"，反向打印路径：";
            for(int w=i; path[w]>=0; w=path[w])cout<<w<<"<-";
            cout<<beg<<'\n';
        }
}

Dijkstra 迪杰斯特拉算法

//队列优化的dijkstra算法模板
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int SIZE = 100010;

//dis[i]表示从起点到i的最短距离
int head[SIZE], node_num, edge_num, ecnt, dis[SIZE];
bool vis[SIZE];

struct NODE{
    int id, w;
};

struct EDGE{
    int frm, nxt, dist;
}edge[SIZE];

bool operator < (NODE a,NODE b){
    return a.w > b.w;
}
void add_edge(int from, int to, int dis){
    edge[++ecnt] = (EDGE){to, head[from], dis};
    head[from] = ecnt;
}

void dijkstra(int u){
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    priority_queue<NODE> q;
    dis[u] = 0;
    q.push((NODE){u,0});
    while(!q.empty()){
        NODE flag = q.top();
        q.pop();
        int v = flag.id;
        if(vis[v]) continue;
        vis[v] = 1;
        for(int i = head[v] ; i ; i = edge[i].nxt){
            int to = edge[i].frm;
            if(dis[to] > dis[v] + edge[i].dist){
                dis[to] = dis[v] + edge[i].dist;
                q.push((NODE){to,dis[to]});
            }
        }
    }
}
int main(){
    int i;
    int from, to, weight, begin;
    scanf("%d%d%d", &node_num, &edge_num, &begin);  //node_num点数,edge_num边数，begin搜索的起点
    for(i = 1 ; i <= edge_num ; i++){               //加入edge_num条边
        scanf("%d%d%d", &from, &to, &weight);
        add_edge(from, to, weight);
        // add_edge(y,x,z); //有向或无向
    }
    dijkstra(begin);        //以s为起点开始搜索

    //把begin点到所有点的距离打出来
    for(int i = 1 ; i <= node_num ; i++)
        printf("%d ",dis[i]);
    return 0;
}

强连通分量

//强连通分量模板
//tarjan算法
//求强连通分量数、其入度和出度、点对应的强连通分量编号
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define INF 0x3f3f3f3f
#define MAXN 100005

using namespace std;

struct Edge {
    int next;
    int to;
}edge[MAXN];

int in[MAXN];       //入度
int out[MAXN];      //出度
int low[MAXN];
int dfn[MAXN];      //dfs序
int vis[MAXN];
int from[MAXN];
int belong[MAXN];   //所属的强连通分量，从１开始编号
int cnt_1;
int cnt_2;
int cnt_3;          //强连通分量总数
stack<int> s1;
int N;              //点数量
int mx1, mx2;

void init(void) {
    memset(in, 0, sizeof(in));
    memset(out, 0, sizeof(out));
    memset(low, 0, sizeof(low));
    memset(dfn, 0, sizeof(dfn));
    memset(vis, 0, sizeof(vis));
    memset(from, 0, sizeof(from));
    memset(belong, 0, sizeof(belong));
    cnt_1 = 0;
    cnt_2 = 0;
    cnt_3 = 0;
    mx1 = 0;
    mx2 = 0;
    while (s1.size())
        s1.pop();
}

//添加边x向y
void add(int x, int y) {
    edge[++cnt_1].next = from[x];
    edge[cnt_1].to = y;
    from[x] = cnt_1;
}

void tarjan(int x) {
    s1.push(x);
    vis[x] = 1;
    dfn[x] = low[x] = ++cnt_2;
    for (int j = from[x]; j; j = edge[j].next) {
        int k = edge[j].to;
        if (!dfn[k]) {
            tarjan(k);
            low[x] = min(low[x], low[k]);
        }
        else if (vis[k] && dfn[k] < low[x])
            low[x] = dfn[k];
    }
    if (dfn[x] == low[x]) {
        int temp;
        cnt_3++;
        do{
            temp = s1.top();
            s1.pop();
            vis[temp] = 0;
            belong[temp] = cnt_3;
        } while (temp != x);
    }
}

//求每个强连通分量的入度和出度
void in_out(void) {

    for (int i = 1; i <= N; i++) {
        for (int j = from[i]; j; j = edge[j].next) {
            int k = edge[j].to;
            if (belong[i] != belong[k]) {
                ++in[belong[k]];
                ++out[belong[i]];
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    int m;
    cin >> N >> m;  //点数Ｎ，边数ｍ
    int i, j;
    int a, b;
    init();

    for (i = 0; i < m; i++) {
        cin >> a >> b;
        add(a, b);
    }

    for (int i = 1; i <= N; i++) {
        if(!dfn[i]) tarjan(i);
    }

    in_out();

    cout << "there are/is " << cnt_3 << " group(s)" << endl;

    cout << "node a belong group B" << endl;
    for(i = 1 ; i <= N ; i++){
        cout << i << " -> " << belong[i] << endl;
    }

    cout << "group B 's in and out" << endl;
    for(i = 1 ; i <= cnt_3 ; i++){
        cout << "group" << i << ": " << in[i] << " --- " << out[i] << endl;
    }

    return 0;
}

/*
样例
8 9
1 2
2 4
4 3
3 2
4 5
4 6
6 7
7 8
8 6
*/

动态规划

背包问题

详见这里，《背包九讲》笔记。

/*
容量为V的背包
第i件物品费用为c[i]，价值为w[i]，
每种物品只能用一次（只有一件）。
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    ll i, v, V, N;
    ll f[10005], c[10005], w[i];
    cout << "01bag" << endl;
    for(i = 1 ; i <= N ; i++){
        // 01背包
        for(v = V ; v >= 0 ; v--){
        // 完全背包，只需要改一下顺序
        // for(v = 0 ; v <= V ; v++){
            f[v] = max(f[v], f[v-c[i]] + w[i]);
        }  
    }
    cout << max(12,999) << endl;

    return 0;
}

数位dp

//数位dp模板
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int a[20];
//dp[位数][状态数]
ll dp[20][200];
// 位置、状态、前导零、数字上界
// state表示状态，具体问题具体分析
ll dfs(int pos, ll state, bool lead, bool limit){
    if(pos == -1) return state;
    if(!limit && !lead && dp[pos][state] != -1) return dp[pos][state];
    int up = limit ? a[pos] : 9;

    ll ans = 0;
    for(int i = 0 ; i <= up ; i++){
        //主要需要修改的地方，考虑状态用dfs如何转移
        ans += dfs(pos-1, state + i, lead && i == 0, limit && i == a[pos]);
    }

    if(!limit && !lead) dp[pos][state] = ans;
    return ans;
}
ll solve(ll x){
    int pos = 0;
    while(x){
        a[pos++] = x % 10;
        x /= 10;
    }
    //初始状态，数字放在a[0]~a[pos-1]里
    return dfs(pos-1, 0, true, true);
}
int main(){
    ll le, ri;
    //dp初始化，如果问题不变则只需要初始化一次
    memset(dp, -1, sizeof(dp));
    cin >> le >> ri;
    cout << solve(ri) - solve(le - 1) << endl;
    return 0;
}

并查集

#include<iostream>
#include<cstring>
#define maxn 100
using namespace std;
int par[maxn];  //树
int height[maxn]; //树的高度

//初始化
void init(int n){
    for(int i = 0 ; i < n ; i++){
        par[i] = i;
        height[i] = 0;
    }
}

//查询树的根
int find(int x){
    if(par[x] == x) return x;
    else return par[x] = find(par[x]);
}

//合并x和y所属的集合
void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return;
    //合并时使树的高度尽量小
    if(height[x] < height[y]) par[x] = y;
    else{
        par[y] = x;
        if(height[x] == height[y]) height[x]++;
    }
}

//判断x和y是否属于同一个集合
bool same(int x, int y){
    return find(x) == find(y);
}

int main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    init(n);
    return 0;
}

---

知道的暂时就这些，以后再补充吧。