Statistics

A monomial is a product of non-negative powers of variables, with an implied coefficient of 1. For example, x, xy, x²y, xyz, and 1 are all monomials.

A monomial formed from a set of n variables (specified in some particular order) can be represented as a vector of non-negative integers of length n. The ith element of this vector represents the power of the ith variable in our set of variables.

For example, let our set of variables be { x, y, z }. Then we have the following vectors for the following monomial expressions:

• x = [ 1, 0, 0 ]
• xy = [ 1, 1, 0 ]
• x²y = [ 2, 1, 0 ]
• xyz = [ 1, 1, 1 ]
• 1 = [ 0, 0, 0 ]

The degree of a monomial is then the sum of the elements of its vector representation. For instance, x has degree 1 and x²y has degree 3.

Now we can define an ordering on monomials, based on their vector representations. First we will define what is known as reverse lexicographic order. This ordering states that a monomial v comes before a monomial w if the left-most non-zero element of v - w is positive. For example, xyz comes before xy under a reverse lexicographic ordering. In this case, v - w is given by

[ 1, 1, 1 ] - [ 1, 1, 0 ] = [ 0, 0, 1 ]

The first non-zero element of v - w is 1, which is positive, so xyz comes before xy.

Now we will extend this ordering to define a more complex one, which is known as graded reverse lexicographic order (or simply graded order). Under the graded order, a monomial v comes before a monomial w if the degree of v is greater than the degree of w, or if both have the same degree and v comes before w under the reverse lexicographic order. For instance, the five monomials in the example above, sorted by graded ordering, are:

x²y, xyz, xy, x, 1

The monomials x²y and xyz have the same degree, but x²y comes before xyz under the reverse lexicographic ordering. All of the other monomials have different degree, and are shown in descending order of degree.

A polynomial of degree n can be formed from a list of variables by combining all of the monomials of degree less than or equal to n that can be formed from these variables. We will ignore constant coefficients in this problem, except for the monomial of degree 0, which we will denote as 1. We will call such a polynomial a "full polynomial." For example, if n = 3 and the list of variables is [ x, y ], then the full polynomial, with its terms listed in graded order, is:

x³ + x²y + xy² + y³ + x² + xy + y² + x + y + 1

In this full polynomial, x³ is the 0th term, x²y is the 1st term, and 1 is the 9th term. Note that the number of terms in a full polynomial of degree n formed from m variables is given by:

C(n + m, m) = (n + m)! / (n! m!)

For n = 3 and m = 2, we have C(5, 2) = 5! / (3! 2!) = 10.

Given a list of variables, an integer n, and an index k, you are to return the String representation of the kth term in the full polynomial formed by these parameters, with its monomial terms sorted in graded order. The terms must be sorted by graded order before their positions are determined. The list of variables will be given as the String vars, where the ith character specifies the ith variable. The String representation of the monomial that should be returned is as follows.

1. If the degree of the monomial is 0, its representation is "1"
2. Otherwise, its representation is of the form "<var><var>...<var>", where <var> is the String representation of a variable and its power in the monomial. The vars must appear in the order that they appear in the vars parameter to getTerm, and are of the following form:
   1. If the power of the variable in the monomial is 0, it should be represented by the empty string (that is, not appear at all)
   2. If the power of the variable in the monomial is 1, it should be represented by only its name (e.g., "x")
   3. Otherwise, the variable should be represented as its name, followed by the '^' character, followed by its power, represented as a decimal integer with no leading zeros. For example, "x^2", "y^3", etc.