There are 3 integers a, b, w.
There are 2 equations –
w+a=b
a (bitwise AND) b = 0;
I was given the value of w and he asked me to calculate the number of pairs (a, b) satisfying the two equations.
Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3640 |
| 2 | Benq | 3593 |
| 3 | tourist | 3572 |
| 4 | orzdevinwang | 3561 |
| 5 | cnnfls_csy | 3539 |
| 6 | ecnerwala | 3534 |
| 7 | Radewoosh | 3532 |
| 8 | gyh20 | 3447 |
| 9 | Rebelz | 3409 |
| 10 | Geothermal | 3408 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 24.04.2024 01:28:38 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Let i be the left-most set bit in m (0 -based), then for ever a = "111111111..00000", where 1 appears aleast two times, and zero appears i times, then a&b = a&(a + w) = 0
Therefore the number of solutions is ∞ (for positive w).
you are right that is why I am asking about constraints.
constraints?
I guess the first equation should look like a + b = w instead of a + w = b.
In this case answer is equal to 2ones(w) where ones(w) is amount of ones in binary representation of w.
a&b = 0 says that there is no common set bit in a and b. In this case sum operation equals to bitewise-or operation, because there is no digit overflows in our sum.
So now we have these equations:
a&b = 0
a|b = w
As we only use bitwise operations we can solve the problem for each bit independently and then multiply our results for all bits.
If current bit in w is zero, only possible solution is a = 0; b = 0. Answer is 1.
If current bit in w is one, there are two solutions: a = 0; b = 1 and a = 1; b = 0. Answer is 2.
Final answer is 2ones(w)·1zeroes(w) which is equal to 2ones(w).
If w = 0 then we have a = b, and the only possible solution for this is a = b = a&b = 0.
If w is positive we can generate infinte amount of pairs (a, b) that satisfy both equations. Let's onsider w = 13 and look at binary presetation of some correct pairs (a, b). It is easy to see the pattern that generates some of them:
As we have no other limitations answer is ∞ for any positive w.
What if there is a limit for case
a + w = b