Connection Status:
Competition Arena > TwiceTwiceTree

TwiceTwiceTree

TCO 2014 Semifinal 2 · 2014-03-26 · by snuke

TCO 2014 Semifinal 2 · 2014-03-26 · by snuke · Graph Theory, Math, Recursion
Class Name: TwiceTwiceTree
Return Type: int
Method Name: sumup
Arg Types: (int, int, int)
Problem Statement

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.

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
0)
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)
1
10
503
Returns: 0

There is no path of length 10 because the tree is too small.

2)
10
1
503
Returns: 17
3)
10
5
1000000009
Returns: 21352
4)
987654321
500
1000000009
Returns: 420937613

Submissions are judged against all 99 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TwiceTwiceTree with a public method int sumup(int N, int D, int P) · 99 test cases · 2 s / 256 MB per case

Submitting as anonymous