RndSubTree | Topcoder Archive

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:

Place a token onto the root vertex r.
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.
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
```
```
Returns: 0
```
With only one red vertex there are no paths, so their total length is always zero.
```
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
```
```
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
```
```
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
```
```
Returns: 531250023
```

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.