1066E - Binary Numbers AND Sum - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define ff first
#define ss second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define ins insert
#define endl "\n"
#define deb(x) cout<<(x)<<endl
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x<<" "<<x<<endl

const int INF=1e9;
const int MOD=998244353;
const int MAXN=1e5+5;


int power(int x, int y, int p)
{
 
    int res = 1;

	x = x % p;
 
	if(x == 0) return 0;
 
    while (y > 0) {
 
        if (y&1)
            res = (res * x) % p;
 
        y = y >> 1;

        x = (x * x) % p;
    }
    return res % p;
}



int tt=1,n,m;
string s1,s2;
void solve(){
	cin>>n>>m;
	cin>>s1>>s2;
	
	reverse(all(s1));
	reverse(all(s2));
	
	
	int pref[n];
	
	for(int i=0;i<n;i++) {
		if(s1[i] == '1') {
			
			if(i == 0) {
				pref[i] = power(2,i,MOD);
			} else {
				pref[i] = (pref[i-1] + power(2,i,MOD) ) % MOD;
			}
			
		}else {
			if(i == 0) pref[i] = 0;
			else pref[i] = pref[i-1];
		}
	}
	
	
	int ans = 0;
	
	
	for(int i=0;i<m;i++) {
		
		
		if(s2[i] == '1') ans = (ans + pref[min(n-1,i)]) % MOD;
		
	} deb(ans % MOD);

	
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
   // cin>>tt;
    while(tt--){
        solve();
    }
}