0%

数学基础知识整理

整理一些数学基础知识。

算数基本定理

任意一个大于1的正整数都能被唯一分解成有限个质数的乘积,可写作:

其中 $c_i$ 都是正整数,$p_i$ 均为质数,且满足 $p_1<p_2<…<p_m$。

显然的推广:如果两个数没有相同的质因数,则这两个数互质。

裴蜀定理:对于方程 $ax+by=c \ \ \ x,y\in \mathbb{Z}^+$,当且仅当 $gcd(a,b)|c$ 时,有整数解。

gcd/lcm转换:$gcd(a,b)lcm(a,b)=ab$

费马小定理

若 $gcd(a,m)=1 $,则 $a^{m-1} \equiv 1(mod \ m)$

推广:若 $gcd(a,m)=1$,则 $a^m \equiv m(mod \ m)$

线性同余转换

欧几里得:$gcd(a,b)=gcd(b,a \ mod \ b) \ \ gcd(a,0)=a \ \ (b\not=0)$

欧拉定理:若 $gcd(a,m)=1$,则 $a^{\phi(m)}\equiv 1(mod \ m)$

拓展欧拉定理:$a^b\equiv a^{b \ mod \ \phi(m)+\phi(m)}(mod \ m)$

Stein算法

  • 均为偶数 $gcd( x,y ) =2gcd( x/2,y/2 )$
  • 均为奇数 $gcd( x,y ) = gcd( (x+y)/2,(x-y)/2 )$
  • $x$ 奇 $y$ 偶 $gcd( x,y ) = gcd( x,y/2 )$
  • $x$ 偶$ y$ 奇 $gcd( x,y ) = gcd( x/2,y )$ 或 $gcd( x,y )=gcd( y,x/2 )$

组合排列数

组合恒等式

恒等式编号按顺序从 $1$ 开始依次递增。

  • $\left( \begin{array}{c}n\\k\\\end{array}\right)=\left( \begin{array}{c}n\\{n-k}\\\end{array}\right)$ 组合意义:选出一部分再反选。

  • $\left( \begin{array}{c}n\\k\\\end{array}\right)=\left( \begin{array}{c}n-1\\k\\\end{array}\right)+\left( \begin{array}{c}n-1\\k-1\\\end{array}\right)$ 组合意义:枚举第一个选或不选。

  • $\left( \begin{array}{c}n\\k\\\end{array}\right)\left( \begin{array}{c}k\\t\\\end{array}\right)=\left( \begin{array}{c}n\\t\\\end{array}\right)\left( \begin{array}{c}n-t\\k-t\\\end{array}\right)$ 组合意义:把 $n$ 个数中选 $k$ 个再选 $t$ 个转化为 $n$ 中选 $t$ 个再选出 $k-t$ 个。

  • $\left( \begin{array}{c}n\\k\\\end{array}\right)=\sum_{i=k}^n\left( \begin{array}{c}i-1\\k-1\\\end{array}\right)$ 组合意义:考虑最后一个数选在哪里,如果选在 $i$ 则前 $i-1$ 个中要选出 $k-1$ 个。

  • $\left( \begin{array}{c}n+m\\k\\\end{array}\right)=\sum_{i=0}^k\left( \begin{array}{c}n\\i\\\end{array}\right)\left( \begin{array}{c}m\\k-i\\\end{array}\right)$ 组合意义:$n+m$ 里面选 $k$ 个,枚举前 $n$ 个里面选多少个。

    当 $n-m=k$ 时结合恒等式 $1$ 有 $\sum_{i-1}^n\left( \begin{array}{c}n\\i\\\end{array}\right)^2=\left( \begin{array}{c}2n\\n\\\end{array}\right)$。

  • $\left( \begin{array}{c}n\\a+b+1\\\end{array}\right)=\sum_{i=a+1}^{n-b}\left( \begin{array}{c}i-1\\a\\\end{array}\right)\left( \begin{array}{c}n-1\\b\\\end{array}\right)$ 组合意义:考虑那个 $1$ 选在 $i$,一边选 $a$ 个一边选 $b$ 个。

    若 $b=0$ 则该式退化为恒等式 $4$。

  • $(a+b)^n=\sum_{i=0}^n\left( \begin{array}{c}n\\i\\\end{array}\right)a^ib^{i-1}$ 组合意义:真他妈难证,背过算了。

    当 $a=b=1$ 时,有 $\sum_{i=0}^n\left( \begin{array}{c}n\\i\\\end{array}\right)=2^n$。

    当 $a=-1,b=1$ 时,有$\sum\left( \begin{array}{c}n\\2k\\\end{array}\right)-\sum\left( \begin{array}{c}n\\2k+1\\\end{array}\right)=0(n\ge1)$

递推阶乘逆元:$\frac{1}{(n-1)!}=\frac{n}{n!}$

递推求组合数的方法

  • 杨辉三角递推,见组合恒等式 $2$。
  • 预处理阶乘,递推处理阶乘逆元,对小质数很可能失效(可用卢卡斯补救)。

Lucas定理:$\left( \begin{array}{c}n\\m\\\end{array}\right)\equiv\left( \begin{array}{c}\lfloor\frac{n}{p}\rfloor\\\lfloor\frac{m}{p}\rfloor\\\end{array}\right)\left( \begin{array}{c}n \ mod \ p\\m \ mod \ p\\\end{array}\right) \ (mod \ p)$

容斥原理:规律为奇加偶减。

错置排序:$D_n=n!(\sum_{i=0}^n\frac{(-1)^i}{i!})$

组合排列问题常见模型

  • 捆绑法:多个对象排列在一起的问题把这些对象合并为一个整体,先考虑整体的组合再考虑整体内部的组合。

  • 插空法:多个对象要分开时,把其他对象排好再在空隙中插入。

  • 插板法:

    • 对于求 $x_1+x_2+…+x_n=m$ 的正整数解,考虑是在 $m$ 个球的 $m-1$ 个空隙中插入 $n-1$ 个板子,因此答案是 $C^{n-1}_{m-1}$。

    • 对于求 $x_1+x_2+…+x_n=m$ 的非负整数解,实际上可以直接把 $x_i$ 变为 $x_i+1$,答案为 $C_{m+n-1}^{n-1}$。

组合排列常用结论

  • 斯特林数

    • 第一类

      定义:$s(n,k)$ 表示 $n$ 个元素构成 $k$ 个圆排列的方案数。

      递推公式:$s(n,k)=s(n-1,k-1)+(n-1)\times s(n-1,k)$。

    • 第二类

      定义:$s(n,k)$ 表示把 $n$ 个不同的元素放入 $k$ 个无差别盒子的方案数。

      递推公式:$s(n,k)=s(n-1,k-1)+k\times s_2(n-1,k)$。

  • 圆排列:$n$ 个元素组成一个长度为 $m$ 的圆排列的方案数为 $A_n^m/m$。