题意
给定一个满足 \(A_i=i\) 的排列 \(A\)，求对其进行一次 \(\mathrm{shuffle}(1,N)\) 操作后其第 \(K\) 项的值。其中 \(\mathrm{shuffle}(L,R)\) 的定义如下：
- 若 \(R = L + 1\)，那么交换 \(A_L\) 和 \(A_R\) 的值
- 否则，依次执行 \(\mathrm{shuffle}(L,R-1)\), \(\mathrm{shuffle}(L+1,R)\)
（\(1 \le T \le 1000, 1 \le K \le N \le 10^{18}\)）。
题解
通过计算出 \(N\) 较小时的情况我们可以发现若 \(N\) 为偶数，对于一对下标，在执行操作 \(\mathrm{shuffle}(1,n)\) 操作后，有 \(2i - 1, 2i\)，有 \(A_{2i - 1} = 2i - 1, A_{2i} = 2i\) 或 \(A_{2i - 1} = 2i, A_{2i} = 2i - 1\) 成立。换句话说，就是在 \(N\) 为偶数时，只会交换一些相邻且互不相交的数对。
考虑使用归纳法证明，设 \(N = 2K\)，当 \(K = 1\) 时命题成立，对于 \(K > 1\) 的情况，可以发现会依次执行如下操作：
- \(\mathrm{shuffle}(1,2K-2)\)
- \(\mathrm{shuffle}(2,2K-1)\)
- \(\mathrm{shuffle}(2,2K-1)\)
- \(\mathrm{shuffle}(3,2K)\)
可以发现中间两次 \(\mathrm{shuffle}(2,2K-1)\) 操作相互抵消，所以只会剩下两个操作区间长度为 \(N - 2\) 的子操作，故命题成立。
因此在 \(N = 2K\) 的情况下，只要计算出数对 \(2i - 1, 2i\) 被操作的次数即可计算出对应位置的值。可以发现在初始时区间长度为 \(2K\)，至最后会缩减至 \(2\)，每次缩减有两种方案：右移左边界和左移右边界，那么从 \(N = 2K\) 缩减至数对 \(2i - 1, 2i\) 共需要缩减 \(K - 1\) 次，只有恰好缩减 \(i - 1\) 次右边界才能使得最终操作的数对为 \(2i - 1, 2i\)，可以计算出方案数为 \(\dbinom{K - 1}{i - 1}\)。由于交换只有两种状态，那么我们只需要计算出 \(\dbinom{K - 1}{i - 1} \bmod 2\) 即可。使用卢卡斯定理直接计算即可在 \(\mathcal{O}(\log N)\) 的时间内完成计算。但是存在如下结论：
其中 \(\operatorname{AND}\) 表示按位与操作。
证明可以考虑卢卡斯定理的过程，设二进制下 \(n\) 的每一位依次为 \(a_i\)，\(m\) 的每一位依次为 \(b_i\)，那么有
那么 \(\dbinom{n}{m} \equiv 1 \bmod 2\) 的充要条件即为 \(\forall i, \dbinom{a_i}{b_i} = 1\)，即 \(a_i \operatorname{AND} b_i = b_i\)，即 \(n \operatorname{AND} m = m\)。
因此我们可以快速计算 \(\dbinom{K - 1}{i - 1} \bmod 2\) 的值，若 \(N\) 为奇数那么分别计算两次区间长度为偶数的情况即可。
Code
#include <bits/stdc++.h>
typedef long long valueType;
valueType query(valueType N, valueType K) {
if (((N / 2 - 1) & ((K + 1) / 2 - 1)) == ((K + 1) / 2 - 1))
return (K & 1) ? K + 1 : K - 1;
else
return K;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType T;
std::cin >> T;
for (int testcase = 0; testcase < T; ++testcase) {
valueType N, K;
std::cin >> N >> K;
if (N & 1)
std::cout << query(N - 1, query(N - 1, K - 1) + 1) << std::endl;
else
std::cout << query(N, K) << std::endl;
}
return 0;
}