Chess Rush
Contest: Central-European Olympiad in Informatics, CEOI 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated)
Difficulty rating: 3200
Tags: *special, combinatorics, dp, implementation, math

The mythic world of Chess Land is a rectangular grid of squares with $$$R$$$ rows and $$$C$$$ columns, $$$R$$$ being greater than or equal to $$$C$$$. Its rows and columns are numbered from $$$1$$$ to $$$R$$$ and $$$1$$$ to $$$C$$$, respectively.

The inhabitants of Chess Land are usually mentioned as pieces in everyday language, and there are $$$5$$$ specific types of them roaming the land: pawns, rooks, bishops, queens and kings. Contrary to popular belief, chivalry is long dead in Chess Land, so there are no knights to be found.

Each piece is unique in the way it moves around from square to square: in one step,

- a pawn can move one row forward (i.e. from row $$$r$$$ to $$$r+1$$$), without changing columns;
- a rook can move any number of columns left/right without changing rows OR move any number of rows forward/backward without changing columns;
- a bishop can move to any square of the two diagonals intersecting at its currently occupied square;
- a queen can move to any square where a rook or a bishop could move to from her position;
- and a king can move to any of the $$$8$$$ adjacent squares.

Recently, Chess Land has become a dangerous place: pieces that are passing through the land can get captured unexpectedly by unknown forces and simply disappear. As a consequence, they would like to reach their destinations as fast (i.e. in as few moves) as possible, and they are also interested in the number of different ways it is possible for them to reach it, using the minimal number of steps – because more paths being available could mean lower chances of getting captured. Two paths are considered different if they differ in at least one visited square.

For this problem, let us assume that pieces are entering Chess Land in a given column of row $$$1$$$, and exit the land in a given column of row $$$R$$$. Your task is to answer $$$Q$$$ questions: given the type of a piece, the column it enters row $$$1$$$ and the column it must reach in row $$$R$$$ in order to exit, compute the minimal number of moves it has to make in Chess Land, and the number of different ways it is able to do so.

Input format:
The first line contains three space-separated integers $$$R$$$, $$$C$$$, and $$$Q$$$ $$$(1 \leq Q \leq 1000$$$, $$$2 \leq C \leq 1000$$$ and $$$C \leq R \leq 10^9)$$$ – the number of rows and columns of Chess Land, and the number of questions, respectively. Then $$$Q$$$ lines follow.

Each line consists of

- a character $$$T$$$, corresponding to the type of the piece in question ('P' for pawn, 'R' for rook, 'B' for bishop, 'Q' for queen and 'K' for king);
- two integers $$$c_1$$$ and $$$c_R$$$, $$$1\leq c_1,c_R\leq C$$$, denoting that the piece starts from the $$$c_1$$$-th column of row $$$1$$$, and has to reach the $$$c_R$$$-th column of row $$$R$$$.

Output format:
You have to print $$$Q$$$ lines, the $$$i$$$-th one containing two space separated integers, the answer to the $$$i$$$-th question: the first one is the minimal number of steps needed, the second is the number of different paths available using this number of steps. Since the answer can be quite large, you have to compute it modulo $$$10^9+7$$$.

If it is impossible to reach the target square, output the line "0 0".

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
Scoring:
$$$ \begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & 0 & \text{samples}\\ \hline 2 & 8 & T\in\{\text{'P','R','Q'}\}\text{, i.e. all pieces are pawns, rooks or queens} \\ \hline 3 & 15 & T=\text{'B' and } \: C,R\leq 100 \\ \hline 4 & 22 & T=\text{'B'} \\ \hline 5 & 5 & T=\text{'K' and }\:C,R\leq 100\:\text{and}\:Q\leq 50 \\ \hline 6 & 8 & T=\text{'K' and }\:C,R\leq 100\\ \hline 7 & 15 & T=\text{'K' and }\:C\leq 100\\ \hline 8 & 20 & T=\text{'K'}\\ \hline 9 & 7 & \text{no additional constraints}\\ \hline \end{array} $$$

You can download the above example and an additional (bigger) sample input here: https://gofile.io/d/GDzwfC

Example input:
8 8 5
P 1 2
R 4 8
Q 2 3
B 3 6
K 5 5

Example output:
0 0
2 2
2 5
2 2
7 393

Editorial:
Pawns, Rooks and Queens
If $$$c_1=c_R$$$ then there is a unique shortest path, which takes $$$1$$$ step for the rook and the queen, and $$$R-1$$$ steps for the pawn. Otherwise, it is impossible getting to the exit square for the pawn, and it takes exactly $$$2$$$ steps for both the queen and the rook. It is also obvious that the latter can always do it in two different ways.
Therefore, we only have to be careful about enumerating the number of ways to do the required $$$2$$$ steps for the queen. She always has the same two paths as the rook available, plus we need to take into account all the options involving one or two diagonal moves. For these, we have to check if any path is blocked by the edges Chess Land, and also note that two diagonal moves are only possible if $$$1+c_1$$$ and $$$R+c_R$$$ have the same parity.
Bishops
First note that the bishop can reach its destination iff $$$1+c_1$$$ and $$$R+c_R$$$ have the same parity, otherwise the answer is $$$0$$$. For a small number of rows, a carefully implemented bruteforce evaluation can also solve the problem, but if $$$R$$$ is large, we need to be more thorough. It is useful to note that we can count the number of steps and paths separately for the cases when the bishops leaves the first row using the left diagonal and the right diagonal, and in the end, if one is shorter than the other then choose that one, and if they take the same number of steps, just sum them to get the answer.
Now, for a given starting direction, we can use a combinatorial argument to find the answer. First, imagine that we move forward in a greedy manner, bouncing between the left and right edges of Chess Land until we reach the last row in some impact column $$$c_I$$$. This way, we can jump $$$C-1$$$ rows forward before hitting a wall and having to move again, except the first and last moves, which are easy to handle. This gives us an initial guess for the number of steps. It is relatively easy to see that if $$$c_I=c_R$$$ then this shortest path is unique and the previously computed length is correct. Otherwise, there are two cases depending on how we arrive at the last row: for example, if we reach the last row while moving from left to right, and the target square is further to the right of $$$c_I$$$ (i.e. $$$c_I<c_R$$$), then the previous step length is once again correct, as we could have chosen to not go all the way to the edges in one or more previous step, which would increase the vaule of $$$c_I$$$ so we ensure $$$c_I=c_R$$$. However, if we reach the last row while moving from left to right, and the target square is to the left of $$$c_I$$$ (i.e. $$$c_R<c_I$$$ and we effectively "jump over" the requred destination), then we need to include one additional step into our path somewhere along the way in order to ensure $$$c_I=c_R$$$.
This way, we obtain the number $$$n$$$ of required steps, and the number $$$f$$$ of diagonal movements we can spare by stopping before hitting an edge, and we need to distribute them arbitrarily over $$$n-1$$$ steps, as we cannot stop during the last step. This is equivalent to the well-known combinatorial problem of distributing $$$f$$$ balls into $$$n-1$$$ boxes, but is also relatively easy to figure out that it is the combination $$$$$$  \binom{f+n-2}{f}. $$$$$$
Regarding the implementation of the solution, one has to be very careful about handling corner cases such as starting from the first or last column or arriving there, the direction of arrival and so. Note that in the formula above, $$$n-2$$$ can be $$$O(R/C)$$$ large which makes the evaluation a bit tricky when $$$C$$$ is small: notice that $$$$$$  \binom{f+n-2}{f} = \frac{(f+n-2)!}{f! (n-2)!} = \frac{(f+n-2)(f+n-3)\cdots (n-1)}{f!}, $$$$$$ which only has $$$O(f)$$$ terms and $$$f<C$$$, so we can answer all queries with $$$O(QC)$$$ time complexity.
We remark that alternately, the answers to all possible queries could be precomputed in $$$O(C^2)$$$ time, using the fact that while cycling through all the possible values of $$$c_R$$$ for a fixed $$$c_1$$$, the values $$$n$$$ and $$$f$$$ can change by at most $$$2$$$, making it possible to adjust the answer in constant time, but this is much more difficult to implement and was not required to pass.
Kings
It is easy to see that the king has to make exactly $$$R-1$$$ bottom-up moves, and if $$$|c_R-c_1|\leq R-1$$$, we need to advance one row in each step in order to have a shortest path. The other case, when $$$|c_R-c_1| > R-1$$$ means we need to advance one column towards the destination each step and have some free maneuverability between rows, can be solved seperately in a similar manner as the easiest case of the bottom-up problem, since this can only occur when $$$R<C$$$.
From now on, we assume $$$R\geq C$$$, so the king moves one row forward in each step and takes $$$R-1$$$ steps total, so we just need to count the number of paths. First, we observe that the number of ways we can reach the $$$j$$$-th column of a row is initially ways[c1]=1 and otherwise ways[j]=0 for the first row, and for any further row can be computed dynamically as
Next, we have to notice that with the same technique, we can precompute and store the answer for every $$$(c_1,c_R)$$$ pair, and answer each query in $$$O(1)$$$ time after, by adding another dimension to our dynamic programming: let DP[i][j] denote the number of ways to go from the $$$i$$$-th column of the first row to the $$$j$$$-th column of some current row, so initially we have DP[i][i] = 1 and every other entry is 0. Now we just repeat
Our next observation is to notice that at each iteration, instead of advancing a sinle row $$$r\to r+1$$$, we can choose to compute the answer for $$$r\to 2r-1$$$ instead. Indeed, our current DP array stores all the numbers of ways to get from the columns of the first row to the columns of the $$$r$$$-th row, or in other words, to advance $$$r$$$ rows forward. So if we want to count the number of ways to get from the $$$i$$$-th column of the first row to the $$$j$$$-th column of the $$$2r-1$$$-st row, we can enumerate all the possible paths going through the intermediate $$$k$$$-th column of the $$$r$$$-th row ($$$k=1,\ldots,C$$$) by the formula
Notice that the cost of advancing a single row was $$$O(C^2)$$$, so if we could somehow speed up the computation of $$$r\to 2r-1$$$ advancements too, then generating all answers for the king could be done in $$$O(C^2 \log R)$$$ time. There are multiple ways to do this step, but they all can be a bit tricky to find, so implementing a previous, less efficient approach and studying some of its outputs for small $$$C$$$ and different $$$R$$$ values could be very useful to figure out the main ideas and guess how a solution works.
First, the entries of double_DP[i][1], i.e. going from any column of the first row to a fixed column $$$j=0$$$, can be computed in $$$O(C^2)$$$ time, and since reversing the paths from the $$$i$$$-th to the $$$j$$$-th column gives exactly the paths from the $$$j$$$-th to the $$$i$$$-th column, double_DP[i][j] is symmetric and we obtain every double_DP[1][j] entry immediately.
Now suppose $$$1<i<j<C/2$$$ holds. The key observation is that we don't have to use the values of DP anymore, as the paths going from the $$$i$$$-th to the $$$j$$$-th column are almost the same as the paths going from the $$$i-1$$$-st column to the $$$j-1$$$-st column, shifted by a single column to the right. In fact, the relation