Connection Status:
Competition Arena > LISNumber

LISNumber

SRM 585 · 2013-06-25 · by wrong

SRM 585 · 2013-06-25 · by wrong · Dynamic Programming
Class Name: LISNumber
Return Type: int
Method Name: count
Arg Types: (vector<int>, int)
Problem Statement

Problem Statement

Let A be a sequence of integers. The LISNumber of A is the smallest positive integer L such that A can be obtained by concatenating L strictly increasing sequences. For example, the LISNumber of A = {1, 4, 4, 2, 6, 3} is 4, since we can obtain A as {1, 4} + {4} + {2, 6} + {3}, and there is no way to create A by concatenating 3 (or fewer) strictly increasing sequences. The LISNumber of a strictly increasing sequence is 1.


You have N types of cards. For each i, 0 <= i < N, you have cardsnum[i] cards of the i-th type. Each card of the i-th type contains the number i.


You are given the int[] cardsnum and an int K. You want to arrange all the cards you have into a row in such a way that the resulting sequence of integers has LISNumber K. Note that you must use all the cards you have, you can only choose their order.


Let X be the number of different valid sequences you can produce. Compute and return the number X, modulo 1,000,000,007.

Constraints

  • cardsnum will contain between 1 and 36 elements, inclusive.
  • Each element of cardsnum will be between 1 and 36, inclusive.
  • K will be between 1 and 1296, inclusive.
Examples
0)
{1, 1, 1}
2
Returns: 4

In this case, there are 3 types of cards and you have one of each. Among the 6 sequences you can make, the following 4 have LISNumber 2: {0, 2, 1} {1, 0, 2} {1, 2, 0} {2, 0, 1}

1)
{2}
1
Returns: 0

The only sequence you can make is {0, 0} and its LISNumber is 2.

2)
{36, 36, 36, 36, 36}
36
Returns: 1

Only the sequence {0, 1, 2, 3, 4, 0, 1, 2, 3, 4, ... (36 times) ... } has LISNumber 36.

3)
{3, 2, 11, 5, 7}
20
Returns: 474640725
4)
{31, 4, 15, 9, 26, 5, 35, 8, 9, 7, 9, 32, 3, 8, 4, 6, 26}
58
Returns: 12133719

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

Coding Area

Language: C++17 · define a public class LISNumber with a public method int count(vector<int> cardsnum, int K) · 88 test cases · 2 s / 256 MB per case

Submitting as anonymous