P16625 [GKS 2017 #D] 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^\text{th}$ element in the $i^\text{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 \ge c$ and $d \ge b$, and the submatrix consists of all cells $(i, j)$ such that $c \le i \le a$ and $b \le j \le 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^\text{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_1$, $B_1$, $C$, $D$, $E_1$, $E_2$ and $F$. $N$ is the length of arrays $A$ and $B$; $K$ is the rank of the submatrix sum Watson has to output, $A$$_1$ and $B$$_1$ 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_1 = A_1$, $y_1 = B_1$, $r_1 = 0$, $s_1 = 0$. Then, use the recurrences below to generate $x_i$ and $y_i$ for $i = 2$ to $N$: - $x_i = (C \times x_{i-1} + D \times y_{i-1} + E_1) \pmod{F}$. - $y_i = (D \times x_{i-1} + C \times y_{i-1} + E_2) \pmod{F}$. Further, generate $r_i$ and $s_i$ for $i = 2$ to $N$ using following recurrences: - $r_i = (C \times r_{i-1} + D \times s_{i-1} + E_1) \pmod{2}$. - $s_i = (D \times r_{i-1} + C \times s_{i-1} + E_2) \pmod{2}$. We define $A_i = (-1)^{r_i} \times x_i$ and $B_i = (-1)^{s_i} \times 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^\text{th}$ largest submatrix sum in the matrix defined in the statement.

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 $$\begin{aligned} &[1, \ -3] \\ &[-3, \ 9] \end{aligned}$$ 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 $$\begin{aligned} &[4] \end{aligned}$$ 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 $$\begin{aligned} &[2, \ -1] \\ &[0, \ 0] \end{aligned}$$ All possible submatrix sums in decreasing order are [2, 2, 1, 1, 0, 0, 0, -1, -1]. As **K = 3**, answer is 1. ### Limits $1 \le T \le 20$. $1 \le K \le \min(10^5, \text{total number of submatrices possible})$. $0 \le A_1 \le 10^3$. $0 \le B_1 \le 10^3$. $0 \le C \le 10^3$. $0 \le D \le 10^3$. $0 \le E_1 \le 10^3$. $0 \le E_2 \le 10^3$. $1 \le F \le 10^3$. **Small dataset (Test set 1 - Visible)** $1 \le N \le 200$. **Large dataset (Test set 2 - Hidden)** $1 \le N \le 10^5$.