my python 3 pretty simple approach and passes all test case:
a=input() b=input() x=int(a,2) y=int(b,2) p=0 for i in range(0,314160): p+=x^(y<<i) print(p%((10**9)+7))
If you're having trouble, notice that a^b = a+b-2*(a&b). The a and b part has its own formula for some. for the third term, see that every bit in a would collide with every bit in b that come there or after that. That means if a = 1100 b = 1001 the first one would collide with all 1s in b and the second one would collide with one in the 4th position of b.
I will not post my answer here. It's supposed to be locked away in the editorial.
Solved with Python the brutal approach and felt that I cheated:(
A python solution
I will just explain my algorithm below using the example a='1011'=11 and b='11'=3 with n=5
the problem ask us to compute
'1011'xor'11' =(1000) = bx2^0+a+err1
+'1011'xor'110' =(1101) = bx2^1+a+err2
+'1011'xor'1100' =(111) = bx2^2+a+err3
+'1011'xor'11000' =(10011) = bx2^3+a+err4
+'1011'xor'110000' =(111011) = bx2^4+a (no err from here)
+'1011'xor'1100000' =(1101011) = bx2^5+a
with err1=4+2, err2=4, err3=16, err4=16 with total error=sum=42.
so we can reduce the problem into two parts
1) compute the trivial sum bx(2^0+2^1+...+2^n)+ax(n+1) %1e9+7
2) compute the error terms
here i will explain how to compute the total errors by this example, the detailed algorithm can be found below
these errors come from when shifting b to the left, each '1' in b will only hit the digits '1' of a on the left.
for example,
'1 1 ' will hit ' 1 0 11 '
leading to an error 2x(1+2+8)=2+4+16 (times 2 here since both of those 1 become 0 after we take xor)
also ' 1 1' will only hit ' 1 0 1 1'
leading to an error 2x(2+8)=4+16
you can see that 2,4,16,4,16 are exactly the terms in err1--err4.
from collections import defaultdict M=1000000007 a = str(input()) b = str(input()) # need to change n into 314159 n=314159 # pre-compute powers of 2 up to n=314159 pof2=[1] for i in range(n+1): pof2.append((pof2[-1]*2)%M) # use a default list to count the number of 1's in b in the right k digits len_a=len(a) len_b=len(b) #print(len_a,len_b) cnt_b=defaultdict(int) cnt_b[0]=int(b[-1]) for i in range(1,len_b): cnt_b[i]=cnt_b[i-1]+int(b[-i-1]) # extend to the length of a for i in range(len_b,len_a): cnt_b[i]=cnt_b[len_b-1] # using pof2 to compute num_a%M,num_b%M num_a=0 num_b=0 for i in range(len_a): if int(a[-1-i])!=0: num_a+=pof2[i] for i in range(len_b): if int(b[-1-i])!=0: num_b+=pof2[i] #print(num_a,num_b) #compute the offset offset=0 for i in range(len_a): if int(a[-i-1])!=0: offset+=pof2[i+1]*cnt_b[i] #print(offset) # n=314159, which is very large answer=(num_b*(pof2[n+1]-1)+num_a*(n+1)-offset)%M print(answer)
here is a C++ solution that uses only 32 and 64 bit integers, and passes all test cases in O(lg a + lg b) time and space (took me about 4 hours of debugging, so the code is a bit messy, but I finally got it to work, and it runs very fast). No recursion or dynamic programming is used.
The basic idea is that only the first approximately lg a terms in the sum require any actual XOR to be done; for the rest of the terms, a and b are "decoupled" and XOR is equivalent to addition, so that part of the sum can be computed in O(1) time.
The XOR in the first lg a terms can be done by "sliding" b through a, and for each bit in a (as well as the zeros padding a from above), we can count the number of zeros and ones that will "hit" that bit in O(1) time per bit, provided that we precompute the number of ones and zeros in b, which takes O(lg b) time.
#include <iostream> #include <string> #include <vector> #include <algorithm> using std::string; using std::vector; constexpr unsigned mod=1000000007U; constexpr unsigned top=314159U; constexpr unsigned powtop=348880127U; // 2**(top+1) % mod vector<unsigned> powers(int n){ vector<unsigned> p; p.reserve(n); unsigned x=1; p.push_back(x); for(int i=1;i<n;++i){ x=(x<<1)%mod; p.push_back(x); } return p; } inline void increment(unsigned &x, unsigned y){ x=(x+y)%mod; } unsigned solve(const vector<bool> &a, const vector<bool> &b){ const int na=a.size(), nb=b.size(); vector<unsigned> p{powers(na+nb)}; unsigned sum=0; vector<unsigned> ones(nb,0), zeros(nb,0); zeros[0]=!b[0]; ones[0]=b[0]; for(int i=1;i<nb;++i){ ones[i]=ones[i-1]+b[i]; zeros[i]=zeros[i-1]+(!b[i]); } for(int i=na+nb-2, j=nb-1, k=1; i>=na; --i){ unsigned long add=p[i]; unsigned nones=ones[j]-(j>=k?ones[j-k] : 0); add=(add*nones)%mod; increment(sum,static_cast<unsigned>(add)); if(i<nb) --j; if(k<na) ++k; } for(int i=na-1;i!=-1;--i){ unsigned long add=p[i]; unsigned times=0; unsigned nones=i<nb? ones[i]:ones.back(); unsigned nzeros=i<nb? zeros[i]:zeros.back(); if(a[i]){ times=nzeros+na-1-i; if(i>nb-1) times+=i-(nb-1); }else if(i<nb-1) times=nones; else times=ones.back(); add=(add*times)%mod; increment(sum,static_cast<unsigned>(add)); } unsigned aval=0,bval=0; for(int i=0;i<na;++i){ if(a[i]) increment(aval,p[i]); } for(int i=0;i<nb;++i){ if(b[i]) increment(bval,p[i]); } unsigned long temp1=top-na+1; temp1=(temp1*aval)%mod; increment(sum,static_cast<unsigned>(temp1)); unsigned long temp2=powtop; temp2+=mod-p[na]; temp2=(temp2*bval)%mod; increment(sum,static_cast<unsigned>(temp2)); return sum; } void input(){ string sa,sb; std::cin >> sa >> sb; const int na=sa.size(), nb=sb.size(); vector<bool> a(na,0), b(nb,0); for(int i=0;i<na;++i) a[na-i-1]=(sa[i]=='1'); for(int i=0;i<nb;++i) b[nb-i-1]=(sb[i]=='1'); std::cout << solve(a,b) << '\n'; } int main(){ input(); }
Sort 49 Discussions, By:
Please Login in order to post a comment