問題一覧 > 通常問題

No.1783 Remix Sum

レベル : / AI推定難易度 : 3125 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 11
作問者 : NyaanNyaan / テスター : PCTprobability
お気に入りにしたユーザー ProblemId : 6028 / 自分の提出
問題文最終更新日: 2026-09-26 02:23:50
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2021 (順位表) の他の問題:

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.

  1. Let $x$ be the number currently held.
  2. Choose $1$ ball from ball $1$, $\dots$, ball $N$, and let $y$ be the number written on the ball.
  3. 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}$.
  4. After determining the value of $z$, replace the number held with $z$.
  5. 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もしくは右上の雲マークをクリックしてアカウントを作成してください。