[AHOI2005] 洗牌题解

思路

观察一张原来位于第 $i$ 个位置的牌。若它在上半叠，洗牌后位于第 $2i$ 个位置；若它在下半叠，洗牌后位于第 $2i-N-1$ 个位置。两种情况可以统一写成

所有实际位置都在 $1$ 到 $N$ 之间，因此不会出现模意义下的零。洗牌 $M$ 次后，原位置 $i$ 会到达

题目给出的是最终位置 $L$，要求原来的牌号，所以需要乘上 $2^M$ 的逆元。由于 $N$ 为偶数，$N+1$ 为奇数，$2$ 一定可逆，而且

于是答案为

做法

使用二进制快速幂计算 $((N+2)/2)^M\bmod(N+1)$，再乘以 $L$ 并取模。乘法的两个因子都可能接近 $10^{10}$，中间结果使用 128 位整数。

第一档可以每次根据当前位置的奇偶性逆推一次洗牌前的位置，共执行 $M$ 次。第二档把逆位置映射看作一个置换，从 $L$ 出发找到所在环的长度，将 $M$ 对环长取模后再沿环移动；由于环长不超过 $N$，总操作数是线性的。满分做法不依赖 $N$ 或 $M$ 的线性大小。

正确性由位置映射直接得到：一次洗牌的正向映射等价于模 $N+1$ 乘二，连续 $M$ 次等价于乘 $2^M$。乘以其逆元恰好从最终位置恢复唯一的原位置，而初始牌号等于原位置，因此公式输出的就是所求牌号。

复杂度

满分算法的时间复杂度为 $O(\log M)$，额外空间复杂度为 $O(1)$。