题解

思路

若一个格子两个条件都不满足，那么它是所在列的最大值、所在行的最小值。

做法

这样的格子至多有一个：假设两个坏格位于不同行不同列，沿第一个坏格所在行、第二个坏格所在列比较可得第一个坏格小于第二个坏格；交换两者角色又会得到相反的不等式，产生矛盾。因此可以用全部 $(N^2)!$ 种填法减去恰有一个坏格的填法。

先选坏格的位置，共有 $N^2$ 种。它所在行与列的并集含 $2N-1$ 个格子，从所有数中选出填入这些格子的数有 $\binom{N^2}{2N-1}$ 种；其中第 $N$ 小的数必须放在坏格，较小的 $N-1$ 个数任意排列在同列，其余较大的 $N-1$ 个数任意排列在同行，剩余数任意填入其他格子。故坏填法数为 $N^2\binom{N^2}{2N-1}(N-1)!^2((N-1)^2)!$，答案为 $(N^2)!$ 减去它。

复杂度

顺次计算所需阶乘和组合数即可，时间复杂度为 $O(N^2)$，额外空间复杂度为 $O(1)$。