2022-08-02发表

计数原理

排列数公式：

$$
P^k_n=\frac{n!}{(n-k)!}
$$

组合数公式：

$$
P^k_n=\frac{n!}{k!(n-k)!}
$$

这里规定 $\color{Red}0!=1$

一些比较重要的公式

1.
$$
\dbinom{n}{k}=\dbinom{n}{n-k}
$$
2.
$$
\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}
$$
3.
$$
\dbinom{n}{k}\dbinom{k}{t}=\dbinom{n}{t}\dbinom{n-t}{k-t}
$$
4.
$$
\dbinom{n}{k}={\sum_{i=k+1}^n k^2}\dbinom{i-1}{k}
$$
5.
$$
\dbinom{n+m}{k}=\sum_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}
$$
6.
$$
\dbinom{n}{a+1+b}=\sum_{i=a+1}^{n-b}\dbinom{i-1}{a}\dbinom{n-i}{b}
$$
7.
$$
(a+b)^n=\sum_{i=0}^n \dbinom{n}{i} a^i b^{n-i}
$$

组合数取模

$m \leq n\leq 1000,p \leq 10^9$
- 利用杨辉三角求解
  $$
  \dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}
  $$
$m \leq n\leq 10^5,p$是质数
- 先求出阶乘，再求出阶乘的逆元
  $$
  \dbinom{n}{m}=\dbinom{n}{n-m}
  $$
- 先$O(n)$求出$n!$,然后计算$n!$d的逆元，继而利用$n!$的逆元求出$(n-1)!$等的逆元
- 复杂度$O(n)-O(1)$。
$m \leq n\leq 10^{18},p \leq 10^5,p$是质数
- 利用Lucas定理
  $$
  \dbinom{n}{m}\equiv\dbinom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor}\dbinom{n \mod p}{m \mod p}(\mod p)
  $$
- 转到方法2
- 复杂度$O(p)-O(\log_pn)$
$m \leq n\leq 10^{5},p \leq 10^5$
- 利用线性筛分解n!,计算每种质因子出现的次数,快速幕计算。
- 质数数量为$O(\frac{n}{\ln n})$,复杂度为$O(n)$
$m \leq n\leq 10^{18},p^c \leq 10^5,p$是质数
$$
\dbinom{n}{m}(\mod p^c)
$$
- 由于涉及除法,所以考虑把存成不包含$p$因子的部分和$p$因子出现的次数处理。
- 考虑每次把不包含$p$因子的部分利用已预处理的阶乘计算,包含$p$因子的部分可以写成公差为$p$的等差数列,所以可以递归子问题,范围缩小为原来的$\frac{1}{p}$,
  复杂度为$O(p^c)$
$m \leq n < p \leq 10^9$
- 关键是计算$n!$,假设$n$是完全平方数,否则暴力计算完全平方数以外的部分。
- 构造多项式
  $$
  Q(x)=\prod_{i=0}^{\sqrt{n}}(x+i)
  $$
- 那么可得
  $$
  n!=\prod_{i=0}^{\sqrt{n}-1}Q(i\sqrt{n})
  $$
- $Q(x)$为$\sqrt{n}$阶多项式，现需要在$\sqrt{n}$个点求值
- 现在的问题是多项式多点求值。
- 为了描述方便,设给出多项式$F(x)$,求其在$A = (a_o, a_1,\ldots, a_m)$处的值。
- 构造多项式
  $$
  M_0(x)=\prod_{i=0}^{\lfloor \frac{m}{2} \rfloor}(x-a_i)
  $$
  $$
  M_1(x)=\prod_{i=\lfloor \frac{m}{2} \rfloor+1}^{m}(x-a_i)
  $$
- 那么，设
  $$
  Q_0(x)=F(x) \mod M_0(x)
  $$
  $$
  Q_1(x)=F(x) \mod M_1(x)
  $$
- 由于模去了$(x-a_i)$,所以$F(a_i)$的取值是不变的
- 于是可以得到一个性质
  $$
  \forall i \in [0,\lfloor \frac{m}{2} \rfloor],F(a_i)=Q_0(a_i)
  $$
  $$
  \forall i \in [\lfloor \frac{m}{2} \rfloor+1,m],F(a_i)=Q_1(a_i)
  $$
- 分治递归解决
- 于是求解$n!$的复杂度为$O(\sqrt{n}log^2n)$,问题解决。

#数学