| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Given an array of size $$$n$$$. How can we find sum of XOR sum of all subsets in better than $$$O(2^n)$$$ ?
For example consider $$$array = [1,4,5]$$$
$$$ Answer = 1 + 4 + 5 + 1^4 + 1^5 + 4^5 + 1^4^5 $$$ (here '^' denotes bitwise XOR )
Basically harder version of this leetcode problem, with nums.length <= 10^5.
consider for each individual bit let's say i if for any of the elements in the array we count the number of ones that are there now we will only add the ith position as 2*(i+1) now as there are lets say k ones so there must be (n-k) zeros now for the position to have xor value of one we will have to choose odd number of ones so it would be : kc1+kc3+...+kck=2**(k-1) now we can choose any number of zeros with each of the chossen pair so it would be (n-k)c0+(n-k)c1+(n-k)c2.....=2**(n-k) then we multiply then to get 2**(n-1) so answer would be : pow(2,n-1)*(pow(2,i)) for all position i where i is a set bit at least once in the array (https://mirror.codeforces.com/problemset/problem/1614/C)https://mirror.codeforces.com/problemset/problem/1614/C
sorry for a bad explanation you can try the above problem for a greater understanding
Consider each bit independently. For the $$$i$$$-th bit, let's say there are $$$k$$$ elements that have that bit as $$$1$$$, and $$$n-k$$$ elements that do not.
Then, the contribution to the answer is $$$2^i \times \left( \sum_{j=0}^{\left \lfloor \frac{k-1}{2} \right \rfloor} {k \choose 2j+1} \cdot 2^{n-k} \right) = 2^i \times 2^{n-1}$$$.
Time complexity: $$$O(n \log \max(a_i))$$$.
On observing you can realise that answer is just $$$x \cdot 2^{n-1}$$$, where $$$x$$$ is bitwise OR of all elements of the given array.
I don't understand. Can you prove it?
The expression simplifies to $$$2^i \cdot 2^{n-1}$$$ for each bit which appears atleast once in any number in the array.
So the total sum is $$$x \cdot 2^{n-1}$$$ where $$$x$$$ is OR of the array.
I don't understand why we can simplify from $$$2^i \times \left( \sum_{j=0}^{\left \lfloor \frac{k-1}{2} \right \rfloor} {k \choose 2j+1} \cdot 2^{n-k} \right) $$$ to $$$2^i \cdot 2^{n-1}$$$, xor value of a position = 1 only when the number of set bits is odd
$$$\sum_{j=0}^{\left\lfloor {\frac{k-1}{2}}\right \rfloor}\binom{k}{2j+1}=2^{k-1}$$$
Yeah you are correct
A similiar codeforces problem — Round 757 Div. 2 C Divan and bitwise operations