Codeforces Round 534 (Div. 1) |
---|
Finished |
Let's define radix sum of number $$$a$$$ consisting of digits $$$a_1, \ldots ,a_k$$$ and number $$$b$$$ consisting of digits $$$b_1, \ldots ,b_k$$$(we add leading zeroes to the shorter number to match longer length) as number $$$s(a,b)$$$ consisting of digits $$$(a_1+b_1)\mod 10, \ldots ,(a_k+b_k)\mod 10$$$. The radix sum of several integers is defined as follows: $$$s(t_1, \ldots ,t_n)=s(t_1,s(t_2, \ldots ,t_n))$$$
You are given an array $$$x_1, \ldots ,x_n$$$. The task is to compute for each integer $$$i (0 \le i < n)$$$ number of ways to consequently choose one of the integers from the array $$$n$$$ times, so that the radix sum of these integers is equal to $$$i$$$. Calculate these values modulo $$$2^{58}$$$.
The first line contains integer $$$n$$$ — the length of the array($$$1 \leq n \leq 100000$$$).
The second line contains $$$n$$$ integers $$$x_1, \ldots x_n$$$ — array elements($$$0 \leq x_i < 100000$$$).
Output $$$n$$$ integers $$$y_0, \ldots, y_{n-1}$$$ — $$$y_i$$$ should be equal to corresponding number of ways modulo $$$2^{58}$$$.
2 5 6
1 2
4 5 7 5 7
16 0 64 0
In the first example there exist sequences: sequence $$$(5,5)$$$ with radix sum $$$0$$$, sequence $$$(5,6)$$$ with radix sum $$$1$$$, sequence $$$(6,5)$$$ with radix sum $$$1$$$, sequence $$$(6,6)$$$ with radix sum $$$2$$$.
Name |
---|