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.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
24:11:50
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
24:11:50
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 17:23:10 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
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