Here is the problem link UVA Live 6844

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

1 | MiFaFaOvO | 3520 |

2 | tourist | 3461 |

3 | Um_nik | 3367 |

4 | apiadu | 3351 |

5 | mnbvmar | 3332 |

6 | Benq | 3330 |

7 | LHiC | 3276 |

8 | TLE | 3271 |

9 | Radewoosh | 3251 |

10 | ecnerwala | 3241 |

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

1 | antontrygubO_o | 190 |

2 | Errichto | 188 |

3 | tourist | 179 |

4 | Radewoosh | 172 |

5 | pikmike | 166 |

6 | vovuh | 165 |

7 | ko_osaga | 162 |

8 | Um_nik | 161 |

9 | rng_58 | 155 |

10 | majk | 154 |

Here is the problem link UVA Live 6844

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/19/2020 23:15:00 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

http://www.voidcn.com/article/p-vljjarbk-sw.html

The explanation is in Chinese. You can read the code though...

Sorry, but I need the logic , not the solution. :)

I don't recommend it but you could use Google Translate. The translated explanation is understandable enough.

If you are dealing with binomial coefficients at first always think of how Pascals triangle might help you. The problem basically wants to find quantity of odd numbers in some region of pascals triangle. The region is a trapezoid cut with two horizontal lines.

Next idea is that, when you want to calculate something for interval

[low, high], calculate if for[1,high]and[1,low-1]then subtract and get the result for[low, high].This trick works because it is easier to deal when the left endpoint of your interval is 1.Now we need a function

f(n)which returns the number of odd entries in firstnrows of pascal's triangle. In fact, the following is true: The number of odd entries in rowNof Pascal's Triangle is2raised to the number of1's in the binary expansion ofN. Example: Since83 = 64 + 16 + 2 + 1has binary expansion(1010011), then row83has2^4 = 16odd numbers.Hope these ideas will help you in solving this problem. If something is still unclear let me know.

Thank you

Go to this link and under the Rows you will see:

Parity: To count odd terms in row n (in pascal triangle), convert n to binary. Let x be the number of 1s in the binary representation. Then the number of odd terms will be $$$2^x$$$. These numbers are the values in Gould's sequence.[20]

So, how we can calculate this within a huge $$$10^{11}$$$ range. Use Digit DP. See this link for this kind of problems.