TreeCount | Topcoder Archive

Problem Statement

In graph theory, an independent set or stable set is a set of vertices in a graph such that no two of the vertices are adjacent. That is, it is a set V of vertices such that for every two vertices in V, there is no edge connecting the two.

Similarly, we can define a k-stable set as a set of vertices in a graph such that each vertex in the set has at most k adjacent vertices that are also in the set. So the 0-stable set is the original stable set.

You will be given a String[] graph, representing an undirected, acyclic, connected graph. The j-th character of the i-th element of graph will be 'Y' if vertices i and j are connected, or 'N' otherwise. Return a int[] containing exactly n elements, where n is the number of elements in graph. The i-th element should be the number of distinct i-stable sets in the graph modulo 112901989, where i is a 0-based index.

Definition

Class:: TreeCount
Method:: count
Parameters:: String[]
Returns:: int[]
Method signature:: int[] count(String[] graph)
(be sure your method is public)

Constraints

graph will contain between 1 and 50 elements, inclusive.
Each element of graph will contain exactly N characters, where N is the number of elements in graph.
Each character in graph will be either 'Y' or 'N'.
The j-th character of the i-th element of graph will equal to the i-th character of the j-th element.
The i-th character of the i-th element of graph will be 'N'.
The graph will represent a tree.

Examples

```
{"NYY", "YNN", "YNN"}
```
```
Returns: {5, 7, 8 }
```
The tree is 1-0-2. The 5 0-stable sets are {}, {0}, {1}, {2}, {1, 2}. The 7 1-stable sets are all the subsets except {0, 1, 2}. There are 2^3 subsets total, and each one is a 2-stable set.
```
{"N"}
```
```
Returns: {2 }
```

{"NYNNNYY", "YNNNNNN", "NNNNNNY", "NNNNNNY", "NNNNNNY", "YNNNNNN", "YNYYYNN"}

Returns: {44, 73, 104, 124, 128, 128, 128 }

```
{"NY", "YN"}
```
```
Returns: {3, 4 }
```

{"NYYYYY", "YNNNNN", "YNNNNN", "YNNNNN", "YNNNNN", "YNNNNN"}

Returns: {33, 38, 48, 58, 63, 64 }

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.