modulo operation(模运算):给定一个正整数 m,如果两个整数 a 和 b 满足 a - b 能被 m 整除,即 (a - b)/m 得到一个整数,那么就称整数 a 与 b 对模 m 同余,记作 a≡b (mod m) 。例如 17≡5 (mod 6) ,因为 17 - 5 = 12 能被 6 整除 。
同余性质
congruence(同余):体现了两个整数在模运算下的等价关系 。若 a≡b (mod m) ,c≡d (mod m) ,则 a + c≡b + d (mod m) ,a - c≡b - d (mod m) ,a×c≡b×d (mod m) 等 。这些性质在解决数论问题,尤其是涉及余数的问题时非常有用 。例如,已知 x≡3 (mod 5) ,y≡2 (mod 5) ,那么 x + y≡3 + 2≡0 (mod 5) ,即 x + y 除以 5 的余数为 0 。
multiplication principle(乘法原理):完成一件事,需要分成 n 个步骤,做第 1 步有 m₁种不同的方法,做第 2 步有 m₂种不同的方法…… 做第 n 步有 mₙ种不同的方法,那么完成这件事共有 N = m₁×m₂×…×mₙ种不同的方法 。比如,从 A 城市到 B 城市要经过 C 城市,从 A 到 C 有 2 条路可走,从 C 到 B 有 3 条路可走,那么从 A 经 C 到 B 就有 2×3 = 6 种不同走法,这便是乘法原理的体现 。
排列组合
permutation(排列):从 n 个不同元素中取出 m(m≤n)个元素的所有排列的个数,叫做从 n 个不同元素中取出 m 个元素的排列数,用符号 A (n, m) 表示 。计算公式为 A (n, m)=n (n - 1)(n - 2)…(n - m + 1) 。例如,从 5 个不同元素中选 3 个进行排列,A (5, 3)=5×4×3 = 60 。
combination(组合):从 n 个不同元素中取出 m(m≤n)个元素的所有组合的个数,叫做从 n 个不同元素中取出 m 个元素的组合数,用符号 C (n, m) 表示 。计算公式为 C (n, m)=A (n, m)/m! = n! / [m!(n - m)!] 。例如,从 5 个不同元素中选 3 个的组合数 C (5, 3)=5! / [3!(5 - 3)!]=10 。这里要注意排列与组合的区别,排列考虑元素的顺序,而组合不考虑顺序 。比如从 1、2、3 中选两个数组成两位数,这是排列问题,有 A (3, 2)=6 种情况(12、21、13、31、23、32);若只是选两个数,不考虑顺序,那就是组合问题,C (3, 2)=3 种情况(1 和 2、1 和 3、2 和 3) 。
(二)概率基础
概率相关
probability(概率):对随机事件发生可能性大小的度量,取值范围在 0 到 1 之间 。若一个事件必然发生,其 probability 为 1;若一个事件不可能发生,其 probability 为 0 。例如,抛一枚均匀硬币,正面朝上的 probability 是 0.5 。