【算法笔记】组合数学

组合数学"/>

【算法笔记】组合数学

目录

• • 前言
  • 说明
  • 栗子
  • 计算逆元
  • 解决方法
  • 例题1-小y的组合数取模问题
  • • Description
    • Input
    • Output
    • Data
    • Solution
    • Code
  • 例题2-乘法序列
  • • Description
    • Input
    • Output
    • Data
    • Solution
    • Code
  • 尾声

前言

在 O I OI OI 中，大多数情况下，善良的出题人为了避免高精度等大整数计算，常常会要求输出答案对一个数（大多是质数）取模的情况，但这衍生了一个问题：若题目中计算需用到除法而我们知道，如果 a ≡ b ( m o d c ) a \equiv b \pmod{c} a≡b(modc) 在大部分情况下 ⌊ a d ⌋ ≢ ⌊ b d ⌋ ( m o d c ) \lfloor \frac {a} {d} \rfloor \not\equiv \lfloor \frac {b} {d} \rfloor \pmod{c} ⌊da​⌋​≡⌊db​⌋(modc) （注意一般题目会默认对一个数取模是数论（整数）意义上的取模，故这里除法为整数除法），这和等式的性质是不同的，要解决这个问题，就需要用到一个概念：乘法逆元。

说明

我们来举个例子吧，先再实数范围举例，由小学知识可知，如果一个代数式 F F F 乘一个数 a a a 后，再乘它的倒数 1 a \frac {1} {a} a1​ ，相当于没有乘 a a a （这里不考虑 0 0 0 的情况），换句话说，我们乘 1 a \frac {1} {a} a1​ 后，取消了代数式 F F F 乘 a a a 后值增大的影响。
不难发现这符合逆元的定义，故我们可以说一个数和其倒数互为乘法逆元。除此之外，我们还能发现一个数和其相反数互为加法逆元等等……

接下来回到代数式的例子，考虑为什么 a a a 的倒数 1 a \frac 1 a a1​ 能消去乘 a a a 的影响。显然，是由于乘法结合律的存在，使得我们在运算 F × a × 1 a F \times a \times \frac 1 a F×a×a1​ 时可以先运算 a × 1 a a \times \frac 1 a a×a1​ 的值，再运算它和 F F F 的乘积，而 a × 1 a = 1 a \times \frac 1 a = 1 a×a1​=1 ，任何数与 1 1 1 的乘积均为其本身，从而使乘 a a a 对