No.1783 Remix Sum
タグ : / 解いたユーザー数 11
作問者 :
PCTprobability
Hints
Hint 1
This problem is a knowledge-based problem. If nothing comes to mind after reading the statement, we recommend doing various research.
Hint 2
The time complexity of the intended solution is about $\mathrm{O}(10^K K^2 \log K)$, but the constant factor is tight, so we recommend using a fast language.
Addendum: The time complexity of the intended solution is $\mathrm{O}(B^K (K^2 \log B \log (BK) + BK + \log P))$, where $B = 10, P = 120524861$.
Partly because the TL turned out less tight than expected, solutions other than the intended one can also pass, but we are actively trying to fail solutions with a factor of $B^K K^2 \log B \log M$, so getting them accepted may be difficult. Thank you for your understanding.
Hint 3
The solution requires an algorithm that can solve at least the cases $T = 0$ , $T = K$.
Hidden Hint (Exciting Bonus)
This problem is actually inspired by certain $2$ problems, and those who have solved both original problems can probably derive the solution easily.And for those who do not know the source material, a cipher that serves as a clue for finding the original problems is, believe it or not, hidden somewhere in this problem.
Decipher the code and obtain the solution to this problem!
Also, since the implementation is heavy, a simple tester has been uploaded to GitHub; please use it if you like.
Problem Statement
You are given $N$ distinguishable balls and integers $K,M,T$.
The balls are numbered $1, 2,\dots, N$, and the number $a_i$ is written on ball $i$.
Nyaan initially holds the integer $0$. Nyaan decides to perform the following operation using the balls.
- Let $x$ be the number currently held.
- Choose $1$ ball from ball $1$, $\dots$, ball $N$, and let $y$ be the number written on the ball.
- Determine the integer $z$, at least $0$ and less than $10^K$, obtained from $x$ and $y$ by the following procedure.
- Let $x_i,y_i$ be the $10^i\ (0 \leq i \lt K)$ digits of $x,y$. (If there are not enough digits, fill in leading-zeros as appropriate.)
- For $i = 0,1,\dots, K-1$, determine the $10^i$ digit $z_i$ of $z$ by the following procedure.
- If $i \lt T$:
- If $x_i + y_i$ is less than $10$, let $z_i = x_i + y_i$.
- If $x_i + y_i$ is at least $10$, Nyaan becomes sad, throws away the integer $x$ being held, and ends all operations.
- If $T \leq i$, let $z_i = (x_i + y_i) \bmod{10}$.
- After determining the value of $z$, replace the number held with $z$.
- If the total number of times a ball has been chosen reaches $M$, end the operation. Otherwise, go back to 1.
For each $0 \leq i \lt 10^{K}$, how many ways are there such that Nyaan holds $i$ after the operations end?
Here, $2$ operations are considered different if the numbers of times a ball was chosen differ, or if there exists some $i$ such that the numbers of the balls chosen at the $i$-th time differ.
Since this month is month $12$, find the answers modulo $120586241$ ($=2^{20} \times 115 + 1$, a prime).
Constraints
- $1 \leq K \leq 5$
- $0 \leq T \leq K$
- $1 \leq N \leq 10^5$
- $0 \leq a_i \lt 10^K \ (1 \leq i \leq N)$
- $2 \leq M \leq 10^{18}$
Input
$N$ $K$ $M$ $T$ $a_1$ $a_2$ $\ldots$ $a_N$
Output
Print $10^K$ lines. On the $i$-th line, print the $i$-th answer.
Also, print a newline at the end.
Sample
Sample 1
Input
2 1 2 1 4 7
Output
0 0 0 0 0 0 0 0 1 0
Unless $4$ is drawn 2 times in a row, Nyaan becomes sad.
Sample 2
Input
2 1 2 0 4 7
Output
0 2 0 0 1 0 0 0 1 0
This is ordinary addition modulo $\bmod{10}$.
Sample 3
Input
10 1 1000000000000000000 0 3 1 4 1 5 9 2 6 5 3
Output
83672471 73084724 33774777 113744514 10105711 101071026 44173257 116400687 36430950 107152270
Sample 4
Input
14 2 14 1 67 70 49 49 48 51 69 0 85 79 74 53 57 54
Output
1002 18018 6097 186186 42224 883064 586040 3312764 2793427 10478104 378 18018 20020 78078 179452 392392 998998 1511510 3871504 6266078 3003 1274 84084 5642 397670 212758 1670760 1235780 5139498 5432336 2002 10010 20020 130130 78078 710710 612794 2858128 2877056 9670388 182 24024 6097 144144 82537 630812 683865 2139748 2774331 7346822 2002 4018 72072 8386 410424 200564 1790880 1300924 5860232 5922854 3003 4018 45045 64078 163177 460642 808808 1972180 3050229 7456008 378 24024 2184 192192 42420 845208 596050 2955330 2571478 9273656 1002 10010 45045 30030 314328 246260 1480479 1318408 5289011 6122858 3432 1274 72072 21294 289562 284662 1231230 1352988 3866226 5703152
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。