【矩阵序列转换】20260825C 魔法阵 笔记

给定 $n,m$，求任意大小的、满足以下条件的矩阵 $a$ 的方案数。

1. $a_{i,j}\ge m$；
2. 设 $p,q$ 是任意两个不同的 $[1,n]$ 排列，$\sum a_{i,p_i}=\sum a_{i,q_i}$
3. $\sum a_{i,i}\le n$
4. $a$ 的行数等于列数。

从条件 2 入手，可得对于任意 $i,j,x,y$，$a_{i,x}+a_{j,y}=a_{i,y}+a_{j,x}$，按字母归类可得 $a_{i,x}-a_{i,y}=a_{j,x}-a_{j,y}$，即任意两行的差分序列相同，同理可得任意两列的差分序列相同。

所以可以构造两个序列 $A,B$，使得 $a_{i,j}=A_i+B_j$ 来表示矩阵 $a$，那么这两个序列要满足：

1. $min{A}_i+min{B}_i\ge m$。
2. $\sum (A_i+B_i)\le n$。

可以发现对 $A$ 整体 $-1$，对 $B$ 整体 $+1$，构造的 $a$ 不变，因此可以令条件一变为 $min{A}_i=0,min{B}_i\ge m$。

对 $B_i$ 整体 $-m$，令 $n$ 减去 $im$ 即可转换为 $min{A}_i=0,min{B}_i\ge 0$，插板法 $O(1)$，因此枚举矩阵的大小即可。