Can some one help me on how to solve this problem?
Editorial is given in Japanese, i used google translater to understand it but some sentence doesn't make any sense to me and i couldn't understand solution from editorial.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Can some one help me on how to solve this problem?
Editorial is given in Japanese, i used google translater to understand it but some sentence doesn't make any sense to me and i couldn't understand solution from editorial.
Название |
---|
Problem tag — Digit DP.
Here is my submission, which you can refer to: Atcoder Submission 8567969
I don't know the solution of the editorial, just give it on my own.
Prerequesite knowledge: For every $$$a, b \in \mathbb{N}$$$ then $$$a+b = a\oplus b + 2\times (a\ and\ b) =(a\ or\ b) + (a\ and\ b)$$$. Well this is easy to prove.
Therefore let $$$x = a\ or\ b,\ y = a\ and\ b,\ u = a\oplus b,\ v = a+b$$$ then $$$x+y = v, x-y = u$$$. So for each pair $$$(u, v)$$$ in the answer maps with exactly one pair $$$(x, y)$$$, and each pair $$$(x, y)$$$ such that $$$y \subseteq x, y \le x \le N$$$ corresponds with only one pair $$$(u, v)$$$. Here $$$y \subseteq x$$$ means in binary representation, each bit of $$$y$$$ is smaller than the corresponding bit of $$$x$$$.
So we can count the number of pair $$$(a, b)$$$ such that $$$b \subseteq a, a+b \le N$$$.
Let say in binary representation, $$$a = \overline{a_{60}a_{59}...a_{1}a_{0}}$$$ and $$$b = \overline{b_{60}b_{59}...b_{1}b_{0}}$$$ then we can solve the problem using Digit DP. You can refer to my solution.
Thanks a lot for your explanation
Hi
Can someone explain the dp required to count pairs of (a,b) described above?
Auto comment: topic has been updated by Lets__go (previous revision, new revision, compare).