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.

# | User | Rating |
---|---|---|

1 | Um_nik | 3459 |

2 | tourist | 3438 |

3 | maroonrk | 3359 |

4 | ecnerwala | 3347 |

5 | Benq | 3317 |

6 | ksun48 | 3309 |

7 | boboniu | 3300 |

8 | Petr | 3293 |

9 | Radewoosh | 3289 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 206 |

2 | Monogon | 194 |

3 | SecondThread | 191 |

4 | pikmike | 187 |

5 | antontrygubO_o | 186 |

6 | vovuh | 185 |

7 | Ashishgup | 181 |

8 | Um_nik | 180 |

9 | Radewoosh | 169 |

10 | pashka | 167 |

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.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/21/2020 10:51:51 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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.

Hi

Can 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).