题解

这道题是关于 Vigenère 密码的解密问题，我们需要根据密钥和密文还原出明文。

解题思路

Vigenère 密码的加密规则是：

其中 $m_i$ 是明文字符对应的数字（$0$–$25$），$k_i$ 是密钥字符对应的数字，$c_i$ 是密文字符对应的数字。

那么解密时，我们可以通过以下公式计算明文字符对应的数字：

再将数字转换为对应的字母即可。

代码实现技巧

在代码中，利用了字符的 ASCII 码特性来简化计算：

• 对于任意字母（不区分大小写），字符 & 31 可以将其转换为对应的大写字母的索引值：

  • 例如 'A' & 31 = 1，'a' & 31 = 1，'B' & 31 = 2，'b' & 31 = 2 等。
  • 再减去 $1$ 就得到了该字母在 $0$–$25$ 范围内的数字（即 $k_i$ 或 $c_i$）。

• 计算 $(c_i - k_i) \bmod 26$ 时，需要考虑结果为负数的情况：

  • 如果 $(C[i] \& 31) - tmp \leq 0$，则加上 $26$ 来保证结果在 $0$–$25$ 范围内。
  • 最后再转换为对应的字符，并保持原来的大小写形式。

算法流程

1. 读取密钥字符串 $K$ 和密文字符串 $C$。
2. 遍历密文字符串的每个字符：
   • 计算当前密钥字符对应的数字 $tmp = (K[i \bmod |K|] \& 31) - 1$，其中 $i \bmod |K|$ 是为了循环使用密钥。
   • 计算明文字符对应的数字：
     • 若 $(C[i] \& 31) - tmp > 0$，则明文字符为 $C[i] - tmp$；
     • 否则为 $C[i] - tmp + 26$。
3. 输出解密后的明文字符串。

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是密文的长度。
• 空间复杂度：$O(1)$（不计输入输出存储）。

这种方法通过直接操作字符的 ASCII 码，避免了显式的字母到数字的转换和再转换，效率很高，适用于题目给定的数据范围。