cf 515 div3 E-白红宇

cf 515 div3 E

阅读量：4493 次

发布时间：2019-06-08

本文共 1027 字，大约阅读时间需要 3 分钟。

传送门：

题意：两个二进制数a、b ，每次对a&b的结果求和，b右移一位，继续对a&b的结果求和，直至b==0

a、b长度 <= 2e5，结果对998244353取模

这题思路和某次刷题思路一致，很快就想到了，

a&b，按位与，当a [ i ] == 1 && b [ j ] == 1 时加上该位 2 的幂次权重

e.g.

543210

a 100101

b 10111

ans += 2 ^ 0 + 2 ^ 2

b 右移一位

　 543210

a 100101

b 1011

　　　……

发现 a 不动，对于 a 的每个“1”位，统计 b 中从0到与之对应位的 “1” 的个数，乘上对应位的 2 的幂次就可以啦

对 b 搞一个后缀和，遍历 a，统计求和即可

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;typedef long long ll;typedef pair
                 
                   P;typedef long double ld;#define mem(x) memset(x, 0, sizeof(x))#define me(x) memset(x, -1, sizeof(x))#define fo(i,n) for(i=0; i
                  
                   >n>>m; string s,p; cin>>s>>p; for(i=m-1; i>=0; i--) { if(p[i]=='1') k=1; else k=0; sum[i]=sum[i+1]+k; } k=1; ll ans=0; for(i=n-1, j=m-1; i>=max(0ll,n-m); i--,j--) { if(s[i]=='1') ans+=(sum[0]-sum[j+1])*k, ans%=MOD; k*=2;k%=MOD; } cout<
                   
                    <