自动搬运

查看原文

来自洛谷，原作者为

	lilong AFOed on 2025/4/29 || 互关喵qwq

搬运于2025-08-24 23:15:46，当前版本为作者最后更新于2025-05-10 22:02:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

应该是最好想的做法了。

注意到对于任意非负整数 $k$，$2k$ 和 $2k+1$ 两个数的二进制下 $1$ 的出现次数必定一奇一偶，即贡献和为 $1$。为什么？因为一个偶数的二进制最后一位一定是 $0$，比它大 $1$ 的奇数一定是最后一位变成 $1$（一定不会进位），故 $1$ 的个数刚好相差一，得证。于是这道题就变为判断原题中的 $\text{Sub}(l,r)$ 的奇偶性并分类讨论即可。

时间复杂度 $O(n+q)$，代码中有注释。

#include<iostream>
#include<cstdio>
#define int long long
#define N 500010
#define mod 998244353
#define inv2 (mod+1)/2
using namespace std;
string s;
int n,q,p2[N],a[N],s1[N],s2[N];
int gt(int l,int r){//返回原题中的 Sub(l,r)
    if(l>r)return 0;
    return ((s1[r]-s1[l-1]*p2[r-l+1])%mod+mod)%mod;
}
int pd(int l,int r){//原题中的 Pari 的作用
    return (s2[r]-s2[l-1])%2;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int l,r;
    cin>>n>>q;
    cin>>s;
    p2[0]=1;
    for(int i=1;i<=n;i++)//预处理 2 的幂
        a[i]=s[i-1]-'0',p2[i]=p2[i-1]*2%mod;
    for(int i=1;i<=n;i++){
        s1[i]=(s1[i-1]*2%mod+a[i])%mod;//前 i 个位置构成的二进制数转为十进制数
        s2[i]=s2[i-1]+a[i];//前 i 个位置 1 的个数
    }
    while(q--){
        cin>>l>>r;
        if(a[r])
            cout<<(gt(l,r-1)+1)%mod<<'\n';//除以 2 相当于去掉二进制下最后一位，这里要上取整，故要加上 1
        else
            cout<<(gt(l,r-1)+pd(l,r))%mod<<'\n';//由于多出最后一个偶数，需要另外判断
    }
    return 0;
}