No.1783 Remix Sum
タグ : / 解いたユーザー数 9
作問者 :
NyaanNyaan
/ テスター :
PCTprobability
ヒント
ヒント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 さんはボールを使って次の操作を行うことにしました。
- 現在の持っている数を $x$ とする。
- ボール $1$, $\dots$, ボール $N$ から $1$ 個のボールを選び、ボールに書かれている数を $y$ とする。
- $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}$ とする。
- $z$ の値を決定したあと、持っている数を $z$ に置き換える。
- ボールを選んだ回数が合計で $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もしくは右上の雲マークをクリックしてアカウントを作成してください。