排列组合初步
1. 公式部分
- 排列数
从\(n\)个不同元素中任取\(m\)（\(m\leq n\),
，\(m\)和\(n\)均为自然数）个元素组成一个排列。
排列数公式如下：
\(A_{n}^{m}= \frac{n!}{(n-m)!}\)
理解：第一个位子有\(n\)个选择，第二个位子有\(n-1\)个选择，以此类推，第\(m\)个有\(n-m+1\)个选择，于是得到：
\(A_{n}^{m}=n(n-1)(n-2) \cdots (n-m+1)= \frac{n!}{(n-m)!}\)
显然，\(A_{n}^{n}=n!\)。
- 组合数
从n个不同的元素中，任选\(m\leq n\)个元素组成一个集和，叫做从 $n \(个不同元素中取出\) m $个元素的一个组合；
从 $n \(个不同元素中取出\)m \leq n$ 个元素的所有组合的个数，叫做从$ n$ 个不同元素中取出$ m $个元素的组合数，用符号 $\dbinom{n}{m} \(来表示,及\)C_{n}^{m}$。
组合数公式如下：
\(\dbinom{n}{m} = C_{n}^{m} = \frac{A_{n}^{m}}{m!} = \frac{n!}{m!(n-m)!}\)
理解：从\(n\)个数选出\(m\)个来，不在乎顺序，据需要 $ A_{n}^{m} $ 去掉重复的。选出\(m\)个人，全排得到\(m!\)，所以：\(\dbinom{n}{m} \times m! = A_{n}^{m}\)。
规定：\(m>n\)时，\(A_{n}^{m} = \dbinom{n}{m} = 0\)。
2. 隔板法(插板法)
- \(question 1\)：
现有$ n \(个 完全相同 的元素，要求将其分为\) k $组，保证每组至少有一个元素，一共有多少种分法？
考虑拿 $k - 1 $块板子插入到 $n \(个元素两两形成的\) n - 1 \(个空里面。 因为元素是完全相同的，所以答案就是 \)\dbinom{n - 1}{k - 1}$。
本质是求 $x_1+x_2+\cdots+x_k=n $的正整数解的组数。
- \(question 2\)：
显然此时没法直接插板了，因为有可能出现很多块板子插到一个空里面的情况，非常不好计算。
我们考虑创造条件转化成有限制的问题一，先借$ k \(个元素过来，在这\) n + k \(个元素形成的\) n + k - 1 $个空里面插板，答案为
\(\binom{n + k - 1}{k - 1} = \binom{n + k - 1}{n}\)
虽然不是直接求的原问题，但这个式子就是原问题的答案，可以这么理解：
开头我们借来了$ k $个元素，用于保证每组至少有一个元素，插完板之后再把这 k 个借来的元素从 k 组里面拿走。因为元素是相同的，所以转化过的情况和转化前的情况可以一一对应，答案也就是相等的。
由此可以推导出插板法的公式：
\(\dbinom{n + k - 1}{n}\)。
本质是求$ x_1+x_2+\cdots+x_k=n $的非负整数解的组数（即要求 $ x_i \ge 0 $ ）。
3. 线性乘法逆元求组合数
逆元
线性求\(1 \sim n\)的逆元
首先，可以显然得到 $ inv_{1} = 1\(（\)inv$表示逆元）。
对于任意模数\(p\)，有 $ p=k \times i + r $（\(0 \leq r<i\)）
此时易得：
\(k\times i+r \equiv 0(mod \ \ p )\)
两边同乘上\(i^{-1} \cdot r^{-1}\)，并进行移项：
$ \Rightarrow$ \(i^{-1} \equiv -k \times r^{-1} (mod \ \ p)\)
显然\(r^{-1}\)会先得到。所以：
\(inv_{i}=-\lfloor \frac{p}{i} \rfloor \times inv_{p \ \ mod \ \ i}\)。
于是得到：
inv[1]=1;
for(int i=2;i<=6e6;i++)
inv[i]=(p-p/i)*inv[p%i]%p;
组合数
质数模数求法
$ \dbinom{n}{m}=\frac{n!}{m!(n-m)!}$。
这么好看的式子，显然在模意义可以拆成上下两个 ，上面的直接求取，下面的求逆元就搞定了。
\(O(n)\)预处理逆元和阶乘后，\(O(1)\)计算答案。
code：
线性求阶乘。
fac[0]=1;
for(int i=1;i<=6e6;i++)
fac[i]=fac[i-1]*i%p;
线性求逆元。
inv[1]=1;
for(int i=2;i<=6e6;i++)
inv[i]=(p-p/i)*inv[p%i]%p;
线性求阶乘逆元。
ifac[0]=1;
for(int i=1;i<=6e6;i++)
ifac[i]=ifac[i-1]*inv[i]%p;
组合数计数。
int C(int a,int b)
{
if(a==b)return 1;
if(a<b||b<0) return 0;
return fac[a]*ifac[a-b]%p*ifac[m]%p;
}