初级数学学习笔记

数论基本概念

1. 整除法

$n = ak + r(0 \le r < a) \to k = \lfloor \frac{n}{a} \rfloor$

2. 算数基本定理

$p_i$ 为素数，且 $p_i < p_{i + 1}$，则有：

$n = p_1^{a_1} p_2^{a_2} \cdots p_m ^ {a_m}$

3. 最大公约数与最小公倍数

$\gcd (a,b) \times \operatorname{lcm} (a,b) = \gcd (a,b) \times \frac{a \times b}{\gcd(a,b)} = a \times b$

4. 求一个数的约数个数

一个数的每个因子均由若干个素因子构成，第 $i$ 个素因子共有 $i + 1$ 种取法，所以总个数为（$k$ 为素因子的总个数）：

$\prod_{i = 1}^{k} (a_i + 1)$

代码如下：

int divisor (int n)//算数基本定理
{
    int tot = 1;
    for (int i = 2;i * i <= n;++i)
    {
        if (n % i == 0)
        {
            int cnt = 0;
            while (n % i == 0) n /= i,++cnt;//素因子i 在 num 中的个数
            tot *= (cnt + 1);
        }
    }
    if (n > 1) tot *= 2;//剩下的 n 也为素数的情况
    return tot;
}

int divisor_direct (int n)//直接暴力枚举
{
    int cnt = 0;
    for (int i = 1;i * i <= n;++i)
    {
        if (n % i == 0)
        {
            ++cnt;
            if (n / i != i) ++cnt;//完全平方数时会重复计算
        }
    }
    return cnt;
}

素数筛法

1. 朴素筛法

将每一个数的所有倍数都筛去，时间复杂度为：$O(\frac{n}{2} + \frac{n}{3} + \cdots + 1)$。所以当 $\lim(n \to \infty)$ 时，近似为 $O(n\log n)$。

2. 常数优化

枚举小的那个因子。

1
2
3

for (int i = 2;i * i <= n;++i)
    if (!flag[i])
        for (int j = i * i;j <= n;j += i) flag[j] = 1;

3. 线性筛

时间复杂度为 $O(n)$。

void work (int n)//保证每个数最多被筛一次
{
    for (int i = 2;i <= n;++i)
    {
        if (!flag[i]) p[++cnt] = i;//素数
        for (int j = 1;j <= cnt;++j)
        {
            if (i * p[j] > n) break;//边界
            flag[i * p[j]] = 1;//p[j] 是 i * p[j] 的最小素因子
            if (i % p[j] == 0) break;//之后 p[j] 不为 i * p[j] 的最小素因子
            //若 p[j] = 2,i = 4，则之后 p[j] = 3,i = 4 不符合条件。否则 12 = 2*6 = 3 * 4 被筛的次数 > 1
        }
    }
}

欧几里得算法

1. 辗转相减

若 $a > b$，则 $\gcd (a,b) = \gcd (a - b,b)$。

2. 辗转相除

若 $a > b$，则 $\gcd (a,b) = \gcd (b,a \bmod b)$。

int gcd (int a,int b)
{
    if (a < b) swap (a,b);
    return (!b) ? a : gcd (b,a % b);
}

扩展欧几里得算法

由欧几里得算法可知 $ax + by = \gcd (a,b)$ 一定存在一组解。那么求解 $ax + by = c$ 时，过程如下：

$ax + by = c(a > b)\\\texttt{设 } ax' + by' = \gcd (a,b)\\\texttt{则辗转相减知 } (a - b) \times x_1 + b \times y_1 = \gcd (a,b)\\\therefore a \times x_1 + b \times (y_1 - x_1) = \gcd (a,b)\\\therefore x = x_1,y = y_1 - x_1\\\\\texttt{由辗转相除代替辗转相减，则有 } b \times x_1 + a \bmod b \times y_1 = \gcd (a,b)\\\because a \bmod b = a - \lfloor \frac{a}{b} \rfloor \times b\\\therefore b \times x_1 + (a - \lfloor \frac{a}{b} \rfloor \times b) \times y_1 = \gcd (a,b)\\\therefore a \times y_1 + b \times (x_1 - \lfloor \frac{a}{b} \rfloor \times y_1) = \gcd (a,b)\\\therefore x = y_1,y = x_1 - \lfloor \frac{a}{b} \rfloor \times y_1$

不断递归得到 $\gcd (a,b) \times x + 0 \times y = \gcd (a,b)$，得到特解 $x = 1,y = 0$。

int exgcd (int a,int b,int &x,int &y)
{
    int g = a;
    if (b)
    {
        g = exgcd (b,a % b,x,y);
        x -= (a / b) * y;
        swap (x,y);
    }
    else x = 1,y = 0;//一组特解
    return g;
}

设 $k_1 = \dfrac{a}{\gcd (a,b)},k_2 = \dfrac{b} {\gcd (a,b)}$，显然 $\gcd (k_1,k_2) = 1$。设 $x,y$ 的最小变化单位是 $d_1,d_2$，则此时 $k_1 = d_2,k_2 = d_1$，所以通解是：

$\begin{cases}x = x + k \times \dfrac{b}{\gcd(a,b)}\\y = y - k \times \dfrac{a}{\gcd(a,b)}\\k \in \rm{Z} \\\end{cases}$

欧拉函数

2. 积性函数

设 $p$ 为质数，求 $\phi(p^k)$：

$\phi(p^k) = p^k - \frac{p^k}{p} = p^k - p^{k-1} = (p-1)p^{k-1}$

同理，对于两个不同质数的乘积 $n = p_1^{a_1} p_2^{a_2}$，由容斥原理：

$\begin{aligned} \phi(p_1^{a_1} p_2^{a_2}) &= p_1^{a_1} p_2^{a_2} - \frac{p_1^{a_1} p_2^{a_2}}{p_1} - \frac{p_1^{a_1} p_2^{a_2}}{p_2} + \frac{p_1^{a_1} p_2^{a_2}}{p_1 p_2} \\ &= p_1^{a_1} p_2^{a_2} \left(1 - \frac{1}{p_1} - \frac{1}{p_2} + \frac{1}{p_1 p_2}\right) \\ &= p_1^{a_1} p_2^{a_2} \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \\ &= \phi(p_1^{a_1}) \times \phi(p_2^{a_2}) \end{aligned}$

因此，欧拉函数是积性函数。

3. 计算通式

将 $n$ 进行质因数分解：

$n = p_1^{a_1} p_2^{a_2} \cdots p_m^{a_m}$

由积性函数性质：

$\begin{aligned} \phi(n) &= \phi(p_1^{a_1}) \times \phi(p_2^{a_2}) \times \cdots \times \phi(p_m^{a_m}) \\ &= \prod_{i=1}^m (p_i - 1)p_i^{a_i-1} \\ &= \prod_{i=1}^m p_i^{a_i} \times \frac{p_i - 1}{p_i} \\ &= n \times \prod_{i=1}^m \frac{p_i - 1}{p_i} \end{aligned}$

这个公式可以直接用于计算任意正整数的欧拉函数值。

5. 代码

根据欧拉函数通式求解。

void work (int n)
{
    phi[1] = 1;
    for (int i = 2;i <= n;++i) phi[i] = i;//先标记为自己，方便标记质数，也方便为公式法求解
    for (int i = 2;i <= n;++i)
    {
        if (phi[i] == i)//为素数
            for (int j = i;j <= n;j += i) phi[j] = phi[j] / i * (i - 1);//其中的一个 (pi - 1) / pi
    }
}

根据线性筛实现 $O(n)$ 的时间复杂度求解。

void work (int n)
{
    phi[1] = 1;
    for (int i = 2;i <= n;++i)
    {
        if (!flag[i])
        {
            p[++cnt] = i;
            phi[i] = i - 1;//素数 p 的欧拉函数为 p - 1
        }
        for (int j = 1;j <= cnt;++j)
        {
            if (i * p[j] > n) break;
            flag[i * p[j]] = 1;
            if (i % p[j] == 0)
            {
                phi[i * p[j]] = phi[i] * p[j];//若 p 能整除 n / p，则 φ (n) = φ (n / p) * p
                break;
            }
            phi[i * p[j]] = phi[i] * (p[j] - 1);//若 p 与 n / p 互质，且 p 为质数，则 φ (n)  = φ (n / p) * (p - 1)
        }
    }
}

利用性质 $f$ 的求解。

void work (int n)
{
    for (int i = 1;i <= n;++i) phi[i] = i;
    for (int i = 1;i <= n;++i)
        for (int j = i + i;j <= n;j += i) phi[j] -= phi[i];//减去自己所有因子的值即为 φ(i)
}

欧拉定理

如果 $a,n$ 为正整数，且 $\gcd (a,n) = 1$，则 $a^ {\phi(n)} ≡ 1 \pmod n$。

已知 $a,n \in \rm{N_{+}}$，且 $\gcd (a,n) = 1$。求证 $a^{\phi(n)} \equiv 1 \pmod n$。

$证明：令集合\ A = \{x_1,x_2,\cdots,x_{\phi(n)}\}\ 来表示所有不大于\ n\ 且与其互质的数\\再令集合\ B = \{ax_1 \bmod n,ax_2 \bmod n,\cdots,ax_{\phi{n}} \bmod n\}\\\because \gcd (a,n) = 1,\gcd (x_i,n) = 1\\\therefore \gcd (ax_i,n) = 1\\由欧几里得算法可知\ \gcd (ax_i \bmod n,n) = 1\\\\假设\ B\ 集合中的存在相同元素，即\ ax_1 = k_1n + b,ax_2 = k_2n + b\ (0 < x_1,x_2 < n\ 且\ \gcd(a,n) = 1)\\则有\ a(x_1 - x_2) = (k_1 - k_2)b\\\because \gcd (a,n) = 1\\\therefore x_1 - x_2 = n,k_1 - k_2 = a\\\because 0 < x_1,x_2 < n\\\therefore x_1 - x_2 = n\ 不成立，与假设矛盾，故\ B\ 集合中元素互不相同\\\\\therefore A = B\\\therefore a^{\phi(n)}\times \prod_{i = 1}^{\phi(n)} x_i \equiv \prod_{i = 1}^{\phi(n)} a \times x_i \equiv \prod_{i = 1}^{\phi(n)} x_i \pmod n\\\\\therefore a^{\phi(n)} \equiv 1 \pmod n$

乘法逆元

1. 费马小定理

欧拉定理的特殊情况，当 $n$ 为质数时：

$\because \phi(n) = n - 1\\ \therefore a^{\phi(n)} = a^{n - 1} \equiv 1 \mod n$

2. 计算

$a \div b \% c$ 时，假设存在 $p \times b ≡ 1 \pmod c$，则 $p$ 为 $b$ 的逆元。$a \div b \% c = a \times p \% c$。

$a \div b = k \times c + r\\ a = k \times b \times c + b \times r\\ \because p \times b \equiv 1 \pmod c\\ \therefore a \times p \equiv k \times c + r \pmod c\\ \therefore p \times b + k \times c = 1$

相当于 $b,c$ 已知，则可以通过扩展欧几里得算法求逆元，但需要 $\gcd (b,c) = 1$ 时才有解。时间复杂度 $O(n \log n)$。

int inv (int b,int c)
{
    int x,y;
    exgcd (b,c,x,y);
    return (x % c + c) % c;//化成正数
}

当 $c$ 为质数时，逆元可以表示为 $b^{c - 2} \% c$，直接可以使用快速幂求解。

$\because c \ 为质数\\ \therefore \gcd (b,c) = 1\\ \therefore b^{\phi(c)} \bmod c = 1\\ \therefore b \times b^{\phi(c) - 1} = 1\\ 则逆元\ p= b^{\phi(c) - 1} = b^{c - 1 - 1} = b^{c - 2}$

3. 线性求逆元

时间复杂度为 $O(n)$。

$令\ p\ 是质数，则有:\ inv_i = (p - \dfrac{p}{i}) \times inv_{p \% i} \bmod p。\\ \\ 令\ t = \dfrac{p}{i},k = p \% i，则：\\ t \times i + k \equiv 0 \pmod p\\ -t \times i \equiv k \pmod p\\ 同时除以\ i \times k\ 得：\\ -t \times inv_k \equiv intv_i \pmod p$

void init (int n,int mod)
{
    inv[1] = 1;
    for (int i = 2;i <= n;++i) inv[i] = (p - p / i) * inv[p % i] % p;
}

4. 无法求逆元的转化

$\dfrac{a}{b} \bmod m = \dfrac{a \bmod (b \times m)}{b}\\ \\ \dfrac{a}{b} = k \times m + x\ (x < m)\\ a = k \times b \times m + b \times x\\ a \bmod (b \times m) = b \times x\\ \frac{a \bmod (b \times m)}{b} = x$

中国剩余定理

求解以下方程：

$\forall m_{i \mid 1 \le i \le n},\gcd (m_i,m_{i + j}) = 1\ (1 \le j \le n - i)\\\begin{cases}x \equiv a_1 \pmod {m_1}\\x \equiv a_2 \pmod {m_2}\\\cdots\\x \equiv a_n \pmod {m_n}\\\end{cases}$

构造答案，设

$\begin{aligned}M &= \prod_{i = 1}^n m_i, \quad M_i = \frac{M}{m_i} \\s_i &: \; M_i \times s_i \equiv 1 \pmod {m_i} \\\because &\; M_i = \frac{M}{m_i} \\\therefore &\; M_i \times s_i \bmod m_j = 0 \quad (1 \le j \le n,\ j \ne i) \\x &= \sum_{i = 1}^n a_i \times M_i \times s_i \\\text{通解为} &\; x + k \times M\end{aligned}$

所以直接通过 $n$ 次 $\texttt{exgcd}$ 求出 $s_i$，最后合并即可。

ll CRT (int n,int a[],int m[])
{
    ll M = 1,ans = 0;
    for (int i = 1;i <= n;++i) M *= m[i];
    for (int i = 1;i <= n;++i)
    {
        ll x = 0,y = 0;
        exgcd (M / m[i],m[i],x,y);
        x = (x % m[i] + m[i]) % m[i];
        ans += M / m[i] * x * a[i];
        ans %= M;
    }
    return ans;
}

整除分块

求下列式子的值。

$\sum _{i = 1} ^ n \lfloor\dfrac{n}{i}\rfloor \ (1 \le n \le 10^9)$

若用朴素的算法，时间复杂度为 $O(n)$，显然会 $\texttt{TLE}$。那么再给出一种 $O(\sqrt n)$ 的做法。
先给出所有的 $\lfloor\dfrac{n}{i}\rfloor$ 的取值不会超过 $\sqrt{n}$ 种的证明：

$当 \ i \le \sqrt{n} 时，显然取值不超过 \sqrt{n};\\ 当 i > \sqrt{n} 时，\lfloor\dfrac{n}{i}\rfloor < \sqrt{n}，故取值不超过 \sqrt{n}。\\ 综上，命题成立。$

设一段取值均为 $\lfloor\dfrac{n}{i}\rfloor$ 的区间的左、右端点分别为 $L,R$。

$\because \lfloor\dfrac{n}{R}\rfloor \le \frac{n}{R}\\\therefore R \le \dfrac{n}{\lfloor\dfrac{n}{L}\rfloor}\\\therefore R_{\max} = \biggl\lfloor{\dfrac{n}{\lfloor{\dfrac{n}{L}\rfloor}}\biggr\rfloor}$

代码如下：

for (int L = 1,R;L <= n;L = R + 1)
{
    R = n / (n / L);
    ans += 1ll * (R - L * 1) * (n / L);
}

组合数学基础

1. 组合数的两种表示方法

对于递推公式，是对于第 $n$ 项是否选择得出的。

$\tbinom{n}{m} = C^m_n = \dfrac{n \times (n - 1) \times (n - 2) \cdots \times (n - m + 1)} {m!} = \dfrac{n!}{m!(n - m)!}\\\tbinom{n}{m} = \tbinom{n - 1}{m - 1} + \tbinom{n - 1}{m}$

2. 组合数的预处理

void init ()
{
    c[0][0] = 1;
    for (int i = 1;i < n;++i)
    {
        c[i][i] = c[i][0] = 1;
        for (int j = 1;j < i;++j)
        {
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
            c[i][j] %= MOD;
        }
    }
}

3. 组合数的变形

$(1)\ k \times \tbinom{n}{k} = k \times \dfrac{n!}{k!(n - k)!}\\= k \times n \times \dfrac{(n - 1)!}{k!(n - k)!} = n \times \dfrac{(n - 1)!}{(k - 1)!(n - 1 - (k - 1))!} = n \times \tbinom{n - 1}{k - 1}\\ (2)\ \sum_{i = 1}^{n}i \times \tbinom{n}{i} = \sum_{i = 1}^{n} n \times \tbinom{n - 1}{i - 1} = n \times 2^{n - 1}\\(3)\ \sum_{i = 1}^{n} i^2 \times \tbinom{n}{i} = n \times (n + 1) \times 2^{n - 2}\\(4)\ \sum_{i = 0}^{n} \tbinom{n}{i}^2 = \tbinom{2n}{n}$

其中的$(3)$可以转化为模型。等号左边为班级中的 $n$ 个人选择候选人，然后从候选人中选一个班长与副班长，同一个人可以身兼两职，求最终方案数；等号右边为身兼两职与两个人分别当选的两种情况，有加法原理相加得到，即：

$n \times 2^{n - 1} + n \times (n - 1) \times 2^{n - 2} = n \times (n + 1) \times 2^{n - 2}$

$(4)$ 也一样可以转化为模型。等号右边为班级中有 $n$ 个男生和 $n$ 个女生，从中选 $n$ 人；等号左边相当于等价的，男生选 $i$ 个，女生选 $n - i$ 个，则有
：

$\sum_{i = 0}^{n} \tbinom{n}{i} \times \tbinom{n}{n - i} = \sum_{i = 0}^{n} \tbinom{n}{i}^2$

【摘自 CF2077C Binary Subsequence Value Sum题解】

证明 $\sum_{i=0}^nC_n^ii=n2^{n-1}$
$i=C_i^1$，则原式等于 $\sum_{i=0}^nC_n^iC_i^1$，考虑其组合意义，即先从 $n$ 个元素中选若干个，再从若干个元素里选出一个的方案数。那我们先选这一个，有 $n$ 种方案，再从剩下 $n-1$ 个元素中选出若干个，有 $2^{n-1}$ 种方案，所以是 $n2^{n-1}$。

证明 $\sum_{i=0}^nC_n^ii^2=n(n+1)2^{n-2}$
考虑 $i^2=i+i(i-1)=i+2\times\frac{i(i-1)}{2}=C_i^1+2C_i^2$，则原式等于 $\sum_{i=0}^nC_n^iC_i^1+2C_n^iC_i^2$，等于 $n2^{n-1}+2\sum_{i=0}^nC_n^iC_i^2$，则我们只需解决 $\sum_{i=0}^nC_n^iC_i^2$。
考虑组合意义，即从 $n$ 个元素里选出若干个，再从若干个元素里选出两个的方案数。那我们先选出这两个，有 $\frac{n(n-1)}{2}$ 种方案，然后再从剩下的元素中选出若干个，有 $2^{n-2}$ 种方案，所以有 $n(n-1)2^{n-3}$ 种方案。

二项式定理

1. 概念

对于每一个 $x + y$ 的选择，则选 $i$ 个 $x$，剩余均选择 $y$ 时，答案为：

$C^i_n x^i y^{n - i} \ (1 \le n \le i)$

因此有：

$(x + y)^n = C_n^0 x^n y^0 + C^1_n x^{y - 1} y + C^2_n x^{n - 2} y^2 + \cdots + C^n_n x^0 y^n\\= \sum_{k = 0}^n \tbinom{n}{k} x^{n - k}y^k$

2. 二项式定理的变形

$(1)\ (x + y)^n = \sum_{k = 0}^n \tbinom{n}{n - k} x^{n - k}y^k\\ (2)\ (x + y)^n = \sum_{k = 0}^n \tbinom{n}{n - k} x^k y^{n - k}\\ (3)\ (x + y)^n = \sum_{k = 0}^n \tbinom{n}{k} x^k y^{n - k}\\ (4)\ 当\ y = 1\ 时，(1 + x)^n = \sum_{k = 0}^n \tbinom{n}{k} x^k = \sum_{k = 0}^n \tbinom{n}{n - k} x^k\\ (5)\ 当\ x = 2,y = 1\ 时，(x + y)^n = \sum_{i = 0}^{n} \tbinom{n}{i}2^i = 3^n\\ (6)\ 当\ x = y = 1\ 时，(x - y)^n = \sum_{i = 0}^{n} \tbinom{n}{i}2^i \times (-1)^i= 0\\ (7)\ 当\ x = y = 1\ 时，(x + y)^n = \sum_{i = 0}^{n} \tbinom{n}{i} = 2^n\\ (8)\ \tbinom{n}{0} + \tbinom{n}{2} + \cdots = \tbinom{n}{1} + \tbinom{n}{3} + \cdots = 2^{n - 1}$

隔板法

1. 题意

把 $n$ 个相同的小球，放到 $m$ 个不同的盒子中，盒子不能为空，求方案数。或者求 $x_1 + x_2 + \cdots + x_m = n$ 的正整数解。

解法相当于在 $n - 1$ 个间隔中选择 $m - 1$ 个间隔，将其分为 $m$ 份。故为：

$\tbinom{n - 1}{m - 1}$

2. 变式

把 $n$ 个相同的小球，放到 $m$ 个不同的盒子中，盒子可以为空，求方案数。或者求 $x_1 + x_2 + \cdots + x_m = n$ 的非负整数解。

解法相当于在先在每个盒子中放入 $1$ 个球，然后求 $n + m$ 个相同的小球放入 $m$ 个不同的盒子的方案数，盒子不能为空。故为：

$\tbinom{n + m - 1}{m - 1}$

错位排列

$\forall i \mid 1 \le i \le n,f_i != i$

递推公式为：

$f_1 = 0\\f_2 = 1\\f_i = (i - 1) \times (f_{i - 1} + f_{i - 2})\ (i > 2)$

对于第 $i$ 项，可以在前 $i - 1$ 个数中选一个数与第 $i$ 个数替换，共 $i - 1$ 中，然后问题变为求 $(i - 1) \times (f_{i - 2})$。也可以将前 $i - 1$ 个数中的一个数放在前 i - 1 个位置中符合条件的某一个位置，相当于求 $(i - 1) \times f_{i - 1}$ 这一新的错排。

圆排列

原来每组排列都有 $n$ 种排列等价，故方案数为：

$\frac{n!}{n}$

多重集合的排列

集合中有 $k$ 种不同类型的对象，每种数量均为无限，从中选 $n$ 个，排列的方案数为：

$k^n$

集合中有 $k$ 种不同类型的对象，每种数量分别为 $n_1$ 至 $n_k$，从中选 $n$ 个。相当于选出 $n_1$ 个位置放第 $1$ 种，选出 $n_2$ 个位置放第 $2$ 种，以此类推。方案数为：

$\tbinom{n}{n_1} \times \tbinom{n - n_1}{n_2} \times \cdots \times \tbinom{n - n_1 - n_2 - \cdots - n_{k - 1}}{n_k}= \dfrac{n!}{n_1!n_2!\cdots n_k!}$

多重集合的组合

集合中有 $k$ 种不同类型的对象，每种数量均为无限，从中选 $n$ 个。等价于 $k$ 个相同的球放到 $n$ 个不同的盒子中，盒子可以为空。或者等价于选 $k$ 次球，每次都可以选 $n$ 种球，且选择不分先后。组合的方案数为：

$\tbinom{n + k - 1}{k} = \tbinom{n + k - 1}{n - 1}$

康托展开

1. 计算排列的排名

设 $a_i$ 表示 $i$ 位置右边比它小的数的个数，则该排列之前的排列总数为：

$x = a_1 (n - 1)! + a_2 (n - 2)! + \cdots + a_n0!$

倘若 $i$ 位置上的数比该数小，则在它右边的数可以随意放置，若 $i$ 位置上的数等于该数，则继续判断 $i + 1$ 位置的数的情况，以此类推。因此可以由加法原理得可知该排列之前的排列总数。所以求排名的公式为：

$ans = 1 + \sum_{i = 1}^n a_i \times (n - i)!$

2. 计算特定排名的排列

即康托展开的逆展开。

利用康托展开的公式，类似进制转换的方式去确定从高到底的每一位。若排列长度为 $x$，求编号为 $0$ 开始的，编号为 $k$ 的排列。方法如下：$p = \frac{k}{(x - 1)!}$，则说明第一位右边有 $p$ 个数比它小，所以最高位为 $p + 1$，然后取余数重复操作，知道确定排列上的所有数字。

3. 求下一个排列

对于一个排列：$a_1,a_2,\cdots,a_n$。从后往前找到第一个 $p_i < p_{i + 1}$ 的位置，从后往前找到第一个 $p_j < p_i$ 的位置。最后交换 $p_i,p_j$ 并颠倒 $i$ 位置以后的所有元素即可。

斯特林数

1. 第一类斯特林数

求将 $n$ 个不同的物体摆成k个非空环的方案数。采用动态规划的做法，对于第 $i$ 个物体，可以任取一个环加入，也可以构造一个新环，故有 $dp_{n,k} = (n - 1)dp_{n - 1,k} + dp_{n - 1,k - 1}$。（当然有初始化 $dp_{0,0} = dp_{1,1} = 1$）

2.第二类斯特林数

求将 $n$ 个不同的物体分成 $k$ 个非空集合的方案数。采用动态规划的做法，对于第 $i$ 个物体，可以任取一个集合加入，也可以放入一个新集合中，故有 $k \times dp_{n - 1,k} + dp_{n - 1,k - 1}$。（当然有初始化 $dp_{i,i} = dp_{i,1} = 1$）

卡特兰数

题目描述，假如有一个 $n\times n$ 的网络，从左下角 $A$ 点走到右上角 $B$ 点且不穿越对角线的方案数。通过几何方法证明，答案为：

$\text{Catalan}(n)= \tbinom{2n}{n} - \tbinom{2n}{n + 1}= \frac{1}{n + 1}\tbinom{2n}{n}= \frac{1}{n + 1}\sum_{i = 0}^{n}\tbinom{n}{i}^2$

其它的表达形式还有：

$C(n + 1) = \sum_{i = 0}^n C(i)\times C(n - i),C(0) = 1\\C(n + 1) = \frac{2(2n + 1)}{n + 2} C(n),C(0) = 1$

常见应用：

合法的括号匹配
$n$ 个节点二叉树的形态数
入栈出栈的排列总数
凸 $n+2$ 边形的分割

放球问题

设 $dp_{i,j}$ 表示 $i$ 个小球放到 $j$ 个盒子的方案数。

1. 球相同，盒相同，可为空。

则有：$dp_{i,j} = dp_{i,j - 1} + dp_{i - 1,j}$。

2. 球相同，盒相同，不可为空。

则有：$dp_{i,j} = dp_{i - j,j}$。

3. 球不同，盒不同，可为空。

则有：$j^i$。

4. 球不同，盒相同，不可为空。

则有：$dp_{i,j} = dp_{i - 1,j} + dp_{i - 1,j - 1}$。

5. 球不同，盒不同，不可为空。

则有：$dp_{i,j} \times {j!}$。

6. 球不同，盒相同，可为空。

枚举盒子数，则有：$dp_{i,j} = dp_{i - 1,j} + dp_{i - 1,j - 1}$。

7. 球相同，盒不同，不可为空。

隔板法，则有：$\tbinom{i - 1}{j - 1}$。

8. 球相同，盒不同，可为空。

则有：$\tbinom{i + j - 1}{j - 1}$。

卢卡斯定理

$n = (a_0a_1\cdots a_k)_p\\m = (b_0b_1\cdots b_k)_p\\\tbinom{n}{m} \equiv \Pi_{i = 0}^{k} \tbinom{a_i}{b_i} \pmod p\\\tbinom{n}{m} = \tbinom{n \bmod p}{m \bmod p} \times \tbinom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor} \bmod p$

证明略。代码如下：

int calc (int n,int m)
{
    if (n < m) return 0;
    return 1ll * fac[n] * inv(fac[m]) % MOD * inc (fac[n - m]) % MOD;
}
int lucas (int m,int m)
{
    if (!m) return 1;
    return 1ll * lucas (n / MOD,m / MOD) * clac (n % MOD,m % MOD) % MOD;
}

初级数学 学习笔记