24000번 - Sherlock and Matrix Game 서브태스크다국어

문제

Today, Sherlock and Watson attended a lecture in which they were introduced to matrices. Sherlock is one of those programmers who is not really interested in linear algebra, but he did come up with a problem involving matrices for Watson to solve.

Sherlock has given Watson two one-dimensional arrays A and B; both have length N. He has asked Watson to form a matrix with N rows and N columns, in which the j^th element in the i^th row is the product of the i-th element of A and the j-th element of B.

Let (x, y) denote the cell of the matrix in the x-th row (numbered starting from 0, starting from the top row) and the y-th column (numbered starting from 0, starting from the left column). Then a submatrix is defined by bottom-left and top-right cells (a, b) and (c, d) respectively, with a ≥ c and d ≥ b, and the submatrix consists of all cells (i, j) such that c ≤ i ≤ a and b ≤ j ≤ d. The sum of a submatrix is defined as sum of all of the cells of the submatrix.

To challenge Watson, Sherlock has given him an integer K and asked him to output the K^th largest sum among all submatrices in Watson's matrix, with K counting starting from 1 for the largest sum. (It is possible that different values of K may correspond to the same sum; that is, there may be multiple submatrices with the same sum.) Can you help Watson?

입력

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line with nine integers N, K, A₁, B₁, C, D, E₁, E₂ and F. N is the length of arrays A and B; K is the rank of the submatrix sum Watson has to output, A₁ and B₁ are the first elements of arrays A and B, respectively; and the other five values are parameters that you should use to generate the elements of the arrays, as follows: First define x₁ = A₁, y₁ = B₁, r₁ = 0, s₁ = 0. Then, use the recurrences below to generate x_i and y_i for i = 2 to N:

• x_i = ( C*x_i-1 + D*y_i-1 + E₁ ) modulo F.
• y_i = ( D*x_i-1 + C*y_i-1 + E₂ ) modulo F.

Further, generate r_i and s_i for i = 2 to N using following recurrences:

• r_i = ( C*r_i-1 + D*s_i-1 + E₁ ) modulo 2.
• s_i = ( D*r_i-1 + C*s_i-1 + E₂ ) modulo 2.

We define A_i = (-1)^r_i * x_i and B_i = (-1)^s_i * y_i, for all i = 2 to N.

출력

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the K^th largest submatrix sum in the matrix defined in the statement.

제한

• 1 ≤ T ≤ 20.
• 1 ≤ K ≤ min(10⁵, total number of submatrices possible).
• 0 ≤ A₁ ≤ 10³.
• 0 ≤ B₁ ≤ 10³.
• 0 ≤ C ≤ 10³.
• 0 ≤ D ≤ 10³.
• 0 ≤ E₁ ≤ 10³.
• 0 ≤ E₂ ≤ 10³.
• 1 ≤ F ≤ 10³.

Test Set 1 (13점)

시간 제한: 40 초

• 1 ≤ N ≤ 200.

Test Set 2 (19점)

시간 제한: 200 초

• 1 ≤ N ≤ 10⁵.

힌트

In case 1, using the generation method, the generated arrays A and B are [1, -3] and [1, -3], respectively. So, the matrix formed is

[1, -3]
[-3, 9]

All possible submatrix sums in decreasing order are [9, 6, 6, 4, 1, -2, -2, -3, -3]. As K = 3, answer is 6. In case 2, using the generation method, the generated arrays A and B are [2] and [2], respectively. So, the matrix formed is

[4]

As K = 1, answer is 4. In case 3, using the generation method, the generated arrays A and B are [1, 0] and [2, -1] respectively. So, the matrix formed is

[2, -1]
[0, 0]

All possible submatrix sums in decreasing order are [2, 2, 1, 1, 0, 0, 0, -1, -1]. As K = 3, answer is 1.