NumJordanForms | Topcoder Archive

Problem Statement

You will be given 2 int[]s charPoly and minPoly, each containing N positive integers. A Jordan form is determined by choosing, for each index i, a partition of charPoly[i] such that no component of the partition exceeds minPoly[i] and at least 1 component is equal to minPoly[i]. A partition of a value v is an ordered list of positive integers that sum to v. Two Jordan forms are equivalent if they have the same partition for each i. Return the number of distinct Jordan forms mod 179424673.

Definition

Class:: NumJordanForms
Method:: howMany
Parameters:: int[], int[]
Returns:: int
Method signature:: int howMany(int[] charPoly, int[] minPoly)
(be sure your method is public)

Constraints

charPoly will contain between 1 and 50 elements, inclusive.
minPoly will contain the same number of elements as charPoly.
Each element of charPoly will be between 1 and 4000, inclusive.
Element i of minPoly will be between 1 and charPoly[i], inclusive.

Examples

```
{5}
```
```
{1}
```
```
Returns: 1
```
Only one Jordan form is possible here.
```
{5}
```
```
{3}
```
```
Returns: 2
```
There are 2 partitions of 5 that are possible here: (1,1,3) and (2,3).

{1,2,3,4,5,6,7,8,9}

{1,2,3,3,3,3,3,3,3}

Returns: 840

{4000,4000,4000,4000,4000}

{500,1000,1500,2000,2500}

Returns: 41788067

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.