题目简述：对任意两个（正）十进制数$a = \overline{a_{k-1}\dots a_1a_0}$和$b = \overline{b_{k-1}\dots b_1b_0}$，定义其【十进制按位加法（Decimal digit-wise addition）】$c = a \oplus b = \overline{c_{k-1}\dots c_1c_0}$，其中$c_i = (a_i+b_i) \bmod 10$。给定$1 \leq n \leq 10^5$个正整数$0 \leq x_i < 10^5$，对每个$0 \leq k < n$，求有多少个下标序列$1 \leq i_1, i_2, \dots, i_n \leq n$，使得
$$\bigoplus_{j=1}^n x_{i_j} = k. $$
答案$\bmod 2^{58}$。
解：
建模：
设$a_k$表示$k$在$x_1, x_2, \dots, x_n$中出现的次数，定义母函数（Generating function）
$$ a(x) = a_0x^0 + a_1x^1 + a_2x^2 + \dots + a_{N-1}x^{N-1}, $$
其中$N = 10^5$。
定义【按位卷积（Digit-wise convolution）】
$$ (a \odot b) (x) = a(x) \odot b(x) = \sum_{i=0}^{N-1} \sum_{j=0}^{N-1} a_i b_j x^{i \oplus j}. $$
若记$a^{\odot m} = a^{\odot (m-1)} \odot a$且$a^{\odot 1} = a$，则对每个$0 \leq k < n$，$a^{\odot n}(x)$中$x^k$的系数即为所求。
记进制$B = 10$。实际上，$a \odot b$是一个$d = \log_B N = 5$维卷积。
多维广义离散傅里叶变换（Multidimensional general discrete Fourier transform）：
设$R$是环（Ring），正整数$n \geq 1$，称$\omega$是$R$的主$n$次单位根（Principal $n$-th root of unity），若
$$ \begin{aligned} & \omega^n = 1, \\ & \sum_{j=0}^{n-1} \omega^{jk} = 0 \text{ for } 1 \leq k < n. \end{aligned} $$
特别地，若$R$是整环（Integral domain），则第二个条件可以简化为$\omega^{k} \neq 1$对$1 \leq k < n$。
记模$n$剩余类环为$\mathbb{Z}_{n} = \mathbb{Z}/n\mathbb{Z}$。令$a: \mathbb{Z}_{n} \to R$，或记作多项式
$$ a(x) = a_0x^0 + a_1x^1 + \dots + a_{n-1}x^{n-1}. $$
定义傅里叶变换将$a$变换成$b = \mathcal{F}(a)$为
$$ b_k = \sum_{j=0}^{n-1} \omega^{jk} a_j. $$
若$n = \underbrace{1+1+\dots+1}_{n} \in R$且$n^{-1}$在$R$中存在，则傅里叶变换的逆变换$a = \mathcal{F}^{-1}(b)$为
$$ a_j = n^{-1} \sum_{k=0}^{n-1} \omega^{-jk} b_k. $$
当$n^{-1}$不存在时，可退而求其次有$na = \mathcal{F}^*(b)$为
$$ na_j = \sum_{k=0}^{n-1} \omega^{-jk} b_k. $$
设$R_1, R_2, \dots, R_d$均是环，$\omega_1, \omega_2, \dots, \omega_d$依次是$R_1, R_2, \dots, R_d$的主$n_1, n_2, \dots, n_d$次单位根。
令$a: \mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2} \times \dots \times \mathbb{Z}_{n_d} \to R$，或者记作多项式
$$ a(x_1, x_2, \dots, x_n) = \sum_{i_1=0}^{n_1-1} \dots \sum_{i_d=0}^{n_d-1} a_{i_1, i_2, \dots, i_d} x_1^{i_1} \dots x_d^{i_d}. $$
定义傅里叶变换将$a$变换成$b = \mathcal{F}(a)$为
$$ b_{k_1, k_2, \dots, k_d} = \sum_{j_1 = 0}^{n_1-1} \dots \sum_{j_d = 0}^{n_d-1} \omega_1^{j_1k_1} \dots \omega_d^{j_dk_d} a_{j_1,j_2,\dots,j_d}. $$
其逆变换为
$$ a_{j_1,j_2,\dots,j_d} = n_1^{-1} n_2^{-1} \dots n_d^{-1} \sum_{k_1 = 0}^{n_1-1} \dots \sum_{k_d = 0}^{n_d-1} \omega_1^{-j_1k_1} \dots \omega_d^{-j_dk_d} b_{k_1, k_2, \dots, k_d}. $$
性质：
$$ \mathcal{F}(a) \cdot \mathcal{F}(b) = \mathcal{F}(a \odot b), $$
其中$(x \cdot y)(k) = x(k) \cdot y(k)$。进而
$$ \mathcal{F}^{-1}((\mathcal{F}(a))^m) = a^{\odot m}, $$
其中$x^m = x^{m-1} \cdot x$且$x^1 = x$。
在本题中，$n_1 = n_2 = \dots = n_d = B$。
环$R$的选取：
一般取复数域$R = \mathbb{C}$，则$\omega = \exp \left( \frac {2i \pi} n \right)$。但此题要求模$2^{58}$，浮点数精度不足以支撑（一般只能支持$a_j \sim 10^5$的情况）。为此，我们需要另外的环。我们引入分圆多项式（Cyclotomic polynomial），$n$阶分圆多项式定义为
$$ \Phi_n(x) = \prod_{1 \leq k \leq n, \gcd(k, n) = 1} \left( x - \exp\left(\frac{2i \pi k}{n}\right) \right). $$
特别地，
$$ \Phi_{10}(x) = x^4-x^3+x^2-x+1. $$
定理：
$$ \mathbb{Z}[x]/(\Phi_n(x)) \simeq \mathbb{Z}[\omega_n], $$
其中$\omega_n = \exp \left( \frac {2i\pi} {n} \right)$。注意到，$x$是$\mathbb{Z}[x]/(\Phi_n(x))$的主$n$次单位根。
为将答案模$2^{58}$，我们取$R = \mathbb{Z}_{2^{64}}[x]/\Phi_{10}(x)$，但此环中$N = 10^5$的逆，即$N^{-1}$，不存在，故只能有
$$ \mathcal{F}^*\left(\left(\mathcal{F}(a)\right)^{m}\right) \equiv N a^{\odot m} \pmod {2^{64}}. $$
于是，最后剩下一个数论问题：已知$y = 10^5 x \bmod 2^{64}$，其中$x \in \mathbb{Z}$，求$x \bmod 2^{58}$。
注意到必有$2^5 | y$，令$z = \frac y {2^5}$，则$z \equiv 5^5 x \pmod {2^{58}}$。
又$\gcd(5^5, 2^{58}) = 1$，故$(5^5)^{-1} \equiv (5^5)^{\phi(2^{58})-1} \pmod {2^{58}}$，其中$\phi(\cdot)$是欧拉函数（Euler's totient function）。
进而，$x \equiv (5^5)^{-1} z \pmod {2^{58}}$。
时间复杂度：
$O(D^2 B N \log_B N+D^2 N \log n)$，其中$D = \operatorname{deg} \Phi_B(x) = 4$。
解2：
可取$\mathbb{Z}[x]/(\Phi_5(x))$，其中$\Phi_5(x) = x^4+x^3+x^2+x+1$，且$-x$是主$10$次单位根。
在计算$\omega^{jk} a_j$时，朴素多项式乘法需要$O(D^2)$复杂度。为了降低复杂度，我们取$R = \mathbb{Z}[x]/(x^5-1)$，而$\mathbb{Z}[x]/(\Phi_5(x))$作为其子环。
这时，在$\mathbb{Z}[x]/(x^5-1)$中计算$\omega^{jk} a_j$，可在$O(D)$的复杂度内完成。
从而总时间复杂度为$O(D B N \log_B N + D^2 N \log n)$，其中$D = \operatorname{deg} (x^5-1) = 5$。