浅记齐肯多夫表示

定义斐波那契数列 \(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\)，这样的表示存在且唯一。

构造一个给定自然数 \(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>\)。