Beautiful Matrix
Contest: Technocup 2019 - Elimination Round 4
Difficulty rating: 2900
Tags: combinatorics, data structures, dp

Petya collects beautiful matrix.

A matrix of size $$$n \times n$$$ is beautiful if:

- All elements of the matrix are integers between $$$1$$$ and $$$n$$$;
- For every row of the matrix, all elements of this row are different;
- For every pair of vertically adjacent elements, these elements are different.

Today Petya bought a beautiful matrix $$$a$$$ of size $$$n \times n$$$, and now he wants to determine its rarity.

The rarity of the matrix is its index in the list of beautiful matrices of size $$$n \times n$$$, sorted in lexicographical order. Matrix comparison is done row by row. (The index of lexicographically smallest matrix is zero).

Since the number of beautiful matrices may be huge, Petya wants you to calculate the rarity of the matrix $$$a$$$ modulo $$$998\,244\,353$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2000$$$) — the number of rows and columns in $$$a$$$.

Each of the next $$$n$$$ lines contains $$$n$$$ integers $$$a_{i,j}$$$ ($$$1 \le a_{i,j} \le n$$$) — the elements of $$$a$$$.

It is guaranteed that $$$a$$$ is a beautiful matrix.

Output format:
Print one integer — the rarity of matrix $$$a$$$, taken modulo $$$998\,244\,353$$$.

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

Note:
There are only $$$2$$$ beautiful matrices of size $$$2 \times 2$$$:

There are the first $$$5$$$ beautiful matrices of size $$$3 \times 3$$$ in lexicographical order:

Example input:
2
2 1
1 2

Example output:
1

Example input:
3
1 2 3
2 3 1
3 1 2

Example output:
1

Editorial:
Calculate the following dp: $$$dp[n]$$$ — the number of permutations of length $$$n$$$ of elements $$$1 \dots n$$$ such that $$$p_i \ne i$$$ for every $$$i = 1 \dots n$$$
$$$dp[n] = (n - 1) \cdot (dp[n - 1] + dp[n - 2])$$$;
Calculate the following dp: $$$dp2[n][k]$$$ — the number of permutations of length $$$n$$$ of elements $$$1, 2, \dots, n, n + 1, n + 2, \dots, 2n - k$$$ such that $$$p_i \ne i$$$
$$$dp2[n][0] = n!$$$
$$$dp2[n][k] = dp2[n][k - 1] - dp2[n - 1][k - 1]$$$;
We can follow the usual process of recovering the lexicographic index. Iterate over the element to put in the current position and add the number of ways to complete the matrix to the answer.
How to calculate the number of ways to complete the matrix?
The current row can be completed the following way:
Look at the elements of the previous row (the same suffix as the one we want to complete), renumerate its elements into $$$1 \dots t$$$, where $$$t$$$ is the length of suffix. The current row now incudes some elements which appeared in the suffix of the previous row and some which don't. Let's renumerate those that appeared correspondingly. Let there be $$$k$$$ of such elements. Then the number of ways to complete the row is $$$dp2[t][k]$$$.
The other rows can be completed the following way:
For any row the previous one can be renumerated into permutation of form $$$1 \dots n$$$, thus the number of ways to choose the current row is $$$dp[n]$$$.
The only thing left is to raise $$$dp[n]$$$ to the power of the number of rows to be completed.
That solution is $$$O(N^3)$$$ as we were looking into all the candidates for the current position. However, these candidates can be split up into two groups: those that change the value of $$$k$$$ by 1 and those that leave it as is. Thus a single cell can be processed in $$$O(\log N)$$$ with a couple of data structures.