造字程式 (APCS 2023-01 中級)

給定一個長度為 \(K\)、只包含小寫英文字母的字串 \(S\)。造字程式會依照一個 \(1\) 到 \(K\) 的排列 \(P_1,P_2,\ldots,P_K\)，重新排列字串中的字元。

一次操作中，舊字串第 \(i\) 個位置的字元會被複製到新字串第 \(P_i\) 個位置。也就是：

因為 \(P\) 是 \(1\) 到 \(K\) 的排列，所以新字串的每個位置恰好會收到一個字元。操作完成後，新字串會成為下一次操作的舊字串。

下圖以 abac 和排列 \((4,1,3,2)\) 示意位置的搬移。舊字串的第 \(1,2,3,4\) 個字元分別移到新字串的第 \(4,1,3,2\) 個位置，因此得到 bcaa。

程式會依序執行 \(Q\) 次操作，每次都有一個新的排列。給定整數 \(R\)，請對新字串的前 \(R\) 個位置分別輸出一行：第 \(j\) 行由第 \(1\) 次到第 \(Q\) 次操作後，新字串第 \(j\) 個位置的字元依序串接而成。

輸入格式

第一行包含三個整數 \(K,Q,R\)。

第二行包含一個長度為 \(K\) 的小寫英文字串 \(S\)。

接下來 \(Q\) 行，每行包含 \(K\) 個整數 \(P_1,P_2,\ldots,P_K\)，表示該次操作使用的排列。

限制

• \(1\le R\le K\le 20\)
• \(1\le Q\le 20\)
• \(S\) 只包含小寫英文字母。
• 每次操作的 \(P_1,P_2,\ldots,P_K\) 都是 \(1\) 到 \(K\) 的排列。

輸出格式

輸出 \(R\) 行。

第 \(j\) 行包含一個長度為 \(Q\) 的字串，依序表示每次操作完成後，新字串第 \(j\) 個位置的字元。

評分說明

本題共有兩個子題：

範例輸入 1

5 4 1
abcde
2 1 3 5 4
5 1 2 4 3
4 1 2 3 5
3 1 4 5 2

範例輸出 1

bacd

範例解釋 1

四次操作後的字串依序為 baced、acdeb、cdeab、dbcea。因為 \(R=1\)，只需記錄每次操作後的第 \(1\) 個字元，依序得到 b、a、c、d，所以輸出 bacd。

範例輸入 2

4 3 4
abac
4 1 3 2
1 2 3 4
2 3 4 1

範例輸出 2

bba
ccb
aac
aaa

範例解釋 2

三次操作後的字串依序為 bcaa、bcaa、abca。由上到下逐一查看四個位置在三次操作後的字元，就得到四行輸出 bba、ccb、aac、aaa。

題目來源

2023 年 1 月 APCS 程式實作第 2 題：ZeroJudge j606「造字程式」。題目整理與範例說明另參考王一哲的 HackMD 題解。