[AGC061A] Long Shuffle 题解

标签：std Shuffle dbinom 题解 AGC061A shuffle 2K 2i mathrm

题意

给定一个满足 \(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)\) 的时间内完成计算。但是存在如下结论：

\[\dbinom{n}{m} \equiv 1 \bmod 2 \Leftrightarrow n \operatorname{AND} m = m \]

其中 \(\operatorname{AND}\) 表示按位与操作。

证明可以考虑卢卡斯定理的过程，设二进制下 \(n\) 的每一位依次为 \(a_i\)，\(m\) 的每一位依次为 \(b_i\)，那么有

\[\dbinom{n}{m}\bmod 2 = \prod\limits_{i}\dbinom{a_i}{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;
}

标签：std,Shuffle,dbinom,题解,AGC061A,shuffle,2K,2i,mathrm
From： https://www.cnblogs.com/User-Unauthorized/p/solution-AGC061A.html