初级数学 学习笔记

· · 算法·理论

数论基本概念

1. 整除法

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

2. 算数基本定理

$$ 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)$$ 代码如下： ```cpp 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. 常数优化 枚举小的那个因子。 ```cpp 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)$。 ```cpp 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)$。 ```cpp 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$。 ```cpp 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 \Z \\\end{cases}$$ ## 欧拉函数 ### 1. 定义 $\phi(n)$ 表示小于等于 $n$ 的正整数与 $n$ 互质的个数。 并且规定 $\phi(1) = 1$。 ### 2. 积性函数 设 $p$ 为质数，求 $\phi(p^k)$，也就是总数减去所有 $p$ 的倍数。 $$ \phi(p^k) = p^k - (p^k \div p) = p^k - p^{k - 1} = (p - 1) \times p^{k - 1} $$ 同理，求 $\phi(p_1 ^ {k_1} \times p_2 ^ {k_2})$，也就是总数减去 $p_1,p_2$ 的倍数，然后再加上 $p_1 \times p_2$ 的倍数。 $$ \therefore \phi ({p_1} ^ {k_1} {p_2} ^ {k_2}) = {p_1} ^ {k_1} {p_2} ^ {k_2} - {p_1} ^ {{k_1} - 1} {p_2} ^ {k_2} \times {p_1} ^ {k_1} {p_2} ^ {{k_2} - 1} + {p_1} ^ {{k_1} - 1}{p_2} ^ {{k_2} - 1}\\ \therefore \phi ({p_1} ^ {k_1} {p_2} ^ {k_2}) = \phi({p_1} ^ {k_1}) \times \phi({p_2} ^ {k_2}) $$ ### 3. 计算通式 将 $n$ 进行质因数分解，则有： $$ n = p_1^{a_1} p_2^{a_2} \cdots p_m ^ {a_m}\\ \therefore \phi (n) = \prod_{i = 1}^{m} p_i^{k_i - 1} \times (p_i - 1) = \prod_{i = 1}^{m} p_i^{k_i - 1} \times p_i \times(p_i - 1) \div p_i = n \times \prod_{i = 1}^m \dfrac{p_i - 1}{p_i} $$ ### 4. 性质 1. 若 $m,n$ 互质，则 $\phi(mn) = \phi(m) \times \phi(n)$，此函数为积性函数。证明相当于是 $3$。 2. 若 $p$ 为质数，则 $\phi(p) = p - 1$。 3. 若 $n$ 为奇数，则 $\phi(2n) = \phi(n)$。 $$ \because n = 2k + 1(k \mid \Z)\\ \therefore n\ 与\ 2\ 互质\\ 又 \because 当\ m,n\ 互质时，\phi (mn) = \phi (m) \times \phi (n)\\ \therefore \phi (2n) = \phi (2) \times \phi (n)\\ \because \phi(2) = 1\\ \therefore \phi (2n) = \phi (n) \times 1 = \phi (n) $$ 4. 若 $p$ 能整除 $\dfrac{n}{p}$，则 $\phi(n) = \phi (\dfrac{n}{p}) \times p$。相当于在 $\phi (\dfrac{n}{p})$ 中的某个 $p_i^{k - 1}$ 中乘上一个$ p_i$，也就是 $\phi(n) = \phi(\dfrac{n}{p}) \times p$。 5. 若 $p$ 与 $\dfrac{n}{p}$ 互质，且 $p$ 为质数，则 $\phi(n) = \phi(\frac{n}{p}) \times(p - 1)$。 $$ \because p\ 与 \ \frac{n}{p}\ 互质，所以为积性函数\\ \therefore \phi(n) = \phi(\dfrac{n}{p}) \times \phi(p)\\ \because p\ 为质数\\ \therefore \phi(p) = p - 1\\ \therefore \phi(n) = \phi(\dfrac{n}{p}) \times (p - 1) $$ 6. 求证：$\sum_{d \mid n} \phi(d) = n$。 $$ 证明：设\ f(n) = \sum_{d \mid n} \phi(d)。\\ 若\ m,n\ 互质，则\ m,n\ 之间无公共因子，由乘法原理可知：\\ f(mn) = \sum_{d \mid mn} \phi(d) = (\sum_{d \mid n} \phi(d)) \times (\sum_{d \mid m} \phi(d)) = f(n) \times f(m)\\ \therefore f(n)\ 为积性函数\\ \therefore f(n) = \prod_{i = 1}^{k} f(p_i^{c_i})，其中\ p_i,c_i,k\ 都是相当于对\ n\ 进行质因数分解得到的参数\\ \because 对于一个质因数分解的结果\ p_i^{c_i}\\ \therefore f(p_i^{c_i}) = \sum_{d \mid p_i^{c_i}} \phi(d) = \phi(1) + \phi(p_i) + \phi(p_i^2) + \cdots + \phi(p_i^{c_i})\\ \because 对于一个质数\ p\ 的\ k\ 次幂\ n，有\ \phi(n) = (p - 1) \times p^{k - 1}\\ \therefore f(p_i^{c_i}) = 1 + (p_i - 1) \times (p_i^0 + p_i^1 + \cdots + p_i^{c_i - 1})\\ = 1 + (p_i - 1) \times \dfrac{1 \times (1 - p_i^{c_i})}{1 - p_i} = 1 + (p_i^{c_i} - 1) = p_i^{c_i}\\ \therefore f(n) = \prod_{i = 1}^{k} f(p_i^{c_i}) = n $$ 7. 求证小于 $n$ 且与 $n$ 互质的数的和为 $\dfrac{n \times \phi(n)}{2}$。 $$ 假设与\ n\ 互质的数构成集合\ A = \{a_1,a_2,\cdots,a_m\}，显然由定义知\ \phi(n) = m\\ 先证明\ B = \{n - a_1,n - a_2,\cdots,n - a_m\} \ 之中的元素也与\ n \ 互质\\ 即若\ x < n，\gcd (x,n) = 1，求证\ \gcd (n - x,n) = 1\\ 假设\ \gcd (n - x,n) ≠ 1。设\ n - x = k_1g，n = k_2g\ (g > 1)\\ 那么有\ k_2g - x = k_1g,x = (k_2 - k_1)g，则易知\ \gcd (n,x) = g，与条件矛盾\\ 故有\ \gcd (n - x,n) = 1\\ 发现\ A = B\\ \therefore 为\ \frac{1}{2}[(a_1 + a_2 + \cdots + a_m + (n - a_1) + (n - a_2) + \cdots + (n - a_m)] \times m\\ 即为\ \frac{n \times \phi(n)}{2} $$ ### 5. 代码 1. 根据欧拉函数通式求解。 ```cpp 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 } } ``` 2. 根据线性筛实现 $O(n)$ 的时间复杂度求解。 ```cpp 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) } } } ``` 3. 利用性质 $f$ 的求解。 ```cpp 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 \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)$。 ```cpp 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 $$ ```cpp 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$，最后合并即可。 ```cpp 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}$$ 代码如下： ```cpp 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. 组合数的预处理 ```cpp 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题解](https://www.luogu.com.cn/article/8g58f61g)】 > - 证明 $\sum_{i=0}^nC_n^ii=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}

多重集合的排列

  1. 集合中有 k 种不同类型的对象，每种数量均为无限，从中选 n 个，排列的方案数为：
k^n
  1. 集合中有 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

常见应用：

  1. 合法的括号匹配
  3. 入栈出栈的排列总数
  4. 凸 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;
}