纸牌洗牌难题：推导位置映射公式与实现 k 次洗牌后牌位查询

洗牌操作将牌堆分成两半，交叉合并。 n 张牌初始排列为 1, 2, …, n。 一次洗牌后，位置 x 上的牌会移动到新位置 f(x)。 推导映射公式： 设牌在洗牌前的位置为 x（1 ≤ x ≤ n）。 n 是偶数，令 m = n / 2。 洗牌过程： 前一半牌 a₁, a₂, …, aₘ 对应原位置 1, 2, …, m。 后一半牌 aₘ₊₁, aₘ₊₂, …, aₙ 对应原位置 m+1, m+2, …, n。 交叉合并后，新序列为： 原位置 1, m+1, 2, m+2, …, m, n。 观察位置映射： - 原位置 x（1 ≤ x ≤ m）在新序列中排在第 2x - 1 个位置。 - 原位置 x（m+1 ≤ x ≤ n）在新序列中排在第 2(x - m) 个位置。 因此： f(x) = 2x - 1，当 1 ≤ x ≤ m。 f(x) = 2(x - m)，当 m+1 ≤ x ≤ n。 等价形式（便于计算）： f(x) = (2x) mod (n+1)，当 1 ≤ x ≤ n-1 且 n 为偶数时，注意 n+1 是奇数。 验证： x ≤ m 时，2x ≤ n，2x mod (n+1) = 2x，但我们需要 2x-1，所以不对。 直接使用分段公式即可。 洗牌 k 次后，初始位置 i 的牌移动到了哪个位置？ 题目要求输出洗牌 k 次后第 i 张牌的编号，即初始编号为多少的牌移动到了位置 i。 设初始编号 = 位置编号，初始时位置 p 上是牌 p。 洗牌一次，位置 p 上的牌移动到 f(p)。 洗牌 k 次，位置 p 上的牌移动到 f^k(p)。 我们要求的是：洗牌 k 次后，位置 i 上的牌的初始编号，即求 g = f^{-k}(i)。 因此需要求 f 的逆映射。 由 f： 如果 f(x) = y，那么： 情况 1：y 是奇数，y = 2x - 1 ⇒ x = (y+1)/2。 情况 2：y 是偶数，y = 2(x - m) ⇒ x = y/2 + m。 所以逆映射： h(y) = (y+1)/2，当 y 是奇数。 h(y) = y/2 + m，当 y 是偶数。 洗牌 k 次后位置 i 上的牌初始编号 = h^k(i)。 n, k 最大 1e5，直接模拟 k 次逆映射即可，O(k) 时间。 样例 n=6, k=2, i=5： m = 3。 第一次逆映射：i=5 奇数 ⇒ h=3。 第二次逆映射：i=3 奇数 ⇒ h=2。 输出 2，符合样例。 代码实现： ```python n, k, i = map(int, input().split()) m = n // 2 pos = i for _ in range(k): if pos % 2 == 1: pos = (pos + 1) // 2 else: pos = pos // 2 + m print(pos) ``` ######[AI问答 | 810点数解答 | 2026-01-06 17:43:32]