题目分析

这是一个基于数学和位运算的模拟题。方伯伯用 $m$ 个牌堆进行游戏，每个牌堆的大小是 $2^{n_i}$，通过洗牌、区间操作等步骤计算出一个结果 $\text{ans}_i$，并作为下一个牌堆的输入参数。

关键观察

1. 洗牌操作的数学本质

题目中的洗牌操作（取奇数位放前面）实际上等价于二进制位的置换：

• 对于位置 $k$（0-based），洗牌一次后的新位置是：将 $k$ 的二进制表示循环右移一位
• 洗 $x$ 次牌相当于循环右移 $x$ 位

2. 异或前缀和的性质

代码中的 f(n) 函数高效计算了 $1 \oplus 2 \oplus \cdots \oplus n$，利用了异或的周期性：

• $n \bmod 4 = 0$：结果为 $n$
• $n \bmod 4 = 1$：结果为 $1$
• $n \bmod 4 = 2$：结果为 $n+1$
• $n \bmod 4 = 3$：结果为 $0$

3. 核心函数解析

qry(n, X, R, T) 函数

这个函数计算洗牌 $X$ 次后，前 $R$ 张牌加上 $T$ 后的异或和：

• 将区间按 $2^{n-X}$ 大小分块
• 分别处理高位（块索引）和低位（块内偏移）
• 利用异或前缀和的性质高效计算

Calc(n, X, L, R, T) 函数

计算区间 $[L, R]$ 的异或和：

• 通过前缀异或和相减得到区间结果
• 取模 $2^{n-1}$ 作为最终答案

算法流程

1. 初始化：读入 $m$ 和第一个牌堆的参数
2. 处理每个牌堆：
   • 计算当前牌堆大小 $n_i = (\text{ans}_{i-1} + i - 1) \bmod 5 + \text{base}$
   • 计算关注的区间 $[l_i, r_i]$
   • 计算洗牌次数 $x_i$ 和加数 $t_i$
   • 调用 Calc 计算当前牌堆的答案
3. 输出：最后一个牌堆的答案 $\text{ans}_{m-1}$

代码实现

#include <bits/stdc++.h>
#define ci const long long
#define int long long
using namespace std;

int f(ci n) {
    if (n < 0)
        return 0;

    if (n % 4 == 0)
        return n;

    if (n % 4 == 1)
        return 1;

    if (n % 4 == 2)
        return n + 1;

    return 0;
}

int qry(ci n, ci X, int R, int T) {
    if (X == n)
        return f(R + T - 1) ^ f(T - 1);

    int p = R / (1ll << (n - X));  
    R %= 1ll << (n - X);           
    int g = (T + p) & ((1ll << X) - 1);
    T = (T + p) >> X;
    return ((f(R + T - 1) ^ f(T - 1)) << X) ^ ((R & 1) ? g : 0);
}

int Calc(ci n, int X, ci L, ci R, int T) {
    T++, X %= n;

    if (!X)
        X = n;

    int ans = qry(n, X, R, T);

    if (L > 1)
        ans ^= qry(n, X, L - 1, T);

    return ans & ((1ll << (n - 1)) - 1);
}

signed main() {
    int m, N, X, L, R, T, B;
    cin >> m >> N >> X >> L >> R >> T >> B;
    int las = Calc(N, X, L, R, T);

    for (int i = 1; i < m; ++i) {
        int n = (las + i - 1) % 5 + B, len = 1ll << n, tt = 1ll << (n / 2);
        int l = (2 * las + L + i - 1) % len + 1;
        int r = (las + 1 + l % tt * tt) % len + 1;

        if (l > r)
            swap(l, r);

        int x = (r - l + T + i - 1) % len;
        int t = (l + r) % len;
        las = Calc(n, x, l, r, t);
        N = n, X = x, L = l, R = r, T = t;
    }

    cout << las;
    return 0;
}

复杂度分析

• 时间复杂度：$O(m \cdot n)$，其中 $n \leq 60$，$m \leq 5 \times 10^6$
• 空间复杂度：$O(1)$，只使用常数个变量