排列组合
基本公式：
A_n^m=\frac{n!}{(n-m)!}\\
C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}\\
为了表示整洁，以下都使用 \left( \begin{array}\\ n\\ m \end{array} \right) 来表示 C_n^m
基本性质与证明
\left(\begin{array}\\n\\m\end{array}
\right)
=\frac{n!}{m!(n-m)!}
=\frac{n!}{\left[n-(n-m)\right]!(n-m)!}
=\left(\begin{array}\\n\\n-m\end{array}\right)
\\
\\
\\
\\
\begin{align}
\left(\begin{array}\\n-1\\m\end{array}\right)+\left(\begin{array}\\n-1\\m-1\end{array}\right)
&=\frac{(n-1)!}{m!(n-1-m)!}+\frac{(n-1)!}{(m-1)!\left[n-1-(m+1)\right]}\\
&=\frac{(n-m)(n-1)!}{m!(n-m)!}+\frac{m(n-1)!}{m!(n-m)!}\\
&=\frac{(n-1)!}{m!(n-m)!}\times(n-m+n)\\
&=\frac{n!}{m!(n-m)!}
=\left(\begin{array}\\n\\m\end{array}\right)
\end{align}
不难发现 (x+y)^n 展开后的第 i 项的系数为 \left(\begin{array}\\n\\i\end{array}\right) ，次数为 n-i 和 i
于是我们可以得出二项式定理：
(x+y)^n
=\displaystyle\sum_{i=0}^{n}\left(\begin{array}\\n\\i\end{array}\right)x^{n-k}y^{k}
=\displaystyle\sum_{i=0}^{n}\left(\begin{array}\\n\\i\end{array}\right)x^{k}y^{n-k}
由于该式的存在，组合数也被称为二次项系数
证明如下：
\begin{align}
(x+y)^n &=x(x+y)^{n-1}+y(x+y)^{n-1}\\
&=x\times\displaystyle\sum_{i=0}^{n-1}
\left(\begin{array}\\n-1\\i\end{array}\right)x^{n-1-i}y^i
+y\times\displaystyle\sum_{j=0}^{n-1}
\left(\begin{array}\\n-1\\j\end{array}\right)x^{n-1-j}y^j
\\
&=x\times
\left[\begin{array}\\x^{n-1}+\displaystyle\sum_{i=1}^{n-1}
\left(\begin{array}\\n-1\\i\end{array}\right)x^{n-1-i}y^i\end{array}\right]
+y\times\displaystyle\sum_{j=0}^{n-1}
\left(\begin{array}\\n-1\\j\end{array}\right)x^{n-1-j}y^j
\\
&=x^n+\displaystyle\sum_{i=1}^{n-1}
\left(\begin{array}\\n-1\\i\end{array}\right)x^{n-i}y^i+
\displaystyle\sum_{j=0}^{n-1}
\left(\begin{array}\\n-1\\j\end{array}\right)x^{n-1-j}y^{j+1}
\\
&\ 设\ j=i-1,代入得:
\\
原式 &=x^n+\displaystyle\sum_{i=1}^{n-1}
\left(\begin{array}\\n-1\\i\end{array}\right)x^{n-i}y^i+
\displaystyle\sum_{i=1}^{n}
\left(\begin{array}\\n-1\\i-1\end{array}\right)x^{n-1-(i-1)}y^{(i-1)+1}
\\
&=x^n+\displaystyle\sum_{i=1}^{n-1}
\left(\begin{array}\\n-1\\i\end{array}\right)x^{n-i}y^i+
\displaystyle\sum_{i=1}^{n}
\left(\begin{array}\\n-1\\i-1\end{array}\right)x^{n-i}y^{i}
\\
&=x^n+\displaystyle\sum_{i=1}^{n-1}
\left(\begin{array}\\n-1\\i\end{array}\right)x^{n-i}y^i
+y^n+\displaystyle\sum_{i=1}^{n-1}
\left(\begin{array}\\n-1\\i-1\end{array}\right)x^{n-i}y^{i}
\\
&=x^n+y^n+\displaystyle\sum_{i=1}^{n-1}
\left[\begin{array}\\
\left(\begin{array}\\n-1\\i \end{array}\right)+
\left(\begin{array}\\n-1\\i-1\end{array}\right)
\end{array}\right]x^{n-i}y^i
\\
&=x^n+y^n+\displaystyle\sum_{i=1}^{n-1}
\left(\begin{array}\\n\\i\end{array}\right)x^{n-i}y^i
\\
&=\displaystyle\sum_{i=0}^{n}\left(\begin{array}\\n\\i\end{array}\right)x^{k}y^{n-k}
\end{align}
所以，我们可以得出
\begin{align}
&=\displaystyle\sum_{i=0}^{n}\left(\begin{array}\\n\\i\end{array}\right)1^{k}1^{n-k}\\
&=(1+1)^n\\
&=2^n
\end{align}
我们同时可以得出卢卡斯定理：
\left(\begin{array}\\n\\m\end{array}\right)\mod{p}
=\left(\begin{array}\\\lfloor\frac{n}{p}\rfloor\\\lfloor\frac{m}{p}\rfloor\end{array}\right)
\times\left(\begin{array}\\{n}\mod{p}\\{m}\mod{p}\end{array}\right)
\mod{p}
证明如下：
\begin{align}
&通过二项式定理可得:\\
(1+&x)^p=\displaystyle\sum_{i=0}^{p}\left(\begin{array}\\p\\i\end{array}\right){1^i}\times{x^i}\\
当\ i&\not=0\ 且\ i\not=p\ 时:\\
\left(\begin{array}\\p\\i\end{array}\right)&\equiv\frac{p!}{i!(p-i)!}\equiv 0\ (mod{\ p})\\
所以\ &(1+x)^p\equiv\displaystyle\sum_{i=0}^{p}
\left(\begin{array}\\p\\i\end{array}\right){1^i}\times{x^i}
\equiv(1-x^p)\ (mod\ {p})
\\
\\
设\ a&=\lfloor\frac{n}{p}\rfloor,i={n}\ mod\ {p}\\
b&=\lfloor\frac{m}{p}\rfloor,j={m}\ mod\ {p}\\
则\ n&=ap+i,m=bp+j\\
由于&\left(\begin{array}\\ap+i\\bp+j\end{array}\right)
=\left(\begin{array}\\n\\m\end{array}\right),\\
表示&\ (1+x)^{i+ap}\ ——即\ (1+x)^n,\ 的\ x^{j+bp}\ ——即x^m项的系数\\
而(1&+x)^{i+ap}\equiv(1+x)^i(1+x)^{ap}\equiv(i+x)^i(1+x^p)^a\ (mod\ p)\\
所以&求(1+x)^{i+ap}\ 的\ x^{j+bp}项的系数\\
相当&于求\ (1+x)^{i}\ 中\ x^{j}\ 项的系数,再乘以\ (1+x)^{ap}\ 中\ x^{bp}\ 项的系数\\
而上&方两者用公式书写为:\left(\begin{array}\\a\\b\end{array}\right)\times
\left(\begin{array}\\i\\j\end{array}\right)\\
所以&得到
\left(\begin{array}\\n\\m\end{array}\right)=
\left(\begin{array}\\a\\b\end{array}\right)\times
\left(\begin{array}\\i\\j\end{array}\right)\\
即:\
&\left(\begin{array}\\n\\m\end{array}\right)=
\left(\begin{array}\\\lfloor\frac{n}{p}\rfloor\\\lfloor\frac{m}{p}\rfloor\end{array}\right)\times
\left(\begin{array}\\n\ mod\ p\\m\ mod\ p\end{array}\right)\\
证毕
\end{align}
还有一个不太常用的公式：
\displaystyle\sum_{i=0}^{n}{(-1)^i\times\left(\begin{array}\\n\\i\end{array}\right)}=0
证明如下：
通过二项式定理可得:\\
(-1+1)^n
=\displaystyle\sum_{i=0}^{n}\left(\begin{array}\\n\\i\end{array}\right)(-1)^{i}1^{n-i}
=\displaystyle\sum_{i=0}^{n}{(-1)^i\times\left(\begin{array}\\n\\i\end{array}\right)}
同时这个式子也告诉我们：
\displaystyle\sum_{i}^{n}{[i\ mod\ 2=0]}\times\left(\begin{array}\\n\\i\end{array}\right)
=\displaystyle\sum_{i}^{n}{[i\ mod\ 2=1]}\times\left(\begin{array}\\n\\i\end{array}\right)
-----------------------分----------------割-----------------线--------------------------
讲了那么多公式，我们再回头来看看具体怎么求 \left(\begin{array}\\n\\m\end{array}\right) 吧
法一：
直接套公式 \frac{n!}{m!(n-m)!} 。
算一下复杂度：预处理阶乘要 O(n) ；
处理逆元要快速幂，复杂度 O(\log_2n) ；
总合 O(n+\log_{2}n) 。
法二：
利用 \begin{align} \left(\begin{array}\\n-1\\m\end{array}\right)+\left(\begin{array}\\n-1\\m-1\end{array}\right)=\left(\begin{array}\\n\\m\end{array}\right)\end{align}
显然复杂度为 O(n^2) ，设询问组数为 q ；
总复杂度为 O(qn^2) 。
总复杂度较高，但它可以再次复杂度内求出一定范围内的所有组合数，即单次询问只有 $O(1)$。
但如果要求我们求出一定范围内的所有数，而且 p 很小 n,m 很大呢？
这时候我们就要使用卢卡斯定理：
\left(\begin{array}\\n\\m\end{array}\right)\mod{p}
=\left(\begin{array}\\\lfloor\frac{n}{p}\rfloor\\\lfloor\frac{m}{p}\rfloor\end{array}\right)
\times\left(\begin{array}\\{n}\mod{p}\\{m}\mod{p}\end{array}\right)
\mod{p}
如果 \lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor 还是很大怎么办呢？——递归即可解决。
所以我们只需要预处理出 p 以内的组合数，剩下的递推解决。
其中预处理复杂度 O(p) ，单次询问递推递推复杂度 O(\log_{p}{n}) ，
总和 O(p+q\log_{p}n) ，
这是相当可观的复杂度了。
还是那句话，LATEX炸了的刷新一下，拜托了qwq
不要老是在评论区发看不见LATEX
猜你想搜：
