← 返回题目列表

Codeforces · 1103/E

E. 基数总和

中文机器翻译题面 查看原题

让我们定义由数字 $$$a_1、\ldots 、a_k$$$ 组成的数字 $$$a$$$ 和由数字 $$$b_1、\ldots 、b_k$$$ 组成的数字 $$$b$$$ 的基数和(我们在较短的数字上添加前导零以匹配较长的长度)为由数字组成的数字 $$$s(a,b)$$$ $$$(a_1+b_1)\mod 10,\ldots,(a_k+b_k)\mod 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}$$$。

示例

输入 #1

2
5 6

输出 #1

1
2

输入 #2

4
5 7 5 7

输出 #2

16
0
64
0

注意

在第一个示例中,存在序列:序列$$$(5,5)$$$,基数和$$$0$$$,序列$$$(5,6)$$$,基数和$$$1$$$,序列$$$(6,5)$$$,基数和$$$1$$$,序列$$$(6,6)$$$,基数和$$$2$$$。