### bhaag_milkha's blog

By bhaag_milkha, history, 10 months ago, 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. Comments (6)
 » Problem tag — Digit DP.
 » 10 months ago, # | ← Rev. 2 →   Here is my submission, which you can refer to: Atcoder Submission 8567969I 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
•  » » 8 months ago, # ^ | ← Rev. 2 →   i'm newbie to CP and didn't understand your explaination could u please elaborate how we can count the no. of pairs (x,y) such that y⊆x,y≤x≤N given that N <= 10^18 it will not pass the time limit.
•  » » HiCan someone explain the dp required to count pairs of (a,b) described above?
 » Auto comment: topic has been updated by pandav (previous revision, new revision, compare).