Codeforces 515(Div. 3) E （1066E）二进制求前缀和&&与运算

 题意：

现在，给你两个位数为 nn 和 mm 的两个二进制数aa,bb，现在，我们要进行如下操作：

• 计算aa&bb
• 答案累加上一个操作的值
• bb右移一位，最后一位直接舍弃

现在,请你算出最终的答案，并输出，答案对998244353取模

这题的关键是这个前缀和，因为暴力是1-2e5的和肯定超时，想想如果仅仅是a，b求&怎么运算？肯定是跑一遍n。

算每次b右移的串利用的b高位的1在右移中一定会和a中比它位低的所有1与成1，所以就可以用前缀和计算这个位前面有多少个1，就知道这个a这个位产生了过多少次非零数，加和起来就是总数了。

#include<iostream>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll pow2[200010],bit[200010];
int main(){
	int n,m;
	string a,b;
	cin>>n>>m;
	cin>>a>>b;
	if(n<=m){
		a=string(m-n,'0')+a;
	}
	else{
		b=string(n-m,'0')+b;
	}
	n=max(n,m);
	pow2[0]=1;
	for(int i=1;i<2e5+10;i++){
		pow2[i]=pow2[i-1]*2%mod;
	}
	bit[0]=(b[0]=='1');
	for(int i=1;i<n;i++){
		bit[i]=bit[i-1]+(b[i]=='1');
	}
	ll sum=0;
	for(int i=0;i<n;i++){
		ll ans=(a[i]=='1');
		ans=ans*pow2[n-i-1]%mod;
		sum+=ans*bit[i]%mod;
		sum%=mod;
	}
	cout<<sum<<endl;
}