题解：P12595 出生于驾校

CleverSea · 2025-07-09 08:24:55 · 题解

首先，艾弗森括号是什么？

在数学中，以肯尼斯·艾佛森命名的“艾佛森括号”，是一种用方括号记号，如果方括号内的条件满足则为 1，不满足则为 0。

——摘自百度百科

即 [P] = \begin{cases} 1 & P \text{ 为真}, \\ 0 & P \text{ 为假}. \end{cases}

题意简述

实现对数列进行 3 种操作：全局加法、全局乘法和模意义下的区间求和。

分析

观察数据范围得知：数列长度和操作次数均可达 4 \times 10^7，因此需要肥肠高效的处理方法。

思路

我们可以通过维护全局乘法标记 mul 和加法标记 add，将全局操作转化为线性变换。每次加法或乘法操作时只需更新这两个标记，避免实际遍历数列。同时将数列下标按模 2^k 的余数分组，预处理每组元素的和与个数。利用高维前缀和快速计算任意 k 和 p 对应的分组和。对于查询操作，利用预处理的分组和与全局标记，即可 O(1) 计算当前分组和。

所以，大致步骤是这样的：

• 使用给定的随机数生成器生成初始数列和操作序列（这种题还真是第一次见，是我孤陋寡闻了）。

• 将数列下标按模 2^{26} 分组，计算每组元素的和（f 数组）和个数（cnt_base 数组）。

• 对每个 k \in [minK, maxK]，预处理模 2^k 的分组和（g_levels）和元素个数（cnt_levels）：

  • 最大层（k = maxK）直接计算每组和。
  • 其他层则从上一层聚合结果（分组和可加性）。

• 操作处理：

  • 全局加法：更新加法标记 add = (add + x) % mod。
  • 全局乘法：更新乘法标记 mul = mul * x % mod 和加法标记 add = add * x % mod。
  • 查询：利用预处理结果，计算当前分组和： sum = (group\_sum \times mul + group\_count \times add) \bmod 998244353

    并累加到异或结果，最后输出。

（为了方便看代码，数组、变量等名称我特地取得很长但通俗易懂。）

Code

#include <iostream>
#include <vector>
#include <cstdint>
using namespace std;

const int mod = 998244353;
const int MAX_K = 26;
const uint64_t M = 1ULL << MAX_K;  // 2^26

uint32_t X, Y, Z;

// 生成下一个随机数
uint32_t nextInt() {
    X ^= Y << (Z & 31);
    Y ^= Z >> (X & 31);
    Z ^= X << (Y & 31);
    X ^= X >> 5;
    Y ^= Y << 17;
    Z ^= Z >> 6;
    return X;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q, minK, maxK;
    cin >> n >> q >> minK >> maxK;
    cin >> X >> Y >> Z;
    // 生成初始数列 a
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        a[i] = nextInt() % mod;
    }
    // 初始化基础分组：f 存储和，cnt_base 存储元素个数
    vector<int> f(M, 0);
    vector<int> cnt_base(M, 0);
    for (int i = 0; i < n; ++i) {
        f[i] = a[i];
        cnt_base[i] = 1;
    }
    // 提前释放 a 的内存
    a.clear();
    a.shrink_to_fit();
    // 分层存储：g_levels[k] 存储模 2^k 的分组和，cnt_levels[k] 存储元素个数
    int num_levels = maxK - minK + 1;
    vector<vector<int>> g_levels(num_levels);
    vector<vector<int>> cnt_levels(num_levels);
    if (num_levels > 0) {
        int idx_max = maxK - minK;
        int size_max = 1 << maxK;
        g_levels[idx_max] = vector<int>(size_max, 0);
        cnt_levels[idx_max] = vector<int>(size_max, 0);
        // 临时数组（long long 防溢出）
        vector<long long> g_temp(size_max, 0);
        vector<long long> cnt_temp(size_max, 0);
        // 计算最大层（k = maxK）
        uint32_t mask = (1U << maxK) - 1;
        for (uint32_t i = 0; i < M; ++i) {
            uint32_t p = i & mask;
            g_temp[p] += f[i];
            cnt_temp[p] += cnt_base[i];
        }
        // 转换到 int 并取模
        for (int p = 0; p < size_max; ++p) {
            g_levels[idx_max][p] = g_temp[p] % mod;
            cnt_levels[idx_max][p] = static_cast<int>(cnt_temp[p]);  // 计数不取模
        }
        // 释放临时数组
        g_temp.clear();
        g_temp.shrink_to_fit();
        cnt_temp.clear();
        cnt_temp.shrink_to_fit();
        // 从大到小聚合到更低的 k
        for (int k = maxK - 1; k >= minK; --k) {
            int idx_cur = k - minK;
            int idx_next = (k + 1) - minK;
            int size_cur = 1 << k;
            g_levels[idx_cur] = vector<int>(size_cur, 0);
            cnt_levels[idx_cur] = vector<int>(size_cur, 0);
            // 从下一层聚合
            for (int p = 0; p < size_cur; ++p) {
                g_levels[idx_cur][p] = (g_levels[idx_next][p] + g_levels[idx_next][p + size_cur]) % mod;
                cnt_levels[idx_cur][p] = cnt_levels[idx_next][p] + cnt_levels[idx_next][p + size_cur];
            }
        }
    }
    // 释放基础数组
    f.clear();
    f.shrink_to_fit();
    cnt_base.clear();
    cnt_base.shrink_to_fit();
    // 全局标记
    int add = 0, mul = 1;
    long long ans_xor = 0;
    // 处理操作
    for (int i = 0; i < q; ++i) {
        int op = nextInt() % 3 + 1;
        if (op == 1) {  // 全局加法
            int x = nextInt() % mod;
            add = (add + x) % mod;
        } else if (op == 2) {  // 全局乘法
            int x = nextInt() % mod;
            mul = 1LL * mul * x % mod;
            add = 1LL * add * x % mod;
        } else if (op == 3) {  // 查询
            int k = nextInt() % (maxK - minK + 1) + minK;
            int p = nextInt() % (1 << k);
            int idx = k - minK;
            long long group_sum = g_levels[idx][p];
            long long group_count = cnt_levels[idx][p];
            long long value = (group_sum * mul + group_count * add) % mod;
            ans_xor ^= value;
        }
    }
    cout << ans_xor << endl;
    return 0;
}

其中预处理时间复杂度为 O(2^{maxK + 1})，操作处理 O(q)。

由于此题猎奇的空间限制（2 GB）和猎奇的做法，我们也来讨论一下空间复杂度：其主要消耗在分层预处理，总空间 O(2^{maxK + 1})，在 maxK = 26 时约 1.5 GB，满足题目 2 GB 的空间限制。

预估占用空间的详细计算方法（可以不看）：

当 maxK = 26 时，预处理的分组存储空间主要来源于两个数组：

• 存储模 2^{26} 的分组和（f）和元素个数（cnt_base），每组大小为 2^{26}，每个元素为 int 类型（占 4 字节），则总空间为：

  2 \times 2^{26} \times 4 \text{字节} = 2^{28} \text{字节} = 512 \text{MB}

• 存储从 minK 到 maxK 所有层的分组和（g_levels）和元素个数（cnt_levels），每层 k 的分组数为 2^k，总空间为

  \sum_{k=\text{minK}}^{\text{maxK}} 2^{k+1} \times 4 \text{字节}

  当 minK=0 且 maxK=26 时，总空间为：

  \sum_{k=0}^{26} 2^{k+1} \times 4 \text{字节} = 8 \times (2^{27} - 1) \text{字节} \approx 1 \text{GB}

故总共约 512 \text{MB} + 1 \text{GB} = 1.5 \text{GB}。