You are viewing a single comment's thread. Return to all comments →
no idea how on earth people are doing it in 4 few lines with what seems to be the brute force method
this method is O(414159 + b.size()), and works for ANY bitwise operator not just XOR
long xorAndSum(string a, string b) { a.insert(0, 414159 - a.size(), '0'); long result = 0, mod = 1000000007; vector<long> twoPower = { 1 }, aPartial = {0, a.back()-'0'}; for (int i = 1; i < 414159; i++) { twoPower.push_back((2 * twoPower.back()) % mod); aPartial.push_back((aPartial.back() + (a[414158 - i] - '0') * twoPower.back()) % mod); } for (int i=0; i <= 314159; i++) result = (result + aPartial[i] + aPartial[414159] - aPartial[i+b.size()]) % mod; vector<vector<long>> cache = { {0, 0} }; for (int i = 0; i <= 314159; i++) { cache[0][0] = (cache[0][0] + ((a[414158 - i] - '0') ^ 0) * twoPower[i]) % mod; cache[0][1] = (cache[0][1] + ((a[414158 - i] - '0') ^ 1) * twoPower[i]) % mod; } for (int i = 0; i < b.size(); i++) { result = (result + cache[i][b[b.size() - 1 - i] - '0']) % mod; long zero = (cache[i][0] - ((a[414158 - i] - '0') ^ 0) * twoPower[i]) % mod; long one = (cache[i][1] - ((a[414158-i] - '0') ^ 1) * twoPower[i] + twoPower[i+314160]) % mod; cache.push_back({zero, one}); } return (result + mod) % mod; }
Seems like cookies are disabled on this browser, please enable them to open this website
Xor and Sum
You are viewing a single comment's thread. Return to all comments →
no idea how on earth people are doing it in 4 few lines with what seems to be the brute force method
this method is O(414159 + b.size()), and works for ANY bitwise operator not just XOR