CF1066EBinary Numbers AND Sum（前缀和，二进制）
发布时间：2020-12-14 04:18:35 所属栏目：大数据 来源：网络整理
导读：题目大意 现在，给你两个位数为 n 和 m 的两个二进制数 a , b ，现在，我们要进行如下操作： 计算 a b 答案累加上一个操作的值 bb b右移一位，最后一位直接舍弃 现在,请你算出最终的答案，并输出，答案对998244353取模 输入输出格式： 输入格式： 第一行，两
题目大意现在，给你两个位数为 n 和 m 的两个二进制数a,b，现在，我们要进行如下操作：
现在,请你算出最终的答案，并输出，答案对998244353取模 输入输出格式：输入格式：第一行，两个整数n,m,(1≤n,m≤2×105) 第一行，一个长度为n的二进制数a 第一行，一个长度为m的二进制数b 输出格式：一行，一个数，表示答案 思路：因为第一个二进制数不动，第二个在动，所以我们可以通过预处理第一个数来获得答案 因为是与，所以只有两个都是1时才会有答案的贡献 那么，比如说这个例子： 1001 他就会有如下几种情况 01001 1001 1001 1001 1001 我们会发现，第一位的1分别和上面的第一个1和最后一个1异或起来对答案有贡献 所以这个1对答案的贡献是8+1=9 我们把这个规律推广开来 对y中每一个1进行如上操作 即可得出答案 但是，我们会发现答案复杂度是O（n×m）的，过不了 所以我们要预处理 用前缀和跑一遍x即可 复杂度优化到O(m+n) 代码：? #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define rii register int i #define rij register int j #define p 998244353 #define int long long using namespace std; int a,b; int x[200005],y[200005],bs[200005],qzh[200005]; void ycl() { bs[0]=1; for(rii=1;i<=200002;i++) { bs[i]=bs[i-1]*2; bs[i]%=p; } } signed main() { scanf("%lld%lldn",&a,&b); for(rii=1;i<=a;i++) { x[i]=getchar()-‘0‘; } getchar(); for(rii=1;i<=b;i++) { y[i]=getchar()-‘0‘; } ycl(); for(rii=a;i>=1;i--) { qzh[a-i+1]=qzh[a-i]; qzh[a-i+1]+=x[i]*bs[a-i]; qzh[a-i+1]%=p; } if(b>a) { for(rii=a+1;i<=b;i++) { qzh[i]=qzh[i-1]; } } // for(rii=1;i<=b;i++) // { // printf("%d ",qzh[i]); // } int ans=0; for(rii=1;i<=b;i++) { ans+=y[i]*qzh[b-i+1]; ans%=p; } cout<<ans%p; } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |