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.

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

1 | tourist | 3778 |

2 | Benq | 3592 |

3 | ecnerwala | 3521 |

4 | Um_nik | 3423 |

5 | jiangly | 3375 |

6 | Petr | 3342 |

7 | Radewoosh | 3337 |

8 | scott_wu | 3313 |

9 | maroonrk | 3265 |

10 | yosupo | 3259 |

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

1 | Errichto | 202 |

2 | 1-gon | 201 |

3 | rng_58 | 194 |

4 | SecondThread | 193 |

5 | awoo | 187 |

6 | vovuh | 183 |

7 | Um_nik | 182 |

8 | antontrygubO_o | 177 |

9 | Ashishgup | 175 |

10 | -is-this-fft- | 171 |

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.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/17/2021 18:36:24 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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=winstead ofa+w=b.In case of a + b = wIn this case answer is equal to 2

^{ones(w)}whereones(w) is amount of ones in binary representation ofw.a&b = 0 says that there is no common set bit inaandb. 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 = 0a|b=wAs 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

wis zero, only possible solution isa= 0;b= 0. Answer is 1.If current bit in

wis one, there are two solutions:a= 0;b= 1 anda= 1;b= 0. Answer is 2.Final answer is 2

^{ones(w)}·1^{zeroes(w)}which is equal to 2^{ones(w)}.In case of a + w = bIf

w= 0 then we havea=b, and the only possible solution for this isa=b=a&b = 0.If

wis positive we can generate infinte amount of pairs (a,b) that satisfy both equations. Let's onsiderw= 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`

Ya,if it is a+b=w then the solution will narrow down to find (a,b) such that a xor b=w but here the equation w+a=b is kinda bizarre in terms of generality.