题解

思路

每一行都是 $1\ldots n$ 的排列。固定上一行后，下一行必须在每一列都避开上一行对应的值，因此可选行数恒为 $n$ 阶错排数。按第一个与给定矩阵不同的位置统计字典序更小的矩阵即可。

做法

子任务 1：枚举全部矩阵

按字典序枚举每行的所有排列，递归生成所有美丽矩阵，直接统计严格小于给定矩阵的数量。复杂度为 $O((n!D_n^{n-1})n^2)$，适用于 $n\le3$。

子任务 2：子集 DP 补全当前行

枚举第一个不同位置 $(i,j)$ 和该位置填入的较小合法值。前 $i-1$ 行及第 $i$ 行前 $j$ 列已经固定。对当前行剩余位置做状态压缩 DP：状态记录已经使用的值，转移时避开上一行同列的值。后续每一行各有 $D_n$ 种选择。复杂度为 $O(n^4 2^n)$。

子任务 3：不完全错排与树状数组

记 $f_{i,j}$ 为 $i$ 个元素的排列中，有 $j$ 个指定位置禁止放指定元素时的方案数。容斥最后一个限制得到

特别地，$D_i=f_{i,i}$。

对第一行做康托展开，并乘上 $D_n^{n-1}$。对于其余每行，枚举第一个不同列。此时只需知道剩余位置中还有多少个“值与禁止位置同时存在”的限制；对应补全方案就是某个 $f_{k,r}$。

用两棵树状数组维护当前行已用值，以及上一行前缀中尚未被当前行使用的值。它们可以在 $O(\log n)$ 内求出比当前值小的两类候选数量，并维护限制数。每个位置据此贡献

再乘后续行的 $D_n$ 次幂并累加即可。

复杂度

预处理 $f$ 需要 $O(n^2)$ 时间和空间；矩阵排名需要 $O(n^2\log n)$ 时间、$O(n^2)$ 空间。