P12465题解

FormulaOne · 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;
}