板子

起手

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
#define ios                          \
    std::cin.sync_with_stdio(false); \
    std::cin.tie(0);
typedef long long ll;
#define int long long
#define pii pair<int, int>
const int N = 500005;
#define endl '\n'
#define Endl '\n'
#define ENDL '\n'
void slove()
{
}
signed main()
{
    // ios;
    int t;
    cin >> t;
    while (t--)
    {
        slove();
    }
}

高精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
const int N = 1e5;   //最大容量
string a, b;    // 输入字符串
int la, lb, lc; // a,b,c长度
int A[N] = {0}, B[N] = {0}, C[N] = {0};
void add(int A[], int B[], int C[]) // 加
{
    for (int i = 0; i < lc; i++)
    {
        C[i] += A[i] + B[i];
        C[i + 1] += (C[i] / 10);
        C[i] %= 10;
    }
}
bool cmp(int A[], int B[]) // 比较大小
{
    if (la != lb)
        return la > lb;
    else
        for (int i = la - 1; ~i; i--)
            if (A[i] != B[i])
                return A[i] > B[i];
    return 1; // 相等返回1,避免结果为-0
}
void sub(int A[], int B[], int C[]) // 减法，使用了比较大小cmp
{
    if (!cmp(A, B))
        cout << "-", swap(A, B);
    for (int i = 0; i < lc; i++)
    {
        if (A[i] < B[i])
            A[i] += 10, A[i + 1]--; // 借位
        C[i] = A[i] - B[i];         // 存差
    }
    while (lc && C[lc] == 0) // 前导零
        lc--;
    lc++;
}
void mul(int A[], int B[], int C[]) // 乘法
{
    for (int i = 0; i < la; i++)
        for (int j = 0; j < lb; j++)
        {
            C[i + j] += A[i] * B[j];       // 累加乘积
            C[i + j + 1] += C[i + j] / 10; // 进位
            C[i + j] %= 10;                // 存余
        }
    while (lc && C[lc] == 0) // 前导零
        lc--;
    lc++;
}
void div(int A[], int b, int C[]) // 除法，b为int以内
{
    long long temp = 0; // 临时被除数
    for (int i = la - 1; ~i; i--)
    {
        temp = temp * 10 + A[i]; // 临时被除数
        C[i] = temp / b;         // 存商
        temp %= b;               // 余数
    }
    while (lc && C[lc] == 0) // 前导零
        lc--;
    lc++;
}
void Input(int A[]) // 转化字符串A
{
    for (int i = 0; i < la; i++)
        A[la - i - 1] = a[i] - '0';
}
void Output(int C[])
{
    for (int i = lc - 1; ~i; i--)
        cout << C[i];
}

快速幂

快速幂 快速幂取模

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
long long quickpow(long long a, long long n, long long p) // 快速幂 a^n
{
    int res = 1;
    while (n)
    {
        if (n & 1)
            res = res * a;
        a = a * a, n >>= 1;
    }
    return res;
}
long long quickpowmodp(long long a, long long n, long long p) // 快速幂取模 a^n%p
{
    int res = 1;
    while (n)
    {
        if (n & 1)
            res = res * a % p;
        a = a * a % p, n >>= 1;
    }
    return res;
}

矩阵快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*求矩阵a的k次方*/
long long n, k;
const int N = 500;
const int mod = 1000000007;
struct Matrix // 定义矩阵a, res
{
    long long c[N][N] = {0};
} a, res;
Matrix operator*(Matrix &x, Matrix &y) // 矩阵乘法
{
    Matrix t; // 临时矩阵
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++) // x的列数，y的行数必须相等，内层效率高
                t.c[i][j] = (t.c[i][j] + x.c[i][k] * y.c[k][j]) % mod;
    return t;
}
void quickpow(long long k) // 快速幂
{
    for (int i = 1; i <= n; i++)
        res.c[i][i] = 1; // 单位矩阵
    while (k)
    {
        if (k & 1)
            res = res * a;
        a = a * a, k >>= 1;
    }
}

数论

判断素数-试除法

1
2
3
4
5
6
7
8
9
10
11
bool prime(int x)
{
    if (x == 1)
        return 0;
    for (int i = 2; i <= x / i; i++)
    {
        if (x % i == 0)
            return 0;
    }
    return 1;
}

分解质因数

$$
n=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\dots p_s^{\alpha_s},p_1<p_2<p
_3<\dots<p_S
$$

1
2
3
4
5
6
7
8
9
10
11
12
const int N = 500005;
int a[N]; // 代表含质因子i的个数
void decompose(int x)
{
    for (int i = 2; i <= x / i; i++)
    {
        while (x % i == 0)
            a[i]++, x /= i;
    }
    if (x > 1)
        a[x]++;
}

埃氏筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int N = 100000010; // 最大
int vis[N] = {0};        // 划掉合数
int prim[N] = {0};       // 记录质数
int cnt;                 // 质数个数
void Eratosthenes(int n) // 埃氏筛法
{
    for (long long i = 2; i <= n; ++i)
        if (!vis[i])
        {
            prim[++cnt] = i;
            for (long long j = i * i; j <= n; j += i)
                vis[j] = 1;
        }
}

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//注意空间，prim有效从下标1开始
const int N = 100000010; // 最大
int vis[N] = {0};        // 划掉合数
int prim[N] = {0};       // 记录质数
int cnt = 0;             // 质数个数
void get_prim(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (vis[i] == 0)
            prim[++cnt] = i;
        for (int j = 1; 1ll * i * prim[j] <= n; j++)
        {
            vis[i * prim[j]] = 1;
            if (i % prim[j] == 0)
                break;
        }
    }
}

欧拉函数

**欧拉函数 **$\varphi(n)$ 指小于 $n$ ，并且与 $n$ 互质的数的个数。

  • 当 $n$ 为质数，$\varphi (n)=p-1$
  • 当 $p$ 为质数，$\varphi (p^k)=(p-1)*p^{k-1}$
  • 当 $n$ 为合数，$\varphi (n)=s*\prod \limits_{i=1}^s{\frac{p_i-1}{pi}}$
    • $n=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\dots p_s^{\alpha_s},p_1<p_2<p
      _3<\dots<p_S$

欧拉定理

若 $gcd(a,m)=1$ ，则 $a^{\varphi(m)=1(%m)}$；

扩展欧拉定理

$a^b=\begin{align*}\begin{split} \left {\begin{array}{lr}a^b,& b<\varphi(m)\a^{b%\varphi(m)+\varphi(m)},& b\ge\varphi(m)\end{array}\right.\end{split}\end{align*} (%m)$

约数

约数个数定理：若 $n=\prod \limits_{i=1}^s{p_i^{\alpha_i}}$ ，约数个数 $d(n)=\prod \limits_{i=1}^s{(\alpha_i+1)}$

约数和定理：若 $n=\prod \limits_{i=1}^s{p_i^{\alpha_i}}$ ，约数和 $f(n)=\prod \limits_{i=1}^s{\sum_{j=0}^{\alpha_{i}}{p_i^j}}$

莫比乌斯函数

莫比乌斯函数：$\begin{align*}\begin{split}M_{1}= \left {\begin{array}{lr}1,& n=1\0,& n含相同质因子\(-1)^s,& s为n的不同质因子的个数\end{array}\right.\end{split}\end{align*}$

欧几里得算法

$$
当a>b,则gcd(a,b)=gcd(b,a%b)
$$

1
2
3
4
5
6
7
8
9
int gcd(int a, int b)
{
    if (a < b) // 确保a大
        swap(a, b);
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

裴蜀定理

一定存在整数 $x,y$ ，满足 $ax+by=gcd(a,b)$

扩展欧几里得算法

$Q$ ：求 $ax+by=gcd(a,b)$ 一组整数解

当 $b=0$ 时，$ax+by=a$，$x=1$，$y=0$

当 $b\neq 0$时，由裴蜀定理， $ax+by=gcd(a,b)$

​ $gcd(b,a%b)=bx_1+(a%b)y_1=ay_1+b(x_1-\lfloor\frac{a}{b}\rfloor y_1)$

​ $x=y_1,y=x_1-\lfloor\frac{a}{b}\rfloor y_1$

​ $\begin{align*}\begin{split} \left {\begin{array}{lr}x=x_0+\frac{b}{gcd(a,b)}*k\y=y_0-\frac{a}{gcd(a,b)}k\end{array}\right.\end{split}\end{align} (考虑ax+by=0构造)$

1
2
3
4
5
6
7
8
9
10
11
12
int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int x1, y1, d;
    d = exgcd(b, a % b, x1, y1);
    x = y1, y = x1 - a / b * y1;
    return d;
}

组合数

组合数原理

组合数原理：$C_{a}^{b}=\frac{a!}{b!(a-b)!}=C_{a-1}^{b-1}+C_{a-1}^{b}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
typedef long long ll;
const int N = 100010, MOD = 1e9 + 7;
ll f[N] = {0};       // x!mod MOD的值
ll g[N] = {0};       //(x!)^(-1)mod MOD的值
ll qpow(ll a, int b) // 快速幂
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
void init() // 初始化
{
    f[0] = g[0] = 1;
    for (int i = 1; i < N; i++)
    {
        f[i] = f[i - 1] * i % MOD;
        g[i] = g[i - 1] * qpow(i, MOD - 2) % MOD;
    }
}
ll getC(ll n, ll m) // 返回
{
    return f[n] * g[m] % MOD * g[n - m] % MOD;
}

卢卡斯定理

卢卡斯定理：$C_n^m=C_{n/p}^{m/p}C_{n%p}^{m%p}(%p),p为质数$

  • $C_{p}^{x}=0(%p),0<x<p$
  • $(1+p)^x=1+x^p(%p)$
1
2
3
4
5
6
7
//递归，配合组合数原理使用
int lucas(ll n, ll m, int p)
{
    if (m == 0)
        return 1;
    return lucas(n / p, m / p, p) * getC(n % p, m % p, p) % p;
}

卡特兰数

卡特兰数：$C_{2n}^n-C_{2n}^{n-1}=\frac{C_{2n}^n}{n+1}$

二项式反演

二项式定理：$(a+b)^n=\sum_{i=0}^{n}{C_{n}^{i}a^{n-1}b^i}$；

  • $\sum_{i=0}^{n}{C_i^n(-1)^i}=[n=0] $

背包

01（逆序）/完全（顺序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int v[N] = {0}, w[N] = {0};
#define endl '\n'
// int f[1005][1005] = {0}; // 前i件物品容量为j
int f[N] = {0};
signed main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++)
        // for (int j = m; j >= v[i]; j--) // 逆序 01背包
        // for (int j = v[i]; j <= m; j++) // 顺序 完全背包
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m];
}

多重背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const int N = 2005; // 2000<2^12
int n, m;
int v1, w1, s;            // 体积 价值 数量
int v[N * 12], w[N * 12]; // 存体积 存价值
int f[N];

int main()
{
    cin >> n >> m;
    // 二进制拆分
    int num = 1;
    for (int i = 1; i <= n; i++)
    {
        cin >> v1 >> w1 >> s;
        for (int j = 1; j <= s; j <<= 1)
        {
            v[num] = j * v1;
            w[num++] = j * w1;
            s -= j;
        }
        if (s) // 剩余
            v[num] = s * v1, w[num++] = s * w1;
    }
    // 01背包
    for (int i = 1; i < num; i++)
        for (int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m];
}

混合背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int n, m;
int f[1010], g[1010];
int q[1010];
void ZeroOnePack(int v, int w) // 01
{
    for (int j = m; j >= v; j--)
        f[j] = max(f[j], f[j - v] + w);
}
void CompletePack(int v, int w) // 完全
{
    for (int j = v; j <= m; j++)
        f[j] = max(f[j], f[j - v] + w);
}
void MultiplePack(int v, int w, int s) // 多重
{
    memcpy(g, f, sizeof(f));
    for (int j = 0; j < v; j++)
    {
        int h = 0, t = -1;
        for (int k = j; k <= m; k += v)
        {
            if (h <= t && q[h] < k - s * v)
                h++;
            if (h <= t)
                f[k] = max(g[k], g[q[h]] + (k - q[h]) / v * w);
            while (h <= t && g[k] >= g[q[t]] + (k - q[t]) / v * w)
                t--;
            q[++t] = k;
        }
    }
}
int main()
{
    int v, w, s;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d %d", &v, &w, &s); // s不同选择不同
        if (s == -1)
            ZeroOnePack(v, w); // 01背包
        else if (s == 0)
            CompletePack(v, w); // 完全背包
        else
            MultiplePack(v, w, s); // 多重背包
    }
    cout << f[m];
}

博弈论

Nim游戏

结论：若初态为必败态（$a_1\oplus a_2 \oplus a_3 \dots \oplus a_n \neq 0)$ ，先手必败；

​ 若初态为必胜态（$a_1\oplus a_2 \oplus a_3 \dots \oplus a_n = 0)$ ，先手必胜；

台阶Nim

结论：只看奇数台阶，转化为Nim游戏；

SG函数

有向图游戏：给定一个有向无环图，图中只有一个起点，在起点上放一个棋子，两个玩家轮流沿着有向边推动棋子，每次走一步，不能走的玩家失败。

$mex(S)$：不属于集合 $S$ 中的最小非负数；

$SG$函数 ：设状态(节点) $x$ 有 $k$ 个后继状态（子节点）$y_1,y_2,\dots,y_k$，$SG(x)=mex({SG(y_1),SG(y_2),\dots,SG(y_k)})$

$SG$定理 ：由 $n$ 个有向图游戏组成的组合游戏，设起点分别为 $s_1,s_2,…s_n$ ，当 $SG(s_1) \oplus SG(s_2) \oplus \dots \oplus SG(s_n) \neq 0$，先手必败；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
const int N = 2005, M = 10005;
int n, m, k, a, b, x;
int h[N], to[M], ne[M], tot; // 邻接表
int f[N];

void add(int a, int b)
{
    to[++tot] = b, ne[tot] = h[a], h[a] = tot;
}
int sg(int u)
{
    // 记忆化搜索
    if (f[u] != -1)
        return f[u];
    // 把子节点的sg值插入集合
    set<int> S;
    for (int i = h[u]; i; i = ne[i])
        S.insert(sg(to[i]));
    // mex运算求当前节点的sg值并记忆
    for (int i = 0;; i++)
        if (!S.count(i))
            return f[u] = i;
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++)
        scanf("%d%d", &a, &b), add(a, b);
    memset(f, -1, sizeof f);
    int res = 0;
    for (int i = 0; i < k; i++)
        scanf("%d", &x), res ^= sg(x);
    if (res)
        puts("win");
    else
        puts("lose");
}

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n, a[1000005]; // n表示数字个数，a存储

int find(int q)
{
    int l = 0, r = n + 1; // 开区间
    while (l + 1 < r)     // l+1=r时结束
    {
        int mid = l + r >> 1;
        if (a[mid] >= q)
            r = mid; // 最小化
        else
            l = mid;
    }
    return a[r] == q ? r : -1;
}

树

BFS（宽搜）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N = 100010;
vector<int> e[N];
int vis[N];
queue<int> q;
void bfs(int s)
{
    vis[s] = 1;
    q.push(s);
    while (q.size())
    {
        int x = q.front();
        q.pop(); // 出队
        for (auto y : e[x])
        {
            if (vis[y])
                continue;
            vis[y] = 1;
            q.push(y); // 入队
        }
    }
}

DFS（深搜）

1
2
3
4
5
6
7
8
9
10
11
const int N = 100010;
vector<int> e[N];
void dfs(int u, int fa)
{
    for (auto v : e[u])
    {
        if (v == fa)
            continue;
        dfs(v, u);
    }
}

最小生成树（prim算法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#define inf __INT32_MAX__
const int N = 5010;
int n, cnt, ans;
struct edge
{
    int v, w;
};
vector<edge> e[N];
int d[N], vis[N];

bool prim(int s)
{
    for (int i = 0; i <= n; i++)
        d[i] = inf;
    d[s] = 0;
    for (int i = 1; i <= n; i++)
    {
        int u = 0;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && d[j] < d[u])
                u = j;
        vis[u] = 1; // 标记u已出圈
        ans += d[u];
        if (d[u] != inf)
            cnt++;
        for (auto ed : e[u])
        {
            int v = ed.v, w = ed.w;
            if (d[v] > w)
                d[v] = w;
        }
    }
    return cnt == n;
}

最短路 （Dijkstra 算法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#define inf 2147483647
const int N = 100010;
int n;
struct edge
{
    int v, w;
};
vector<edge> e[N];
int d[N], vis[N];
priority_queue<pair<int, int>> q;
void dijkstra(int s)
{
    for (int i = 0; i <= n; i++)
        d[i] = inf;
    d[s] = 0;
    q.push({0, s});
    while (q.size())
    {
        auto t = q.top();
        q.pop();
        int u = t.second;
        if (vis[u])
            continue; // 再出队跳过
        vis[u] = 1;   // 标记u已出队
        for (auto ed : e[u])
        {
            int v = ed.v, w = ed.w;
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                q.push({-d[v], v}); // 大根堆
            }
        }
    }
}

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <algorithm>
using namespace std;
#define lc p << 1
#define rc p << 1 | 1
#define N 100005
#define ll long long
ll n, w[N];
struct node
{
    ll l, r, sum, add;
} tr[N * 4];
void pushup(ll p)
{
    tr[p].sum = tr[lc].sum + tr[rc].sum;
}
void pushdown(ll p)
{
    auto &u = tr[p], &l = tr[lc], &r = tr[rc];
    if (u.add)
    {
        l.sum += u.add * (l.r - l.l + 1),
            r.sum += u.add * (r.r - r.l + 1),
            l.add += u.add,
            r.add += u.add,
            u.add = 0;
    }
}
void build(ll p, ll l, ll r)
{
    tr[p] = {l, r, w[l], 0};
    if (l == r)
        return;        // 是叶子则返回
    ll m = l + r >> 1; // 不是叶子则裂开
    build(lc, l, m);
    build(rc, m + 1, r);
    pushup(p);
}
void update(ll p, ll x, ll y, ll k)
{
    if (x <= tr[p].l && tr[p].r <= y) // 覆盖则修改
    {
        tr[p].sum += (tr[p].r - tr[p].l + 1) * k;
        tr[p].add += k;
        return;
    }
    ll m = tr[p].l + tr[p].r >> 1; // 不覆盖则裂开
    pushdown(p);
    if (x <= m)
        update(lc, x, y, k);
    if (y > m)
        update(rc, x, y, k);
    pushup(p);
}
ll query(ll p, ll x, ll y)
{
    if (x <= tr[p].l && tr[p].r <= y) // 覆盖则返回
        return tr[p].sum;
    ll m = tr[p].l + tr[p].r >> 1; // 不覆盖则裂开
    pushdown(p);
    ll sum = 0;
    if (x <= m)
        sum += query(lc, x, y);
    if (y > m)
        sum += query(rc, x, y);
    return sum;
}
int main()
{
    ll m, op, x, y, k;
    cin >> n >> m;
    for (ll i = 1; i <= n; i++)
        cin >> w[i];
    build(1, 1, n);
    while (m--)
    {
        cin >> op >> x >> y;
        if (op == 2)
            cout << query(1, x, y) << endl;
        else
            cin >> k, update(1, x, y, k);
    }
    return 0;
}

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int N = 100010;
int n, m, x, y, z;
int fa[N];
int find(int x)
{
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}
vector<int> siz(N, 1); // 记录并初始化子树的大小为1
void unionset(int x, int y)
{
    x = find(x), y = find(y);
    if (x == y)
        return;
    if (siz[x] > siz[y])
        swap(x, y);
    fa[x] = y;
    siz[y] += siz[x];
}

字符串哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
using namespace std;

typedef unsigned long long ull;
const int N = 1000010, MOD = 131;
char s[N];
int n;
// p[i]=P^i, h[i]=s[1~i]的hash值
ull p[N], h[N];

// 预处理 hash函数的前缀和
void init()
{
    p[0] = 1, h[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        p[i] = p[i - 1] * MOD;
        h[i] = h[i - 1] * MOD + s[i];
    }
}
// 计算s[l~r]的 hash值
ull get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
// 判断两子串是否相同
bool substr(int l1, int r1, int l2, int r2)
{
    return get(l1, r1) == get(l2, r2);
}

命名空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
i64 fpow(i64 x, i64 r)
{
    i64 result = 1;
    while (r)
    {
        if (r & 1)result = result * x % mod;
        r >>= 1;
        x = x * x % mod;
    }
    return result;
}

namespace binom {
    i64 fac[N], ifac[N];
    int __ = []
    {
        fac[0] = 1;
        for (int i = 1; i <= N - 5; i++)
            fac[i] = fac[i - 1] * i % mod;
        ifac[N - 5] = fpow(fac[N - 5], mod - 2);
        for (int i = N - 5; i; i--)
            ifac[i - 1] = ifac[i] * i % mod;
        return 0;
    }();

    inline i64 C(int n, int m)
    {
        if (n < m || m < 0)return 0;
        return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
    }

    inline i64 A(int n, int m)
    {
        if (n < m || m < 0)return 0;
        return fac[n] * ifac[n - m] % mod;
    }
}
using namespace binom;

板子jiangly

并查集（DSU）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
struct DSU
{
    std::vector<int> f, siz;

    DSU() {}
    DSU(int n)
    {
        init(n);
    }

    void init(int n)
    {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x)
    {
        while (x != f[x])
        {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y)
    {
        return find(x) == find(y);
    }

    bool merge(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
        {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x)
    {
        return siz[find(x)];
    }
};