abc_356 Masked Popcount

#include<bitsstdc++.h>
#define ll long long
#define N 100005
#define mod 998244353
using namespace std;
ll sum_b[N], sum_p[N], p[N], a[N], sum;
void f(ll y){
    ll x = y, t = 1, s = 1;
    while(x){
        if(x%2 == 1) a[t] = 1;
        x /= 2;
        p[t] = s;
        // cout<<"t,p: "<<t<<" "<<p[t]<<endl;
        s = s * 2;
        t++;
    }
    t--;
    sum_b[0] = 1;
    for(int i = 1; i <= t; i++){
        if(a[i] == 1){
            (sum_b[i] = sum_b[i-1] + p[i]) %= mod;
        } 
        else{
            (sum_b[i] = sum_b[i-1] + 0) %= mod;
        }    
        // cout<<"bbb: "<<i<<" "<<sum_b[i]<<endl;
    }
    // cout<<endl;
    for(int i = t; i >= 1; i--){
        if(a[i] == 1)
            (sum_p[i] = sum_p[i+1] + p[i]/2)  %= mod;
        else   
            (sum_p[i] = sum_p[i+1] + 0)  %= mod;
        // cout<<"ppp: "<<i<<" "<<sum_p[i]<<endl;
    }
}
ll n,m;
int main(){
    cin>>n>>m;
    f(n);
    ll k = m, t = 1; 
    while(k){
        if(k%2 == 1){
            // cout<<"t:"<<t<<endl;
            if(a[t] == 0){
                (sum += sum_p[t+1]) %= mod; //前缀和，减1(自己的占位)
            }
            else if(a[t] == 1){ 
                (sum += sum_p[t+1]) %= mod;//前缀和，减1(自己的占位)
                (sum += sum_b[t-1]) %= mod; //后缀和，不减1
                // cout<<sum_p[t+1]<<" "<<sum_b[t-1]<<endl;
            }
        }
        k /= 2;
        t++;
    }
    cout<<sum<<endl;
    return 0;
}
/*
 10010
   110
18 6

  10010
    101
18 5
8+8+1

//一旦a当前为1,则有后缀和，后缀和一定是包含a数字本身的
//一旦a当前为0,则无后缀和，后缀和一定是不包含a数字本身的


8+8+1=17
 10110
   100
22 4
8+2+1


20 4
8+1 = 9
10100
  100


100010110
 01011000

 
*/