問題一覧 > 通常問題

No.1783 Remix Sum

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 8
作問者 : NyaanNyaanNyaanNyaan / テスター : PCTprobabilityPCTprobability
2 ProblemId : 6028 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-19 20:18:11

ヒント

ヒント1

この問題は 知識ゲー です。問題文を一読して心当たりがない方は色々調べてみることをお勧めします。

ヒント2

想定解の計算量は $\mathrm{O}(10^K K^2 \log K)$ 程度ですが定数倍が厳しいので、高速な言語の使用を推奨します。
追記:想定解の計算量は $B = 10, P = 120524861$ として $\mathrm{O}(B^K (K^2 \log B \log (BK) + BK + \log P))$ です。
TL が想定より厳しくなかったのもあり想定解以外の解法でも通りますが、$B^K K^2 \log B \log M$ がつく解法は積極的に落としに行っているので通すのは大変かもしれません。ご了承ください。

ヒント3

少なくとも $T = 0$ , $T = K$ の場合に解けるアルゴリズムが解法に必要です。


 
隠しヒント(ワクワク要素) この問題は実はとある $2$ 題をインスパイアした問題で、元の問題を両方解いた方はおそらく容易に解法が導けるのではないかと思います。
そして、元ネタを知らない方のために、なんとこの問題のどこかに元ネタの問題を発見する手掛かりになる暗号が載っています。
暗号を解読してこの問題の解法を手に入れよう!
また、実装が重いのに配慮して簡易的なテスターを github に上げたのでよければお使いください。

問題文

$N$ 個の区別できるボールと 整数 $K,M,T$ が与えられます。
ボールには番号 $1, 2,\dots, N$ が振られていて、ボール $i$ には数 $a_i$ が書きこまれています。

Nyaan さんははじめ整数 $0$ を持っています。Nyaan さんはボールを使って次の操作を行うことにしました。

  1. 現在の持っている数を $x$ とする。
  2. ボール $1$, $\dots$, ボール $N$ から $1$ 個のボールを選び、ボールに書かれている数を $y$ とする。
  3. $x$ と $y$ によって得られる数 $0$ 以上 $10^K$ 未満の整数 $z$ を次の手順によって決定する。
    • $x,y$ の $10^i\ (0 \leq i \lt K)$ の位を $x_i,y_i$ と置く。(桁数が足りない場合は適宜 leading-zero を埋める。)
    • $i = 0,1,\dots, K-1$ について次の手順で $z$ の $10^i$ の位 $z_i$ を決定する。
    • $i \lt T$の場合
      • $x_i + y_i$ が $10$ 未満のとき $z_i = x_i + y_i$ とする。
      • $x_i + y_i$ が $10$ 以上のとき、 Nyaan さんは悲しい気持ちになって持っている整数 $x$ を捨て、すべての操作を終了する。
    • $T \leq i$ の場合、 $z_i = (x_i + y_i) \bmod{10}$ とする。
  4. $z$ の値を決定したあと、持っている数を $z$ に置き換える。
  5. ボールを選んだ回数が合計で $M$ 回に達したら操作を終了する。そうでない場合、 1. に戻る。

$0 \leq i \lt 10^{K}$ について、操作を終了したあとに Nyaan さんが $i$ を持っている場合の数は何通りありますか?
ただし $2$ つの操作が異なるとは、ボールを選んだ回数が異なるか、ある $i$ が存在して $i$ 回目に選んだボールの番号が異なることを言います。
今月は $12$ 月なので答えを$120586241$($=2^{20} \times 115 + 1$,素数)で割った余りを求めてください。

制約

  • $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}$

入力

$N$ $K$ $M$ $T$
$a_1$ $a_2$ $\ldots$ $a_N$

出力

$10^K$ 行出力してください。$i$ 行目には $i$ 番目の答えを出力して下さい。
また、最後に改行してください。

サンプル

サンプル1
入力
2 1 2 1
4 7
出力
0
0
0
0
0
0
0
0
1
0

2 連続で $4$ を引かないと悲しい気持ちになります。

サンプル2
入力
2 1 2 0
4 7
出力
0
2
0
0
1
0
0
0
1
0

普通の $\bmod{10}$ 上の足し算です。

サンプル3
入力
10 1 1000000000000000000 0
3 1 4 1 5 9 2 6 5 3
出力
83672471
73084724
33774777
113744514
10105711
101071026
44173257
116400687
36430950
107152270

サンプル4
入力
14 2 14 1
67 70 49 49 48 51 69 0 85 79 74 53 57 54
出力
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もしくは右上の雲マークをクリックしてアカウントを作成してください。