题解：CF1103E Radix sum

· · 题解

题意简述

给定 n 个至多 5 位的自然数 \langle a_n\rangle，从中取 n 次（可以取已经取过的元素），问有多少种情况使得取出来元素的十进制下不进位加法之和为 i。逐行输出 i \in \{0, 1, 2, \dots, n-1\} 时的答案，对 2^{58} 取模。

题目分析

记模 k 数系为 \Z_k = \{0, 1, 2, \dots, k-1\}，其中的加减乘法都在 {}\bmod k 下进行。

记自然数 a 在 k 进制下的表示为 [a_0, a_1, \dots, a_{m-1}]_k，即最多有 m 位。满足

a_i \in \Z_k \land \sum_{i = 0}^{m - 1}a_i k^i = a.

则 k 进制下不进位加法为 a \oplus b = [a_0 + b_0, a_1 + b_1, \dots, a_{m-1} + b_{m-1}]。

定义由 k 进制下不进位加法定义的卷积为

\begin{aligned} \langle w \rangle &= \langle u \rangle \ast \langle v \rangle \\ w_c &= \sum_{c = a \oplus b} u_a v_b \end{aligned}

令 u_s 为序列 \langle a_n\rangle 中 s 的个数，则问题转化为计算 \overbrace{\langle u \rangle \ast \langle u \rangle \ast \dots \ast \langle u \rangle}^{n\text{ times}}。

离散 Fourier 变换

首先解决 m = 1 时的情形。

定义生成函数

A(z) = \sum_{i = 0}^{n-1} z^{a_i} = \sum_{s = 0}^{k-1} u_sz^s.

则问题转化为计算 A(z)^n \bmod (z^{k} - 1)。该运算亦代表长度为 k 的循环卷积。而加速循环卷积的方法，可以借助长度为 k 的离散 Fourier 变换 \mathcal F_k，但是带来了如下问题：

  1. 如果没有 k 次本原单位根 \zeta_k 怎么办？其中 k 次本原单位根是满足 \zeta_k^k = 1 且 1, \zeta_k, \zeta_k^2, \dots, \zeta_k^{k-1} 两两不相同的元素 \zeta_k；
  2. 如果不存在 k^{-1} 怎么办？这将用于离散 Fourier 逆变换 \mathcal F_k^{-1}。

对于本题，答案是对 2^{58} 取模，而 \Z_{2^{58}} 不存在 10 次本原单位根 \zeta_{10}，也不存在 r = 10^{-1} 满足 10r \equiv 1 \pmod{2^{58}}。更一般地，如果答案是对 M 取模，则：

解决上述两个问题的方法都需要扩大数系：

环扩张

对于问题 1，定义

\Z_M[\zeta_k] = \left\{a_0 + a_1\zeta_k + a_2\zeta_k^{2} + \dots + a_{k-1}\zeta_k^{k-1} \mid a_i \in \Z_M \right\}.

显然有 \Z_M \sub \Z_M[\zeta_k] 且显然 \Z_M[\zeta_k] 存在本原单位根 \zeta_k，同时 \Z_M[\zeta_k] 仍可定义加减乘法。此时只要以 \Z_M[\zeta_k] 的元素为系数就可以做离散 Fourier 变换，便解决了问题 1。

对于问题 2，令 g = \gcd(k, M)。此时 (k / g) \perp M，因此在 \Z_M 是存在逆元的；而对于 g \mid M，将 \Z_M 扩张到 \Z_{gM} 后，直接将 \Z_{gM} 的元素整除以 g 就可以得到在 \Z_M 中的结果而保证正确性。

注意：如果不存在本原单位根 \zeta_k，则直接暴力计算卷积的幂甚至优于先做离散 Fourier 变换再逐个快速幂，因为一次卷积的时间复杂度和 \Z_M[\zeta_k] 做一次乘法的时间复杂度相同。对于本题而言使用离散 Fourier 变换有其它的原因，之后会讲到。

到目前为止，整个数系的转化过程为：

\Z_M \to \Z_{gM} \to \Z_{gM}[\zeta_k] \overset{\cal F}\longrightarrow \Z_{gM}[\zeta_k] \overset{\cdot}\longrightarrow \Z_{gM}[\zeta_k] \overset{\cal F^{-1}}\longrightarrow \Z_{M}[\zeta_k]

最后还有一个问题：如何从 \Z_{M}[\zeta_k] 转化回 \Z_M？考虑 k = 5 时，\zeta_5 + \zeta_5^2 + \zeta_5^3 + \zeta_5^4 = -1，也就是说 \Z_M 的元素在 \Z_M[\zeta_k] 存在不止一种表示方法，不能单纯地提取常数项得到结果。

为了解释上述现象产生的原因，这里需要换一个角度重新审视一下 \Z_M[\zeta_k] 的本质。定义

\Z_M[z] = \{a_0 + a_1z + a_2z^2 + \dots + a_{u}z^u \mid a_i \in R\}

即 \Z_M[z] 是全体 \Z_M - 系数多项式构成的集合，其上可定义自然的加减乘法。考虑到 \zeta_k 是方程 z^k - 1 = 0 的根，\Z_M[\zeta_k] 实际上就是 \Z_M[z] / (z^k - 1)，即每个多项式 f(z) \bmod (z^k - 1) 构成的子集。

出现上述情况的原因归根结底，是 $\Z_M[z] / (z^k - 1)$ 中有 $f(z)g(z) = z^k - 1 \equiv 0 \pmod{z^k - 1}$ 这样荒唐的结论成立（其中 $f(z)$ 和 $g(z)$ 不为 $0$）。如果考虑的是一个不可约多项式 $\Phi_k(z)$ 且满足 $\Phi_k(\zeta_k) = 0$，$\Z_M[z] / \Phi(z)$ 就不会遇到上述情况，每个整数因此将具有唯一表示。 #### 分圆多项式 已知若 $\zeta_k$ 是 $k$ 次本原单位根，则对于所有的 $s$，$\zeta_k^s$ 皆为 $\dfrac{k}{\gcd(s, k)}$ 次本原单位根。定义以所有 $k$ 次本原单位根为根的**分圆多项式**为 $$ \Phi_k(z) = \prod_{s \perp k}(z - \zeta_k^s). $$ 则有 $x^k - 1 = \prod_{d \mid k}\Phi_{d}(z)$，因此由 Mobius 变换可得 $\Phi_k(z) = \prod_{d \mid k}(x^d - 1)^{\mu(k/d)}$。本题使用如下不加证明的重要结论： - $\Phi_k(z)$ 在 $\Z_M[z]$ 下是不可约多项式，因而 $\Z_M$ 中的元素在 $\Z_M[z]$ 下仍具有唯一表示。 对于一开始的问题，只需要对 $\Z_M[z] / (z^k - 1)$ 的元素再模一次 $\Phi_k(z)$，就可以得到唯一的 $\Z_M$ 中的整数。 ### 快速 Walsh 变换 由于 $[a_0, a_1, \dots, a_{m-1}]_k$ 各分量之间是独立的，为了加速上述卷积的幂，Walsh 变换指出可以先计算 $$ \langle v \rangle = \mathcal W_m\langle u \rangle \\ v_{[b_0, b_1, \dots, b_{m-1}]_k} = \mathcal F_k\langle u \rangle + $$