本文多为参考《具体数学》一书，若有其他参考资料将额外列出。

递归问题

一般步骤

  1. 研究小的情形——这有利于我们洞察该问题
  2. 对有意义的量求出数学表达式并给出证明（如求出递归式）
  3. 对数学表达式求出封闭形式并给出证明（一般是对递归式求出递归解）

和式处理

和式运算律

  1. 分配律 $\sum_{k \in K}ca_k = c \sum_{k \in K}a_k$
  2. 结合律 $\sum_{k \in K} (a_k + b_k) = \sum_{k \in K} a_k + \sum_{k \in K} b_k$
  3. 交换律 $\sum_{k \in K}a_k = \sum_{p(k)\in K} a_{p(k)}$

其他

自然数立方和公式

证明（是《Proofs that Really Count》一书第8章Number Theory中的内容）

运用数学归纳法。

当 $n = 1$ 时，$1^3 = \left ( \frac{1 \times 2}{2} \right ) ^ 2$ ，成立。

假设当 $n = k$ 时， $\sum_{i = 1}^k i^3 = \left ( \frac{k(k+1)}{2} \right )^2$ 成立，

那么当 $n = k + 1$ 时，

得证。

任何一个十进制整数模 9 同余于它各数位上数字的和

证明（不严谨） ：

把这个十进制数拆成各数位乘上十的幂次的和的形式。

由于十的各幂次模 $9$ 都为 $1$，且模运算对整数加法和乘法具有结合律，发现每个十的幂都可以化为 $1$ 消掉。

然后就变成了各数位的和。

二进制集合操作

在状压DP中很常用，算是必备技能。

lyd蓝书上似乎有比较全面的介绍，但是手里没蓝书（

所以只能借鉴 OI Wiki

交并补和取出后几位这样的操作大致不必介绍了。

最简单的遍历集合是遍历全集，简单来讲 ：

1
for(int i = 1;i <= (1 << n);i++);

这样得到的 $i$ 就是所有子集。

而在很多情况下，我们希望遍历的是某个给定集合的子集，那么此时再使用这样的方法并判断 $i$是否被已知集合包含则会导致许多不必要的运算。

于是我们可以这样做 ：

1
for(int s = m;s;s = (s - 1) & m);

显然这份代码不会遍历空集，若要考虑空集应当加上特判。

考虑这份代码的意义，每次的减一操作实际上是把 lowbit 的位置变成 $0$，然后将所有更低位变成 $1$，然后与原集合取交，避免了多余元素出现。于是我们忽略掉原集合中为 $0$ 的位置会发现：这样做实际上就像是枚举集合中有几个元素然后枚举位置的过程，于是感性理解之下我们可以明白这个做法的正确性。

以上两种做法的复杂度是 $O(2^n)$ 量级，更严谨地说，第二种方法的复杂度应当是 $O(2^{popcount(m)})$。

结合以上两种方法，我们可以遍历全集中每个元素的子集 ：

1
2
for(int m = 0;m < (1 << n);m++)
    for(int s = m;s;s = (s - 1) & m);

其中 $n$ 是全集中元素的个数。

这个做法的复杂度是 $O(3^n)$ ,证明来自oi-wiki ：

考虑某一个位置的方案有几种 ：

  • 该元素不在两个集合中
  • 该元素在大集合中，但不在小集合中
  • 该元素在这两个集合中

于是枚举的过程就是组合所有位置的这三种情况，复杂度为 $O(3^n)$。