CF1066E Binary Numbers AND Sum 题解

分析

因为 \(a\) 是一直没有改变的，移动的只有 \(b\)，所以从 \(a\) 的每一位的贡献入手。

对于 \(a\) 中的从低到高第 \(i\) 位，其对应的十进制值是 \(a_{n-i+1}\times 2^{i-1}\)。注意到 \(b\) 是每次右移一位的，所以在 \(b\) 中能与 \(a_{n-i+1}\) 匹配的都是在下标区间 \([1,m-i+1]\)。根据 \(1\&1=1,1\&0=0,0\&0=0\) 的性质，能够得到从低到高第 \(i\) 位的贡献是：\(a_{n-i+1}\times 2^{i-1}\times cnt_{m-i+1}\)。其中 \(cnt_i\) 表示 \(b\) 中前 \(i\) 位 \(1\) 的数量。

注：\(b\) 与 \(a\) 的长度可能不一样，注意下标问题。

这题比 CF1881A 简单。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline

const int p=998244353;
string a,b;int n,m;
int cnt,ans,nw=1;

il void solve(){
	cin>>n>>m>>a>>b;
	for(re int i=0;i<m;++i) cnt+=(b[i]-'0');
	for(re int i=n-1,j=m-1;i>=0&&j>=0;--i,--j) 
		ans=(ans+(a[i]-'0')*nw*cnt)%p,
		nw=nw*2%p,cnt-=(b[j]-'0');
	cout<<ans;return ;
}

signed main(){
	solve();
	return 0;
}