齐肯多夫定理
定义斐波那契数列 \(F_0 = F_1 = 1, F_i = F_{i-2}+F_{i-1}(i\geq 2)\)。
\(x \in \mathbb N\) 的齐肯多夫表示 \(\left<c_1,c_2, \cdots,c_k\right>\) 满足 \(c_1 > 0, c_i > c_{i - 1} + 1\) 且 \(\sum_{i=1}^k F_{c_i} = x\)。
齐肯多夫定理是说，对于任意的 \(x\)，这样的表示存在且唯一。
证明
存在性：我们取出最大的 \(F_i\) 满足 \(F_i \leq x\)，并令 \(x' \gets x - F_i\)。此时 \(x'=x-F_i<F_{i + 1}-F_i = F_{i-1}\)，从而接下来 \(x'\) 选取的数最多为 \(F_{i - 2}\)。
对于充分大的 \(F_n\)，我们用一个长为 \(n - 1\) 的 \(01\) 串表示 \(F_1 \sim F_{n - 1}\) 是否被选取。显然长为 \(n - 1\) 的、没有相邻的 \(1\) 的 \(01\) 串的个数为 \(F_{n}\)；同时可以归纳证明，无论我们如何选取，得到的和总是 \(< F_n\)。从而根据存在性，\([0, F_n)\) 内的每个数都有恰好一种表示。
构造一个给定自然数 \(x\) 的齐肯多夫表示是容易的，与存在性证明的归纳方法类似，\(x > 0\) 时选出最大的 \(F_i \leq x\) 并递归构造 \(x - F_i\) 即可。
齐肯多夫表示的基本运算
加法
计算 \(\left<x_1, x_2, \cdots, x_k\right> + \left<y_1, y_2, \cdots, y_k\right>\)。
先简单相加得到 \(z_i = x_i + y_i\)，此时棘手的是 \(z_i \gt 1\) 的位置。
我们考虑从高位到低位逐步调整，即假设当前位为 \(i\)，已经保证 \((i, k]\) 的位合法。
设 \(\text{Carry}(o)\) 表示从第 \(o\) 位开始不断向高位进位的过程，即如下代码：
void Carry(int o) {
while (z[o] && z[o + 1]) --z[o], --z[o + 1], ++z[o += 2];
}
我们 \(\text{Carry}(i)\) 之后，不难发现若仍有 \(z_i \gt 1\)，那么 \(z_{i + 1} = 0\)。
此时我们拆解 \(2F_i = F_i + F_{i - 1} + F_{i - 2} = F_{i + 1} + F_{i - 2}\)，即 \(z_i \gets z_i - 2, z_{i + 1} \gets 1, z_{i - 2} \gets z_{i - 2} + 1\)。
做完上述操作后，我们仍要 \(\text{Carry}(i+1), \text{Carry}(i)\) 来保证高位的合法性。
定义势能为 \(\sum z_i\)，那么 \(\text{Carry}\) 每循环一次势能就会 \(-1\)，其余操作不改变势能。因此时间复杂度为 \(\mathcal O(k)\)。
减法
计算 \(\left<x_1, x_2, \cdots, x_k\right> - \left<y_1, y_2, \cdots, y_k\right>\)。保证 \(x\) 代表的数大于等于 \(y\) 代表的数。
先令 \(z_i = x_i - y_i\)，美观起见用 \(\bar{1}\) 表示 \(-1\)。
我们仍然是从高位向低位调整，逐步把 \(z\) 重构成只包含 \(0, 1, 2\) 的序列，再应用加法的做法。
同时，由于 \(x \geq y\)，我们任意时刻第一个非 \(0\) 位一定不是 \(\bar{1}\)，因此我们只需要设计 \(1, 2\) 开头的转化即可。
时间复杂度依旧是 \(\mathcal O(k)\)。
正则化
给定 \(N = \sum_{i=1}^n a_i F_i\)，求它的齐肯多夫表示。\(n \leq 10^6, a_i \leq 10^{18}\)。
令 \(N_1 = \sum_{i=1}^n \lfloor \frac{a_i}2\rfloor F_i\)，\(N_2 = \sum_{i=1}^n (a_i \bmod 2)F_i\)。
那么可以递归计算 \(N_1\)，再计算 \(N = N_1 + N_1 + N_2\)。
时间复杂度 \(\mathcal O(n \log a_i)\)。
乘法
计算 \(\left<x_1, x_2, \cdots, x_k\right> \times \left<y_1, y_2, \cdots, y_k\right>\)。