Statistics

Problem Statement for "NumJordanForms"

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

  1. {5}

    {1}

    Returns: 1

    Only one Jordan form is possible here.

  2. {5}

    {3}

    Returns: 2

    There are 2 partitions of 5 that are possible here: (1,1,3) and (2,3).

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

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

    Returns: 840

  4. {4000,4000,4000,4000,4000}

    {500,1000,1500,2000,2500}

    Returns: 41788067

  5. {598,401,256,572,169,566,770,471,81,415,525,18,46,86,307,413,64,852,793,227,589,487,61,837,432,797,429,810,712,594,760,985,115,10,138}

    {36,228,174,485,157,530,741,442,12,316,73,5,22,9,36,336,28,471,78,22,490,33,20,272,358,685,374,178,227,420,329,709,56,2,85}

    Returns: 121531666

  6. {12,95,600,328}

    {1,82,362,4}

    Returns: 49492343

  7. {286,752,260,344,8,938,599,249,866,248,724,570,447,659,334,829,225,775}

    {134,498,47,180,3,142,474,221,126,225,123,546,318,294,228,671,146,68}

    Returns: 129059041

  8. {944,618,687,507,394,654,237,182,816,977,576,293,340,1000,175,513,256,932,252,745,79,563,281,378,968,125,283,326,934,780,168,9,803,216,775,880,446,26,228,325,315,20,639}

    {714,613,293,111,199,17,220,66,552,61,497,99,171,892,89,417,205,796,56,371,9,407,133,362,697,3,45,228,338,438,66,5,301,163,725,647,228,8,187,186,18,11,59}

    Returns: 25948695

  9. {714,930,782,861,30,115,994,649,242,442,725,518,489,973,550,374,914,981,364,420,773,690,629,800,924,892,115,190,117,338,960,117,377}

    {669,911,666,330,2,64,347,96,124,29,637,264,448,884,337,339,770,142,264,266,766,422,146,314,421,825,15,23,38,335,130,39,139}

    Returns: 163303608

  10. {770,973,85,980,235,512,787,78,114,351,44,421,723,973,337,648,460,142,353,322,484,297,26,813,570,849,77,912,59,428,484,124,394,234,84,474,851,591,222,839,742,459,175,279,520,144}

    {705,553,81,677,136,67,596,38,110,324,39,163,143,314,295,221,374,5,265,241,111,11,24,51,494,129,59,42,3,195,71,92,337,159,31,386,376,98,86,199,50,157,131,30,359,84}

    Returns: 165018766

  11. {581,847,404,848,304,924,440,754}

    {74,117,20,770,66,778,319,100}

    Returns: 173555948

  12. {97,391,537,395,794,406,454,511,6,731,617,940,648,941,192,802,996,1000,635,237,60,452,187,857,342,528,237}

    {35,16,504,280,147,133,255,43,1,680,9,643,260,864,34,258,887,167,626,130,21,360,99,194,336,257,68}

    Returns: 78076297

  13. {807,435,548,852,776,413,557,369,905,293,539,740,101,192,929,550,879,327,319,6}

    {630,230,134,533,761,149,455,138,821,222,166,161,87,8,253,533,498,113,132,5}

    Returns: 106648765

  14. {399,483,950,977,836,697,661,764,276,719,275,268,608,110,674,47,87,238}

    {71,181,97,16,578,226,474,428,52,546,105,199,234,87,354,43,63,227}

    Returns: 66976762

  15. {562,387,954,720,472,604,104}

    {318,379,911,461,287,243,8}

    Returns: 97483991

  16. {683,239,745,308}

    {327,171,16,217}

    Returns: 62473490

  17. {451}

    {282}

    Returns: 141506280

  18. {108,501,702,320,752,801,729,901,166,83,1000,640,752,657,188,207,996,78,17,585,60,597,232,295,550,471,694,697}

    {82,329,421,211,354,127,404,138,55,26,453,220,429,381,170,122,892,1,5,188,14,226,2,59,514,106,121,10}

    Returns: 175951392

  19. {240,153,865,407,444,330,745,402,312,521,235,376,451,459,274,472,879,339,26,514}

    {202,7,629,345,84,251,742,55,225,134,126,372,272,167,84,292,789,249,6,507}

    Returns: 9019965

  20. {285,267,351,117,413,178,391,413,344,665,594,88,832,624,997,848,694,158,853,367,593,627,304,54}

    {239,125,242,45,387,131,266,18,21,207,26,9,514,315,464,838,421,55,435,63,310,135,166,5}

    Returns: 41878040

  21. {550,126,592,709,350,112,996,416}

    {428,78,24,593,258,72,363,390}

    Returns: 108414211

  22. {176,624,142,396,347,911,376,813,201,675,440,488,582,176,872,532,572,677,809,921,980,979,301,539,385}

    {109,574,71,125,11,435,342,212,54,132,292,165,204,111,615,315,132,168,211,100,410,685,11,204,278}

    Returns: 105018457

  23. {806,548,196,338,53,527,432,318,213,253,436,556,906,718}

    {782,413,4,267,51,242,359,84,144,33,206,554,699,406}

    Returns: 128913996

  24. {537,851,375,78,34,226,549,7,905,685,131,446,197,593,462,442,230,405,436,546,736,739,760,667,376,450,235,718,194,802,699,359,326,686,362,18,13,27,912,108,775,969,981,776,411}

    {94,201,311,28,20,143,240,6,151,76,16,380,49,217,20,77,200,43,15,26,37,462,736,282,68,179,227,51,10,667,506,91,270,187,239,7,8,24,873,31,426,911,530,605,372}

    Returns: 91363576

  25. {980,638,546,276,835,11,930,236,431,838,378,249,231,963,878,51,909,14,727,156,22,462,877,465,686,665,656,936,970,107,570,50,844,481,309,164,360,775,689,699,428,984,178,511,971,651}

    {872,460,258,273,317,9,862,219,161,299,373,32,133,674,581,28,75,3,194,153,11,187,404,290,364,629,63,469,954,88,176,21,423,100,227,132,246,468,10,658,87,269,131,262,814,427}

    Returns: 28106949

  26. {761,636,543,988,263,320,783,55,309,209,584,546,968,297,422,308,889,901,969,119,1000,228,417,500,343,495,86,301,449,789,205,672,780,670,333,901,999,640,952,202,30,990}

    {309,610,87,202,126,33,523,4,192,64,511,468,15,110,319,142,393,690,719,24,137,139,281,12,241,165,32,91,183,335,139,581,105,631,190,113,573,182,39,11,8,652}

    Returns: 164025199

  27. {466,378,819,950,731,640,413,15,127,283,801,476,334,290,596,236,232,698,274,304,11,423,132,178,805,511,534}

    {35,187,793,836,179,42,413,15,58,272,603,213,202,19,255,218,83,477,248,233,8,253,121,29,708,258,60}

    Returns: 10238036

  28. {460,554,343}

    {233,499,134}

    Returns: 95222830

  29. {934,1000,82,479,780,420,636,10,972,696,268,460,149,51,501,438,730,538,227,373,418,258,281,721,186,663,744,651,963,264,136,486,204,352,914,371,289,717}

    {181,415,19,346,319,330,269,6,694,59,128,275,44,33,314,186,255,113,88,118,230,21,45,237,147,176,681,324,714,73,3,152,69,222,34,1,121,706}

    Returns: 32447275

  30. {876,142,753,633,580,239,688,188,974,251,974,423,994,945,115,471,712,600,984,795,599,575,186,700,866,617,96,592,630,616,712,32,574,150,771,253,712,973,422,139,852,775,94,862,347,942,127,288,794}

    {677,20,742,231,330,19,137,114,292,103,359,261,81,816,107,381,390,489,849,316,170,209,43,235,795,518,16,209,54,393,99,9,290,133,168,224,406,746,306,58,359,738,37,249,92,921,33,58,586}

    Returns: 89038270

  31. {747,175,529,630,242,271}

    {71,74,17,529,48,234}

    Returns: 4418291

  32. {896,257,365,217,694}

    {830,253,101,48,98}

    Returns: 50444062

  33. {699,922,859,894,433,719,116,837,491,922,564,163,562,559,606,988,21,255,374,496,336,646,273,256,373,127,547,735,331,582,323,663,73,635,915,662,449,852,720}

    {614,708,266,824,80,718,104,286,433,357,382,35,410,89,545,354,13,167,326,99,301,516,156,97,238,3,292,157,230,506,10,86,51,242,464,163,416,730,522}

    Returns: 59903195

  34. {133,190,85,332,548,990,44,904,831,773,813,69,48,211,850,341,459,989,99,881,175,103,296,616,564,555,132,968,594,262,542,44,221,644,873,86,256,832}

    {36,31,14,199,59,564,26,159,61,172,452,60,40,55,617,308,109,534,97,416,81,25,176,446,175,372,9,701,368,152,141,39,130,491,48,71,131,325}

    Returns: 49375916

  35. {2587,2271,2392,3149,2403,3933,2397,3916,2458,2337,3984,3556,3157,3631,2118,2142,3153,3359,2964,2367,3115,3124,2975,2946,3812,3998,2884,3678,2506,2453,2982,2832,3011,2505}

    {987,2231,1441,1951,835,668,1503,24,796,811,744,345,565,467,1638,561,257,2792,455,1080,1933,2585,2116,1237,2991,2733,167,2473,1153,383,474,125,2015,1568}

    Returns: 42136422

  36. {2930,2770,2600,2661,3058,2749,3129,2410,3812,2419,2405,3576,2040,2514,3608,2223,3098,2424,3143,2570,2364,2945,3849,3918,3599,2927,3453,3098,3324,3662,3460,3526,2993,2547,3631}

    {553,968,1770,2474,1549,2573,426,451,656,1876,771,1653,543,2005,2877,2127,1749,614,2191,1597,1881,2082,1290,184,1682,1766,1356,1229,2063,1473,1271,849,1051,1440,562}

    Returns: 53268505

  37. {3938,3452,3553,2062,2445,2482,2939,2580,2195,3840,3152,2607,2637,2337,3880,3710,3675,3878,3591,2271,2528,3745,2928,2324,2832,3523,3040,2495,3790,3978,2953,2873,3771,3840,2909}

    {3515,597,1126,1537,1411,1750,2111,1672,480,3461,1220,1277,1242,735,3356,935,1425,638,1431,1858,2029,2803,1436,1045,2805,2466,1899,1836,67,2461,2282,2653,2014,2415,1827}

    Returns: 174129091

  38. {2699,2043,3295,3000,2101,2500,3781,2419,2145,2398,2634,3692}

    {262,1693,2309,656,818,14,2038,835,1486,1380,1045,1189}

    Returns: 49612124

  39. {3019,3826,3073,3950,2518,2629,3046,3100,2579,3278,3479,3216,2279,2077,3103,2528,2481,2943,3500,2463,2335,3602,2001,3187,3922,3675,3458,2971,3272,2250,2135}

    {355,135,1071,2658,977,1927,222,1250,1209,2544,593,263,264,1415,2082,2088,360,720,3440,1766,1071,1462,782,2870,959,2272,1701,1685,1614,2084,1616}

    Returns: 68803716

  40. {3539,2428,3454,2816,2503,3817,2888,3648,2847,3486,3175,3165,2861,2144,2916,3430,2101,3214,2737,3753,2834,2789,2493,2263,2265,2609,2461,3256,2341,2596,3676,2352}

    {15,642,2916,1236,1874,1034,1025,354,1972,2335,2147,400,1440,1287,1475,145,1151,308,1759,2944,690,491,2228,1624,152,45,248,307,2083,1396,902,447}

    Returns: 74515110

  41. {3023,2804,2507,2825,3244,3815,2702,3384,3440,2962,2318,2173,3786,2413,3575,3353,3766,2396,3438,2692,3592,3042,2136,2359,2032,2829,2847,3554,3476}

    {496,1954,2356,1540,65,2129,87,64,1446,696,947,1004,1443,1634,2510,1398,1292,847,1528,2227,3387,700,918,869,301,2293,1373,2386,3288}

    Returns: 144940763

  42. {3601,3858,2623,3229,3681,3251,2978,3891,3593,3920,3433,3746,2158,3680,2812,2915,3697,2463,2879,2165,3136,2011,3363}

    {3369,2966,1016,121,3187,2181,1654,1462,2811,415,3259,1575,868,774,966,835,3034,1717,2376,1442,211,250,1316}

    Returns: 82792237

  43. {3097,2930,3980,2731,2049,2937,2995,3501,3142,3467,2582,2724,3563,2364,3577,3978,2679,3209,3152,3921,3907,2543,3046,2657,3147,2352,3133,3945,3508,2647,3437,3802,2001,3288,2371,2375,3905,3023,2826,3803,2573}

    {1745,814,477,842,1024,1864,1859,1005,2542,3118,310,2006,3238,905,3525,5,69,2059,686,2769,985,527,274,2273,1862,1554,855,2475,1769,478,1495,738,782,1199,703,546,2766,1041,2411,410,2372}

    Returns: 97985853

  44. {2062,2372,2570,3883,2669,3961,3076,2413,2294,2974,3914,3995,2471,2757,3679,2698,3277,2635,2870,2146,3168,2331,3033,3410,2566,2881,2600,2503,2920,3944,2341,3124,2501,2691,3428,3350,3345,2783,3809,3107,2427,3313,3778,2404,2409,3092,3416,2568}

    {1154,1339,1205,3868,396,3496,2875,362,1242,828,906,464,260,952,1456,1427,1580,1998,2217,912,867,676,2622,2715,939,642,222,946,2028,3074,40,2640,1041,533,650,1728,1265,365,402,195,1252,328,855,1732,693,2632,3031,2434}

    Returns: 7131045

  45. {3216,3347,3105,2794,2660,3211,3625,2173,2696,3194,2485,2608,3863,2097,2519,3599,3211,2185,2285,2214,2703,3963,2764,3604,2217,2668,3424,3074}

    {1225,1580,2677,1869,303,2834,1271,1191,1181,2915,1068,1790,1168,362,1635,3084,1673,1659,814,1912,667,1308,2389,500,969,748,3202,1720}

    Returns: 23520847

  46. {3468,3402,3725,2904,3701,2268,3663,2334,3970,3395,3969,3468,3135,3732,3682,3333,2372,3599,3941,2437,2477,3124,3853}

    {1453,2385,3453,2542,2880,23,4,415,1949,2685,2392,1547,2576,682,2101,2089,540,2898,3803,1160,1748,3120,1602}

    Returns: 140440904

  47. {3576,3641,3442,3756,3163,2854,2314,2648,2555,3794,3735,2412,3128,2485,2250,2382,2967,2723,2466,3182}

    {1233,3375,1029,651,1459,2212,407,834,1612,680,1459,817,1511,1230,2207,1196,120,199,1907,1634}

    Returns: 106955687

  48. {3989,3592,3282,2660,2281}

    {728,1597,1030,932,351}

    Returns: 37495968

  49. {2169,3850,2785,2706,2269,3103,2821,3145,2499,3555,2612,2446,3988,3097,3315,3542,2264,3892,2290,2845,3600,2395,3857,3381,3506,2458,3378,3011,3242,3027,3532,3614,3349,3481,3498,2585,2510,3769,2931,3217,3378,3113,2644,3154,2377,2339}

    {1217,755,2751,810,257,176,1978,2617,920,1788,1831,2254,1471,1035,391,1828,1485,401,2122,696,767,208,1785,2485,2665,2044,2139,72,3011,2288,67,2086,2354,2394,231,1504,2188,1308,1604,1890,467,2328,1406,922,2292,452}

    Returns: 101759319

  50. {2474,2378,2105,3385,2907,3909,3559,2344,3290}

    {1217,1675,1577,1112,2577,3802,791,1055,47}

    Returns: 126682862

  51. {2279,2797,2943,2511,3541,2021,2929,3496,3278,2208,2602,3635,3251,2654,2711,3013,3951,3230,2186,3180,3927,2706,2093,2013,2714,2828,2831,3171,2553,3217,2635,2398}

    {1211,2029,1684,320,34,506,898,3028,824,178,1569,2998,2903,26,2345,1091,1135,1767,1262,1239,882,1799,1369,687,965,1173,1789,2031,1543,3044,1435,2253}

    Returns: 29927838

  52. {2734,2878,2586,3750,2094,2281,2270,2958,2858,2102,2769,2544,2282,2978,2523,2524,2442,2609,2860,2085,3137,2589,3786,2784,2613,2475,3316,2053,3216,2414}

    {1583,1329,1741,748,1927,2202,2227,2934,414,1289,1717,1533,298,1583,1297,1664,1316,1345,1725,1051,1011,894,2297,2392,1149,714,2679,942,2176,1128}

    Returns: 20712052

  53. {2233,2208,2016,2993,2676,2236,2270,3919,3434,2348,3346,2811,2099,2654,3478,2826,2619,2828,3507,3475,2713,2521}

    {654,1083,1115,1820,1900,1175,532,2115,3113,1369,1186,230,227,1082,1577,814,28,2731,1874,1999,552,246}

    Returns: 174985232

  54. {2565,2676,2846,3945,2881,2268,2171,3753,3008,3838,3942,3108,2768,2185,2713,3307,2876}

    {1503,1545,1392,894,313,353,552,2729,2277,182,3192,1269,894,199,328,59,1386}

    Returns: 81017905

  55. {2243,2405,3758,2224,2062,2203,2045,3910,3844,3744,3626,2276,3290,3399,2923,2736,2098,2453,3138,2758,3626,2961,2186,3127}

    {192,778,82,1421,1212,389,1241,706,2961,971,475,278,405,2959,913,2396,1582,741,1920,1502,3322,2447,1989,2581}

    Returns: 96395910

  56. {3625,2489,3143,2134,2888,3122,3350,2727,3392,3420,3752,3024,2387}

    {961,839,980,731,193,1084,1379,1698,2687,1052,2216,878,638}

    Returns: 105083883

  57. {2279,3580,3358,2808,3846,2156,2647,2576,3136,3434,2081,2176}

    {1459,34,49,261,2213,1531,539,2015,1936,2752,533,618}

    Returns: 85087137

  58. {3288,2816,3677,2151,2694,3034,2543,2790,3132,2189,2156,3628,2108,3819,3224,2966,2406,3033,2100,3366,2981,3655,2523,3851,2471,3381,2849,2757,2604,2544,2557,3830,2843,3876,2367,3725,3270,2466,3461,3705,3857,3029,3038,3952,3054,3521,3728,3696,2931,2188}

    {1937,192,3644,1301,2183,3008,171,276,1741,1544,1661,2006,775,2196,1998,394,1343,2335,2057,2831,1902,2617,1229,123,1302,1779,316,748,1471,166,2118,1031,24,1784,291,3396,2109,1352,1561,2706,1563,2925,1790,2014,1099,1139,1151,404,852,417}

    Returns: 19323090

  59. {3993,2207,2818,3958,2858,3421,3220}

    {2275,1569,1826,2600,2079,1504,2031}

    Returns: 64433700

  60. {3285,2447,2853,2055,3998,3798,3891,3771}

    {153,2177,507,724,1769,3763,2705,2822}

    Returns: 127782866

  61. {3011,3443,2028,3615,2764,2839,3239,2777,3412,3841,2528,2631,3351}

    {2380,2792,167,3514,264,243,1145,713,3232,3421,74,1011,1478}

    Returns: 160701061

  62. {3171,3596,2374,2411,3416,2999,2439,3923,3666,3832,3850,3325,3187,3958,3550,3802,2628,3471,2153,3166,3275,3685,3287,2821,2205,2751,2576,3403,3942,2981,2612,2418,3783,3187,3306,3239,2134,3713,2723,3931,2824}

    {334,3049,673,1988,1125,458,1100,450,1219,3170,1167,988,1032,555,2809,3596,1511,1751,386,150,2038,2033,3273,926,1917,185,1933,1160,3445,274,567,1667,125,2684,1431,2122,1864,2797,1151,522,1835}

    Returns: 77791122

  63. {2126,2459,3007,2014,2856,2212,2000,3199,2836,3247,2935,3830,2956,2317,2384,2720,3435,3016,2384,3879,3636,2270,3982,3048,3373,2330,3052,2999,3894,2819,2217,3037,3977,2833,2236,3086,2996,4000,3907,2197,2187,3899,3206,3361}

    {1975,1639,279,1085,2595,602,1937,2128,1338,1098,2746,2504,2119,1766,1761,672,104,1403,919,3155,969,1214,3386,2118,3257,342,1439,1061,211,301,778,1567,3831,378,467,156,402,274,1161,353,923,166,614,1898}

    Returns: 96541473

  64. {2499}

    {1207}

    Returns: 70837921

  65. { 4000,4000,4000,4000,4000,4000,4000,4000,4000,4000,4000,4000,4000,4000,4000, 4000,4000,4000,4000,4000,4000,4000,4000,4000,4000,4000,4000,4000,4000,4000, 4000,4000,4000,4000,4000,4000,4000,4000,4000,4000,4000,4000,4000,4000,4000, 4000,4000,4000,4000,4000 }

    {1,10,20,50,100, 150,200,250,300,400, 500,600,700,800,900, 1000,1100,1200,1300,1450, 1500,1600,1700,1800,1900, 2000,2100,2200,2300,2400, 2500,2600,2700,2800,2900, 3000,350,3150,3100,3200, 3300,3400,3500,3600,3700, 3800,101,1001,2001,501}

    Returns: 115446561

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.
This problem was used for: