别样的Parity大战

· · 题解

别样的 Parity 大战

一天，仵沉蛋给我打来电话。他说：“你敢不敢和我举行 Parity 大战？”我豪爽地答应了：“我当然敢！周日下午在 xx 路 xx 大厦，给定长度为 n 的二进制字符串 S 和 q 次查询，每次查询对于 [l,r]，要计算 \sum_{x=0}^{\operatorname{Sub}(l,r)}\operatorname{Pari}(x) \bmod 998244353，谁不来谁就是怂货。”

我原本以为我恐吓了仵沉蛋，仵沉蛋应该躲在家，不敢找我，便准备用 O(N) 暴力枚举计算：

long long ans = 0;
for (int x = 0; x <= N; x++) {
    ans += __builtin_popcount(x) % 2;
}

可正当这时，我听到了音乐声，一看，竟然是我的暴力枚举 TLE 了，仵沉蛋打来电话：“小废物，不会用 \operatorname{Pari} 函数的性质？再不会你的锣鼓账号就要被我机惨了！”我回击道：“我要用 S(N)=∑(-1)^{popcount(x)} 的公式和预处理，把你 hack 掉，你说好不好啊。”

他吓得没再回应我，可是到了周日，仵沉蛋竟然又给我打电话了，他还真要和我举行 Parity 大战，于是我按照约定，到达了 xx 大厦，可他已经等我很久了。

第一回合，我占上风，利用公式 f(N)=\frac{(N+1)-S(N)}{2} 发起进攻：

long long X = (Nv + 1) % mod;
long long ans = (X - Sv) * inv2 % mod;

仵沉蛋还在手算 \operatorname{Sub}(l,r) 的值，他比不过我，到了第六回合，他就主动认输了。

第二回合，他开始占上风，我也不甘势弱，我们僵持了一百多个回合，我轻敌地只预处理了前缀和：

Fw[0] = s[0]-'0';
for(int i=1; i<n; i++) {
    Fw[i] = (Fw[i-1]*2 + (s[i]-'0')) % mod;
}

却忽略了全零子串的边界情况：

if(nxt[l0] == -1 || nxt[l0] > r0) {
    // 全0子串处理
}

被他击败了。

从那时开始，我就不轻敌了，我认真研究他的套路，于是我总结出了一种方案：

  1. 预处理 nxt 快速定位首个 1：
int last = -1;
for(int i=n-1; i>=0; i--){
    if(s[i]=='1') last = i;
    nxt[i] = last;
}

第二天，我们举行第三局，他使用祖传暴力算法，对我发动猛烈的攻击，我们势均力敌，平分秋色，2\times 10^5 的查询使我们比了 3 个多小时，也没分出胜负。

后来，他不知不觉的睡着了，我趁着这个好机会，一记凌车漂移，一飞冲天，精准的预处理和 O(1) 查询：

int pos = nxt[l0];
if(s[r0]=='1') Sv=0;
else {
    int m = Cw[r0] - (pos?Cw[pos-1]:0);
    Sv = (m%2)? -1:1;
}
long long Nv = (Fw[r0] - Fw[pos-1]*pow2t[len]) % mod;
long long ans = ((Nv+1 - Sv) * inv2 % mod + mod) % mod;

打的他不敢还手，对他的打击比取模时忘记处理负模数还大：

if(ans < 0) ans += mod;  // 致命一击

下面是正常版题解

题意简述

题目要求计算对于给定的二进制字符串的子串所表示的数字 N，求解：

\sum_{x=0}^{N} \operatorname{Pari}(x) \bmod 998244353

其中 \operatorname{Pari}(x) 是 x 的二进制表示中 1 的个数的奇偶性（即 1 的个数模 2）。

思路

我们可以将问题进行转化：定义函数 S(N) = \sum_{x=0}^{N} (-1)^{\text{popcount}(x)}，则所求答案可表示为：

f(N) = \frac{(N + 1) - S(N)}{2} \bmod 998244353

其中 N 是子串表示的二进制数。

所以，我们只需思考如何求 S(N)。考虑如下计算方式：

\begin{cases} 0 & \text{当 } a = 0 \text{ (即 } N=1\text{)} \\ -S(b) & \text{其他情况} \end{cases}

然后，为了提升算法效率，考虑如下优化：

Code

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 200000;      // 最大字符串长度
const int mod = 998244353;    // 模数
const long long inv2 = (mod + 1) / 2; // 2的逆元，用于除法

int n, q;                     // 字符串长度和查询数
char s[MAXN + 10];            // 存储输入的二进制字符串（下标0开始）
int nxt[MAXN + 10];  // nxt[i]: 从位置i开始向右的第一个'1'的位置，没有则为-1
long long Fw[MAXN + 10]; // Fw[i]: 前缀子串s[0..i]的二进制值取 mod
int Cw[MAXN + 10];       // Cw[i]: 前缀子串s[0..i]中'1'的个数
long long pow2t[MAXN + 10]; // pow2t[i]: 2^i 取 mod

int main() {
    cin >> n >> q;
    cin >> s;
    // 预处理幂表：计算2^i mod mod (0 <= i <= MAXN)
    pow2t[0] = 1;
    for (int i = 1; i <= MAXN; i++) {
        pow2t[i] = (pow2t[i - 1] * 2) % mod;
    }
    // 预处理nxt：从右向左扫描，记录每个位置开始向右的第一个'1'
    int last = -1; // 记录最近遇到的'1'的位置
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '1') {
            last = i; // 更新最近'1'的位置
        }
        nxt[i] = last; // 记录当前位置开始的第一个'1'
    }
    // 预处理前缀和数组Fw和Cw
    if (n > 0) {
        // 初始化第一个字符
        Fw[0] = s[0] - '0'; // 数值
        Cw[0] = (s[0] == '1') ? 1 : 0; // '1'的个数
        // 计算后续位置
        for (int i = 1; i < n; i++) {
            // Fw[i] = 前i-1位的值左移1位 + 当前位的值
            Fw[i] = (Fw[i - 1] * 2 + (s[i] - '0')) % mod;
            // Cw[i] = 前i-1位的'1'个数 + 当前位是否为'1'
            Cw[i] = Cw[i - 1] + ((s[i] == '1') ? 1 : 0);
        }
    }
    // 处理每个查询
    while (q--) {
        int l, r;
        cin >> l >> r;
        // 转换为0-indexed下标
        int l0 = l - 1;
        int r0 = r - 1;
        // 情况1：子串中没有'1'（全0）
        if (nxt[l0] == -1 || nxt[l0] > r0) {
            // N = 0, S(0)=1
            long long X = 1;      // X = N + 1 = 1
            long long Sv = 1;  // S(0)=1
            // f(N) = (X - Sv) / 2
            long long ans = (X - Sv) % mod;
            if (ans < 0) ans += mod; // 处理负数（仵沉蛋就是这一步忘记了！）
            ans = ans * inv2 % mod;  // 乘以逆元
            cout << ans << endl;
        } 
        // 情况2：子串中有'1'
        else {
            int pos = nxt[l0]; // 第一个'1'的位置（0-indexed）
            long long Sv; // 存储S(N)的值
            // 判断子串最后一个字符（决定N的奇偶性）
            if (s[r0] == '1') {
                // N为奇数，S(N)=0
                Sv = 0;
            } else {
                // N为偶数，计算有效子串中'1'的个数m
                int m;
                if (pos == 0) {
                    // 有效子串从0开始，直接取前缀
                    m = Cw[r0];
                } else {
                    // 有效子串从pos开始，计算Cw[r0] - Cw[pos-1]
                    m = Cw[r0] - Cw[pos - 1];
                }
                // S(N) = (-1)^m
                if (m % 2 == 0) {
                    Sv = 1;
                } else {
                    Sv = -1;
                }
            }
            // 计算有效子串表示的数值N
            long long Nv;
            int len = r0 - pos + 1; // 有效子串长度
            if (pos == 0) {
                // 有效子串从0开始，直接取前缀值
                Nv = Fw[r0];
            } else {
                // 计算：子串值 = 整个前缀值 - 前pos-1部分左移len位的值
                Nv = (Fw[r0] - Fw[pos - 1] * pow2t[len]) % mod;
                if (Nv < 0) Nv += mod; // 处理负数（仵沉蛋就是这一步忘记了！）
            }
            // 计算答案 f(N) = ((N+1) - S(N)) / 2
            long long X = (Nv + 1) % mod; // X = N+1
            long long temp = (X - Sv) % mod; // temp = (N+1) - S(N)
            if (temp < 0) temp += mod;       // 处理负数（仵沉蛋就是这一步忘记了！）
            long long ans = temp * inv2 % mod; // 乘以逆元
            cout << ans << endl;
        }
    }
    return 0;
}

其中查询时间复杂度为 O(1)，总时间复杂度 O(n + q)。