问题描述

你是一家计算机取证公司的负责人，刚刚收到了一位新客户寄来的以下笔记：

我，阿尔伯特·查尔斯·蒙哥马利，刚刚发现了一种令人惊叹的消息加密密码。让我来告诉你关于它的信息。

首先，你需要决定一组符号，称之为集合 S，例如包含字母 RATE。集合 S 的大小必须是 2 的幂次方，并且 S 中符号的顺序很重要。例如，R 位于位置 0，A 位于位置 1，T 位于位置 2，E 位于位置 3。你还需要一个排列 P，它是 S 中所有符号的一个排列，例如 TEAR。最后，你需要一个整数 x。这些共同构成了密钥。给定一个密钥，你现在就可以将一个长度为 n 的明文消息 M（M[0], M[1]... M[n-1]）转换为同样长度为 n 的密文 C（C[0], C[1],...C[n-1]）。明文和密文都可能只包含 S 中的部分符号。

加密算法计算 C 的步骤如下：

1. 计算整数 d，它是 (n^1.5 + x) 的整数部分除以 n 的余数。可以简洁地表示为 d = (int)(n^1.5 + x) % n，其中 "%" 是取余运算符。
2. 设置 C[d] 为 S 中位置与 M[d] 在 P 中的位置相同的符号。
3. 对于每个 j ≠ d（0 ≤ j ≤ n-1），设置 C[j] 为 S 中位置等于 M[j] 在 P 中的位置与 M[(j+1) % n] 在 S 中的位置进行异或运算后的值的符号。注意，在 C、C++ 和 Java 中，位异或运算符是 "^"。

例如，考虑以下场景：S=RATE，P=TEAR，x=102，M=TEETER，n=6。首先计算 d：

• 6^1.5 + 102 ≈ 116.696938，然后取除以 6 的余数，所以 d = 116 % 6 = 2。

以下是填充密文 C 的步骤表。注意，步骤的顺序并不重要。

• C[0] = S[0 ^ 3] = S[3] （因为 M[0] 是 T，T 在 P 中的位置是 0；M[1] 是 E，E 在 S 中的位置是 3）
• C[1] = S[1 ^ 3] = S[2] （因为 M[1] 是 E，E 在 P 中的位置是 1；M[2] 是 E，E 在 S 中的位置是 3）
• C[2] = S[1] （因为 2 是 d，M[2] 是 E，E 在 P 中的位置是 1）
• C[3] = S[0 ^ 3] = S[3] （因为 M[3] 是 T，T 在 P 中的位置是 0；M[4] 是 E，E 在 S 中的位置是 3）
• C[4] = S[1 ^ 0] = S[1] （因为 M[4] 是 E，E 在 P 中的位置是 1；M[5] 是 R，R 在 S 中的位置是 0）
• C[5] = S[3 ^ 2] = S[1] （因为 M[5] 是 R，R 在 P 中的位置是 3；M[0] 是 T，T 在 S 中的位置是 2）

最终密文 C 为 "ETAEAA"。

在笔记的末尾，我提供了几个加密消息的例子供你实验。然而，下一页关于解密算法的内容完全无法阅读，因为上面布满了巨大的、重叠的、凌乱的墨渍。鉴于你在解谜方面的出色能力，你的任务是根据你对加密算法的了解，编写解密程序。

输入

解密程序的输入由一个或多个 {密钥, 加密消息} 对组成。密钥由三行组成：

1. 第一行包含一个整数 x，0 < x < 10,000。
2. 第二行包含字符串 S。
3. 第三行包含字符串 P，它是 S 的一个排列。

S（以及 P）的长度总是以下 2 的幂次方之一：2, 4, 8, 16, 或 32。密钥之后是一行包含加密消息字符串 C，其长度至少为 1，最多为 60 个字符。字符串 S、P 和 C 不包含空白字符，但可能包含除字母和数字之外的可打印字符。输入的结束是一行只包含整数 0。

输出

对于每个输入集，打印解密后的字符串，如示例输出所示。

示例输入

102
RATE
TEAR
ETAEAA
32
ABCDEFGHIJKLMNOPQRSTUVWXYZ._!?,;
;ABCDEFGHIJKLMNOPQRSTUVWXYZ._!?,
MOMCUKZ,ZPD
1956
ACEHINT_
ACTN_IHE
CIANCTNAAIECIA_TAI
0

示例输出

TEETER
HELLO_WORLD
THE_CAT_IN_THE_HAT

来源

Mid-Central USA 2004