F - Preimage Resistance

概要

少し実装量が多めですが，一つ一つ課題を解決していくことで解くことができます．
また，少し深く考察をして実装量を減らすことも可能です．

問題原案：uni_kakurenbo

略解

先頭から求める

$P_i := ($先頭 $i$ 項を決定したとき，残りの $M - i$ 項は何通りの選び方ができるか$)$ とします．

$K$ をデクリメントして $K$ が 0-based の前提で考えると，求めるべき列の $1$ 項目は，先頭が $H_1$ であるような文字列のうち辞書順で $\lfloor \frac{K}{P_1} \rfloor$ 番目に小さいものであり，残りの $M - 1$ 項は『$P_1$ 通りの選び方の中から辞書順で $K \bmod P_1$ 番目に小さいもの』を求めればよいです．
結局，再帰的に同じ処理を繰り返して答えを求めることができます．(『カッコ内』がちょうど，大きさの小さい同様の問題になっています．)

$P_i$ は簡単な DP によって求めることができますが，その際は乗算のオーバーフローに注意してください．

末尾から求める

$10$ 進法からの基数変換の要領で，末尾から順に求めていくこともできます．
先頭から求めていった場合に比べて，実装量は低減されるはずです．

解説

$d[h] := ({S^{(i)}}_1 = h$ であるような $i$ の個数) とします．

$Ⅰ.$ 先頭から順に決定する

$P_i := ($先頭 $i$ 項を決定したとき，残りの $M - i$ 項は何通りの選び方ができるか$)$ とします．
$P_i = d[H_M] \times d[H_{M-1}] \times \cdots \times d[H_{i + 1}]$ ですから，これは次に示すような DP によって $i$ の降順に $O(M)$ 時間で計算できます．

• $P_M = 1$
• $\text{For}\;k \xleftarrow{\text{each}} [M-1,M-2,\ldots,0]:$
  • $P_i = P_{i+1} \times d[H_{i+1}]$

以降 $K$ をデクリメントして $K$ が 0-based の前提で考えます．

求めるべき列の $1$ 項目は，先頭が $H_1$ であるような文字列のうち辞書順で $\lfloor \frac{K}{P_1} \rfloor$ 番目に小さいものであるといえます．
残りの $M - 1$ 項は『$P_1$ 通りの選び方の中から辞書順で $K \bmod P_1$ 番目に小さいもの』を求めればよいです．

この残った $M - 1$ 項の求め方が，元の問題と全く同じということに気づいたでしょうか．

これを利用することで，次のように先頭から順々に求めていくことができます．

• $1$ 項目($M$ 項のうちの先頭)を求める．
  • これは $\lfloor \frac{K}{P_1} \rfloor$ 番目に小さいもの．
  • 残りの $M - 1$ 項目は，$P_1$ 通りの中で $K \bmod P_1$ 番目に小さいもの．
  • $K \gets K \bmod P_1$
• $2$ 項目(末尾 $M-1$ 項のうちの先頭)を求める．
  • これは $\lfloor \frac{K}{P_2} \rfloor$ 番目に小さいもの．
  • 残りの $M - 2$ 項目は，$P_2$ 通りの中で $K \bmod P_2$ 番目に小さいもの．
  • $K \gets K \bmod P_2$
• $3$ 項目(末尾 $M-2$ 項のうちの先頭)を求める．
• $\vdots$
• $M$ 項目(末尾 $1$ 項のうちの先頭)を求める．
  • これは $\lfloor \frac{K}{P_M} \rfloor$ 番目に小さいもの．
  • 残りは $0$ 項．

注記： $P_i$ のオーバーフロー対策

$N, M$ の制約を考えると，$P_i$ の値を求める段階でオーバーフローが生じてしまう可能性が非常に高いです．
これは，$K < 10^{18}$ という制約を利用して，積が $10^{18}$ を超える場合は強制的に $10^{18}$ とするようにするとよいです．
($K$ はデクリメントして 0-based で考えていることに注意してください．)

ABC169 - B でこれと同等の処理をする問題が出題されています．

$Ⅱ.$ 末尾から順に決定する

より実装量の少ない解法を紹介します．

答えとなる列の $i$ 項目としてあり得る文字列が $d[H_i]$ 通りあることは明らかです．

答えの $i$ 項目となる文字列を直接求めるのではなく，「答えの $i$ 項目は，それとしてあり得る $d[H_i]$ 通りのもののうちで何番目に小さいものか」を求めるとします．

たとえば，入出力例 $1$ について考えてみます．

$K$ の値は簡単のために 0-based で考えたいので，デクリメントして $K=5$ とします．

• $1$ 項目としてあり得るものは，辞書順で昇順に the, topcoder の $2$ 通り
• $2$ 項目としてあり得るものは，辞書順で昇順に grand, gray の $2$ 通り
• $3$ 項目としてあり得るものは，辞書順で昇順に competition, contest の $2$ 通り

です．
したがって，答えである，辞書順で $5$ 番目に小さい列 $($topcoder, grand, contest$)$ は，

• $1$ 項目は，$2$ 通りのうち $1$ 番目に小さい topcoder
• $2$ 項目は，$2$ 通りのうち $0$ 番目に小さい grand
• $3$ 項目は，$2$ 通りのうち $1$ 番目に小さい contest

ですから，$(1, 0, 1)$ と表せることになります．(便宜上これらも 0-based で考えます．)
以降このような表記方法を「(文字列の列の)数列表現」と呼ぶこととします．

この数列を求めます．

この数列の各項について，$i$ 項目の数値は明らかに $0$ 以上 $d[H_i]$ 未満です．

もう一度入力例 $1$ に戻って考えます．
答えとしてあり得る列の数列表現を辞書順に列挙してみましょう．
これは，辞書順の定義より明らかに $(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)$ となります．

いかがですか？
$0$ 以上 $8$ 未満の数値を $2$ 進数で表記したものと全く同じであることがポイントです．

$10$ 進数で与えられた $K = 5$ は $2$ 進数に変換すると，$101$ ですから，先ほど考えた答えの列の数列表現とも一致します．

今回の入出力例 $1$ が，ちょうど $2$ 進数を用いて考えることができたのは，$d[H_1] = d[H_2] = d[H_3] = 2$ であったからです．

この考え方はより一般化することができ，あらゆる入力に対する答えの数列表現は「$i$ 桁目に，$0$ 以上 $d[H_i]$ 未満の $d[H_i]$ 種類の数字を用いることができるような数値表現で，$K$ の値を表したときの各桁の値」に対応するといえます．

これは，$10$ 進表現から他の基数による表現へ変換する際と同じ要領で簡単に実装することが可能です．

$Ⅲ.$ 時間計算量

いずれの解法でも，各 $1 \leq i \leq M$ について先頭が $H_i$ であるような $S$ の(昇順に並び替えられた)一覧が必要です．

これは事前に一度 $S$ をソートすればよいので，全体を通しての時間計算量は $O(N \log N + M)$ となります．

$Ⅲ.$ 発展

$1)$ 類題

• ABC 271 $\hspace{0.15em}$ A - 484558
• ABC 169 $\hspace{0.15em}$ B - Multiplication 2
• ABC 156 $\hspace{0.15em}$ B - Digits
• ABC 234 $\hspace{0.15em}$ C - Happy New Year!
• Typical90 $\hspace{0.15em}$ 067 - Base 8 to 9（★2）
• MojaCoder $\hspace{0.15em}$ aab aba baa (Hard version) $\hspace{0.15em}$ [Written by: @RedSpica]

実装例

$\\$

余談

実装問題でごめんなさい...