Sukarna_Paul's blog

By Sukarna_Paul, history, 6 months ago, In English,

Here is the problem link UVA Live 6844

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
Rev. 4   Vote: I like it +7 Vote: I do not like it

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 first n rows of pascal's triangle. In fact, the following is true: The number of odd entries in row N of Pascal's Triangle is 2 raised to the number of 1's in the binary expansion of N. Example: Since 83 = 64 + 16 + 2 + 1 has binary expansion (1010011), then row 83 has 2^4 = 16 odd numbers.

Hope these ideas will help you in solving this problem. If something is still unclear let me know.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.