Statistics

Problem Statement for "RndSubTree"

Problem Statement

Hero has an infinite complete binary tree rooted at the vertex r. That is, the tree contains r, its two children, four grandchildren, and so on. Initially, all vertices in this tree are white. Hero is going to color k vertices of its tree red. He will choose each of those vertices at random. More precisely, he will repeat the following procedure k times:
  1. Place a token onto the root vertex r.
  2. While the token is on a red vertex, choose one of its two children at random with equal probability and move the token onto the chosen child.
  3. When the token is on a white vertex for the first time, color that vertex red and remove the token.
If there are k red vertices in the tree, there are exactly k*(k-1)/2 simple paths such that both endpoints of the path are red. Hero is interested in the total length of all these paths. Calculate the expected value of that total length. Let M = 10^9 + 7. It can be shown that the exact value of the answer can be written as a reduced fraction P/Q such that Q and M are relatively prime. Let Q^(-1) be the multiplicative inverse of Q, modulo M. Compute and return the value (P*Q^(-1)) modulo M.

Definition

Class:
RndSubTree
Method:
count
Parameters:
int
Returns:
int
Method signature:
int count(int k)
(be sure your method is public)

Constraints

  • k will be between 1 and 2000, inclusive.

Examples

  1. 1

    Returns: 0

    With only one red vertex there are no paths, so their total length is always zero.

  2. 2

    Returns: 1

    The two red vertices will always be the root vertex r and one of its children. The only path with both endpoints red will always have length 1.

  3. 3

    Returns: 4

    Regardless of the random choices, the three red vertices will always form a path. (The root vertex r may be an endpoint of this path, or it can be in its middle.) The three random paths will have lengths 1, 1, and 2, for a total of 4.

  4. 4

    Returns: 875000016

    With probability 7/8 the sum of path lengths is 10 and with probability 1/8 the sum of path lengths is 9. Thus, the expected value of the sum of path lengths is (7/8)*10 + (1/8)*9 = 79/8. The multiplicative inverse of 8 modulo M = 10^9 + 7 is 125,000,001, because (125000001*8) mod M = 1. Thus, the value you should return is (79 * 125000001) mod M = 875000016.

  5. 5

    Returns: 531250023

  6. 13

    Returns: 550543927

  7. 6

    Returns: 536132849

  8. 10

    Returns: 582619904

  9. 14

    Returns: 989090268

  10. 963

    Returns: 683171333

  11. 465

    Returns: 715789616

  12. 1706

    Returns: 824216557

  13. 146

    Returns: 117331447

  14. 1282

    Returns: 804393528

  15. 828

    Returns: 892514529

  16. 1962

    Returns: 711362666

  17. 492

    Returns: 750679241

  18. 996

    Returns: 561537129

  19. 1943

    Returns: 284057289

  20. 828

    Returns: 892514529

  21. 1437

    Returns: 836650432

  22. 392

    Returns: 291294092

  23. 605

    Returns: 641435326

  24. 1903

    Returns: 760951976

  25. 154

    Returns: 611633578

  26. 293

    Returns: 100983582

  27. 383

    Returns: 693880629

  28. 1422

    Returns: 526846566

  29. 717

    Returns: 933463998

  30. 2000

    Returns: 201217106

  31. 1997

    Returns: 566030206

  32. 1972

    Returns: 66744704

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: