Codeforces #589 E. Another Filling the Grid

https://codeforces.com/contest/1228/problem/E

I used inclusion-exclusion principle. Let R_i be the event that the minimum of i-th row is not 1, and C_i is similarly defined. Then the answer is can be written as

\begin{align}
| \overline{R_1} \cap \cdots \cap \overline{R_N} \cap \overline{C_1} \cap \cdots \cap \overline{C_N} |
\end{align}

It can be decomposed into several terms by inclusion exclusion. For example, for N=5, the following term will appear.

\begin{align}
-| R_4 \cap C_1 \cap C_4 |
\end{align}

This means that 4th row, 1st col and 4th col should be taken from the set {2 ... K}. That is the filled area should be 2..K.

The number of such a pattern is $(K - 1)^{xN + yN - xy} \times K^{(N - x)(N - y)}$ where x=1 (it corresponds to the number of factors of the form $R_*$) and y=2 (it corresponds to the number of factors of the form $C_*$). By this, the answer is equal to

\begin{align}
\sum_{x=0}^{N} \sum_{y=0}^{N} (-1)^{x+y} \binom{N}{x} \binom{N}{y} (K - 1)^{xN + yN - xy} K^{(N - x)(N - y)}.
\end{align}

The time complexity is O(N^2) naively. But it can also be computed in O(N log MOD).