Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

bhaag_milkha's blog

By bhaag_milkha, history, 3 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.

• +10

 » 3 months ago, # |   0 Problem tag — Digit DP.
 » 3 months ago, # | ← Rev. 2 →   +11 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.
•  » » 3 months ago, # ^ |   +5 Thanks a lot for your explanation
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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.
 » 3 months ago, # |   0 Auto comment: topic has been updated by pandav (previous revision, new revision, compare).