I am not sure about N, but it must be not O(n^²) solution.
№ | Пользователь | Рейтинг |
---|---|---|
1 | ecnerwala | 3649 |
2 | Benq | 3581 |
3 | orzdevinwang | 3570 |
4 | Geothermal | 3569 |
4 | cnnfls_csy | 3569 |
6 | tourist | 3565 |
7 | maroonrk | 3531 |
8 | Radewoosh | 3521 |
9 | Um_nik | 3482 |
10 | jiangly | 3468 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 161 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
I am not sure about N, but it must be not O(n^²) solution.
Название |
---|
Attempt 2 Let x&y = 2^k = (100..00)2 with k zeroes. Clearly, k+1-th bit should be 1 in both x and y (a&b=1 <=> a=b=1). And clearly x and y should have no other common bits. Let's find the number of pairs for each k. First, take only those numbers with k+1-th bit set. Consider one of them as a candidate for x. If it has ones in some other positions, then y should have zeroes in those positions. This translates into following: let mask = !(x) + 2^k and find all other numbers with k+1-st bit set, that are submasks of mask. For each k, you can find this number with dp over submasks.
i couldn't get the thing "Also all other bits should be 0 in both x and y (a&b=0 <=> a=b=0)" why? if other than $$$k$$$th bit if a bit is set in atmost one of $$$x$$$ and $$$y$$$ then still their bitwise and will be power of 2.
Lol, playing smart just wakig up is not a good idea! Updated.
Now it's correct. I think it's time complexity will be O($$$bits$$$ * $$$bits$$$ * 2$$$bits$$$), where $$$bits$$$ = floor(log2($$$maxAi$$$)). Correct me if i am wrong?
what topic should i study for understanding this? dp+ bitmask right?
Sum over subset dp(called as SOS dp). Here is a nice tutorial.
a AND b = 0 implies either a or b is 0 not both My proposed solution was wrong.