HiddenTree | Topcoder Archive

Problem Statement

In this problem a directed forest is an arbitrary directed acyclic graph in which each node has at most one incoming edge.

Suppose we have a directed forest and we have already assigned a positive integer weight a[i] to each node i of the forest. We can now compute aggregate weights b[i] as follows: b[i] will be the sum of the weights of all nodes reachable from i, including node i itself.

You are given the int[] b. We say that a directed forest is compatible with b if there is at least one way to assign a positive integer weight a[i] to each node i of the forest in such a way that the aggregate weights of all vertices will be exactly equal to the values given in b.

Compute and return the number of directed forests that are compatible with the given b, modulo 10^9 + 7. Note that each valid forest should only be counted once, even if there are multiple valid ways to assign weights to its vertices.

Definition

Class:: HiddenTree
Method:: count
Parameters:: int[]
Returns:: int
Method signature:: int count(int[] b)
(be sure your method is public)

Constraints

b will be contain between 1 and 14 elements, inclusive.
Each element of b will be between 1 and 10^9, inclusive.

Examples

```
{1,1,1,1,1,1,1,1,1,1,1,1,1,1}
```
```
Returns: 1
```
The only valid forest is the one with no edges.
```
{3,1,2}
```
```
Returns: 5
```
There are five different forests with the following edge lists, and corresponding values of a. [], a = {3,1,2} [0 -> 1], a = {2,1,2} [0 -> 2], a = {1,1,2} [2 -> 1], a = {3,1,1} [0 -> 2, 2 -> 1], a = {1,1,1}
```
{3,1,1}
```
```
Returns: 4
```
```
{1000000000,1,2,3,4,5,6}
```
```
Returns: 2870
```

{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}

Returns: 178290591

Don't forget about mod.

```
{474747474}
```
```
Returns: 1
```

{536870912,536870912,536870912,536870912,536870912,
536870912,536870912,536870912,536870912}

Returns: 1

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.