变进制数的一些研究成果

· · 算法·理论

变进制数的一些研究成果

AI 生成的内容需注明：这是 DeepSeek 润色的。

变进制表示的定义

以下所有数组，如无特别说明，下标均从 0 开始。

对于长度为 n 的正整数数组 C，定义其前缀积数组 B：B_i = \prod_{j < i} C_j（B_0 = 1）。称一个长度为 n+1 的整数数组 a 为数 X 的 C 进制表示，若满足

X = \sum_{i=0}^{n} a_i B_i。

若对所有 0 \le i < n 均有 0 \le a_i < C_i，则称该表示为正规的。此时记 a_i 为 X_C[i]，在不引起歧义时简记为 X[i]。显然当 X>0 时，X[i] = \left\lfloor X/B_i \right\rfloor \bmod C_i，这如同“取出数字中的某一位”。

变进制表示的正规化

若一个表示不是正规的，可通过如下方式将其修正为正规的：按 i 从 0 到 n-1 的顺序，将 X[i] 写为 X[i] = p C_i + q，其中 0 \le q < C_i，然后将 X[i] 改为 q，并将 X[i+1] 增加 p。该过程类似于高精度运算中的进位。

一些平凡的运算

将整数 X 转换为 C 进制表示，只需对表示 \{X, 0, 0, \dots, 0\} 进行正规化。

两个 C 进制表示 X, Y 相加，结果为 \{X[0]+Y[0], X[1]+Y[1], \dots, X[n]+Y[n]\}，然后正规化。

对 $C$ 进制表示取相反数，可将所有 $X[i]$ 取相反数，但这样不利于体现结构。若原表示为正规的，则可按如下方式得到相反数的正规表示：找到最小的 $p$ 使得 $X[p] \neq 0$，令 $X'[p] = C_p - X[p]$；对 $p < i < n$，令 $X'[i] = C_i - 1 - X[i]$；最后令 $X'[n] = -1 - X[n]$。 $C$ 进制表示 $X$ 与一个整数 $Y$ 相乘，结果为 $\{X[0]\cdot Y, X[1]\cdot Y, \dots, X[n]\cdot Y\}$，随后正规化。 ## 变进制表示转回整数 直接按定义式计算即可，但存在更优雅的做法：初始化 $Y = X[n]$，然后从 $i = n-1$ 向下枚举到 $0$，执行 $Y = Y \times C_i + X[i]$。这避免了部分高精度运算，同时也给出了转换进制的一种方法——只需将 $Y$ 维护为另一种变进制表示即可。 ## 变进制表示的乘法 给定 $C$ 进制表示 $X$ 和 $D$ 进制表示 $Y$，可以求出 $XY$ 的 $D$ 进制表示。做法如下：令 $D$ 进制的表示 $Z = X[n] Y$，然后从 $i = n-1$ 向下枚举到 $0$，执行 $Z = Z \times C_i + X[i] Y$。这本质上是“变进制表示转回整数”的一种自然推广。 ## 整数转变进制表示的一些优化 1. **压位优化**：输入的整数可以任意压位。输出的变进制数也可以压位：将 $O(w / \log \max C)$ 个 $C_i$ 先乘在一起，转换为压位表示后再拆分回来（拆分时整数很小，无需高精度运算，速度很快）。 2. **提前终止**：若 $B_n$ 明显大于输入的整数，则结果的后缀可能出现大段零。此时若当前已全为零，可以安全退出算法，从而降低复杂度。例如，将十进制高精度整数转换为 $\{1,2,\dots,n\}$ 进制时，由于 $B_n \sim \exp\!\bigl(n\ln n - n + \frac12\ln(2\pi n)\bigr)$ 增长极快，远大于 $10^n$。粗略估计，若输入的十进制整数有 $m$ 位，则取 $n = O(m / \log m)$ 便已足够。 ## 变进制数和阶乘字典序的关系 阶乘字典序的计算由康托展开给出： > 排列 $a$ 的字典序为： > $$ > \mathrm{ans} = 1 + \sum_{i=1}^{n} A[i] \times (n-i)!, > $$ > 其中 $A[i] = \sum_{j=i}^{n} [a_j < a_i]$。 将 $A$ 反转后，便得到排列字典序在 $\{1, 2, \dots, n\}$ 进制下的表示。因此，我们可以对这样的变进制表示进行各种变进制运算。当然，$A$ 可以自由地与排列相互转换，借助适当的数据结构即可实现。 排列转为 $A$：离线静态二维数点，树状数组即可。 $A$ 转为排列：从前往后取出并删除全局第 $k$ 小，树状数组二分即可。 ## 例题 0：状态压缩 常见的问题：对于非负整数数组 $c_1, c_2, \dots, c_n$，若 $\sum_i c_i = m$，则 $\prod_i (c_i+1) = O(2^m)$（也就是 $O(\exp(m))$），远小于 $O(m^n)$。利用变进制数可以将所有满足 $a_i \le c_i$ 的非负整数数组 $a$ 压缩为 $\prod_i (c_i+1)$ 个状态，达到最优状态数。 另外一个类似的，我们有 $\prod_ic_i=O(3^{m/3})$（也就是 $O(\exp(m/e))$。可以应用到例如 [P5972 [PA 2019] Desant - 洛谷](https://www.luogu.com.cn/problem/P5972) 这题上。 ## 例题 1：[P15375 Soso 的模法矩阵 / modmat - 洛谷](https://www.luogu.com.cn/problem/P15375) 维护一个 $b$ 进制数 $X$，初始 $X = 1$。按 $i$ 从 $1$ 到 $n$ 枚举，每次将 $X$ 乘上 $a_i$，然后取 $f(i,j) = X[1..j]$（即 $\{X[1], X[2], \dots, X[j]\}$），将其转入模 $M$ 的域中计算即可。根据定义式直接计算非常方便，复杂度 $O(nm)$。注意无需维护 $X[m]$。 ## 例题 2：[P15394 Soso 的排列 / soperme - 洛谷](https://www.luogu.com.cn/problem/P15394) 使用 $\{1, 2, \dots, n\}$ 进制数，可按如下方式解决问题： 1. 求出 $p$ 的变进制表示； 2. 计算 $\le p$ 的答案； 3. 将变进制表示加上 $k$（自然溢出即可，无需特判）； 4. 计算 $\le p+k$ 的答案； 5. 合并两个答案。 计算 $\le p$ 的答案部分较为繁琐，不属于本文重点，故略去。 注意此处需要维护 $X[n]$，因为它体现了跳过所有排列的次数，对应有相应贡献。整体复杂度 $O(n \log n)$。 ## 例题 3：[U667696 Soso 的排列 2 - 洛谷](https://www.luogu.com.cn/problem/U667696) 1. **长度优化**：最终转换出的变进制数长度为 $\ell = O(m / \log m)$，而非 $O(m)$。证明可利用阶乘的斯特林公式，此处从略。例如 $k = 10^{100000}$ 时，$\ell = 25205$；$k = 10^{200000}$ 时，$\ell = 47175$。这一优化将原来的 $O(m^2)$ 算法除去了一个 $\log m$ 因子。 2. **压位高精度**：由于题目输入为十进制，只能采用压 $9$ 位（即 $10^9$ 进制）的高精度表示，相当于将复杂度再除去一个位长因子 $w = 9$。 结合上述两项优化，即可通过本题。总复杂度为 $O\!\left( \dfrac{m^2}{w \log m} + n \log n \right)$。 ## 例题 4：求逆元 给定低精度整数 $a, c$，以及长度为 $n$ 的正整数数组 $C$，记 $B_i = \prod_{j < i} C_j$（$B_0 = 1$）。对于每个 $i$，考虑同余方程 $$ a x_i \equiv c \pmod{B_{i+1}}, $$ 假设解存在且唯一。我们希望求出所有 $x_i$。 一种自然的思路是先求出 $x_{n-1}$，然后利用 $x_i \equiv x_{n-1} \pmod{B_i}$ 得到其余解。但这里我们给出一个基于变进制数的递推方法。 将 $c$ 转换为 $C$ 进制表示，记其第 $i$ 位为 $c[i]$。设 $X$ 是满足 $a X \equiv c \pmod{B_n}$ 的一个解，并将其表示为 $C$ 进制数 $X[0..n-1]$（$X[n]$ 可以取 $0$）。我们希望通过递推逐位确定 $X[i]$。 定义 $r_i$ 为前 $i$ 位产生的“进位”： $$ r_i = \frac{\sum_{j=0}^{i} \bigl(a X[j] - c[j]\bigr) B_j}{B_{i+1}}. $$ 注意 $r_i$ 是整数，因为 $a \sum_{j=0}^{i} X[j] B_j \equiv \sum_{j=0}^{i} c[j] B_j \pmod{B_{i+1}}$。 递推关系如下： - 已知 $r_{i-1}$，考虑 $i$ 位。由 $a X[i] B_i$ 的贡献，应满足 $$ a X[i] \equiv c[i] - r_{i-1} \pmod{C_i}. $$ 由于方程有解，可求出 $X[i]$（需计算模 $C_i$ 下的逆元）。 - 然后更新 $r_i$： $$ r_i = \frac{a X[i] - c[i] + r_{i-1}}{C_i}. $$ 初始 $r_{-1} = 0$，最终 $r_{n-1} = 0$（因解满足模 $B_n$ 的同余式）。这样便依次求出了 $X[0], X[1], \dots, X_{n-1}$，进而得到 $x_i = \sum_{j=0}^{i} X[j] B_j$。 该过程类似于牛顿迭代法逐次提升精度，也类似于多项式求逆，但这里是诡异的“单项式求逆”。