TwiceTwiceTree | Topcoder Archive

Problem Statement

Given a tree T, we can produce a new tree T' as follows: T' will contain the entire tree T. Additionally, for each vertex x in T, add a new vertex to T' and attach it to x. We will call this procedure growing the tree.

You are given ints N, D, and P. Start with a tree that consists of a single vertex. Grow this tree N times to produce a tree with 2^N vertices. In that tree, count all simple paths of length D, and return that count modulo the prime P.

The length of a simple path is the number of edges it contains. Two simple paths are considered different if they contain a different set of edges. In other words, the direction in which the path is traversed does not matter.

Definition

Class:: TwiceTwiceTree
Method:: sumup
Parameters:: int, int, int
Returns:: int
Method signature:: int sumup(int N, int D, int P)
(be sure your method is public)

Constraints

N will be between 1 and 1,000,000,000, inclusive.
D will be between 1 and 500, inclusive.
P will be between 503 and 1,000,000,009, inclusive.
P will be a prime.

Examples

```
3
```
```
3
```
```
1000000007
```
```
Returns: 8
```
The eight paths are shown in orange in the figure below. You may also note that the size of the nodes corresponds to their "generation": the largest node is the original one, the smallest nodes are the ones that were added when the tree grew for the last time.
```
1
```
```
10
```
```
503
```
```
Returns: 0
```
There is no path of length 10 because the tree is too small.
```
10
```
```
1
```
```
503
```
```
Returns: 17
```
```
10
```
```
5
```
```
1000000009
```
```
Returns: 21352
```

987654321

1000000009

Returns: 420937613

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.