数学

基础思想

余数

同余定理：两个整数a和b，如果它们除以正整数m得到的余数相等，我们就可以说,a和b对于模m同余。同余定理其实就是用来分类的。

求余就是一种哈希

迭代法

不断地用旧的变量值，递推计算新的变量值

基本步骤：

数学归纳法

用来证明任意一个给定的情形都是正确的

和使用迭代法的计算相比，数学归纳法最大的特点就在于归纳二字。它已经总结出了规律。只要我们能够证明这个规律是正确的，就没有必要进行逐步的推算

  1. 证明基本情况（通常是 n=1 的时候）是否成立
  2. 假设 n=k−1 成立，再证明 n=k 也是成立的（k 为任意大于 1 的自然数）

递归

递归和循环其实都是迭代法的实现，而且在某些场合下，它们的实现是可以相互转化的

递归的核心思想和数学归纳法类似，并更具有广泛性：

  1. 一个当前所采取的步骤
  2. 另外一个更简单的子问题

分而治之 的思想需要使用递归来实现

排列

从n个不同的元素中取出m (1<=m<=n) 个不同的元素，按照一定的顺序排成一列，这个过程就叫排列。当m=n的时候，这就是全排列。

组合

组合是指，从n个不同元素中取出m (1<=m<=n) 个不同的元素。所有m取值的组合之全集合，我们可以叫作全组合。