CF1103E Radix sum

我们定义数 $a$（由数字 $a_1, \ldots, a_k$ 组成）和数 $b$（由数字 $b_1, \ldots, b_k$ 组成）的“逐位和”为 $s(a, b)$，其结果是一个由 $(a_1 + b_1) \bmod 10, \ldots, (a_k + b_k) \bmod 10$ 组成的数（对于较短的数，在高位补零使其长度与较长的数相同）。多个整数的逐位和定义为：$s(t_1, \ldots, t_n) = s(t_1, s(t_2, \ldots, t_n))$。 给定一个数组 $x_1, \ldots, x_n$。你的任务是，对于每个整数 $i$（$0 \le i < n$），计算从数组中连续选择 $n$ 个整数，使得它们的逐位和等于 $i$ 的方案数。请将这些值对 $2^{58}$ 取模后输出。

第一行包含一个整数 $n$，表示数组的长度（$1 \leq n \leq 100000$）。 第二行包含 $n$ 个整数 $x_1, \ldots, x_n$，表示数组元素（$0 \leq x_i < 100000$）。

输出 $n$ 个整数 $y_0, \ldots, y_{n-1}$，其中 $y_i$ 表示对应的方案数，对 $2^{58}$ 取模。

在第一个样例中，存在如下序列：序列 $(5,5)$ 的逐位和为 $0$，序列 $(5,6)$ 的逐位和为 $1$，序列 $(6,5)$ 的逐位和为 $1$，序列 $(6,6)$ 的逐位和为 $2$。 由 ChatGPT 4.1 翻译