EqualSums

作者：穆皓远 钟知闲

关键词： 排列 容斥原理 建图 枚举 不等式

题目简述

求满足如下条件的n行n列矩阵a的个数：

1.所有元素非负，即$a_{i,j}\ge0$

2.对于任意两个大小为n的排列p,q，有$\sum_{i=1}^na_{i,p_i}=\sum_{i=1}^na_{i,q_i}$

3.满足若干个形如$a_{i,j}=k$的条件

答案对1e9+7取模

题目保证不会有无穷多个解

$1\le n\le 50,0\le\forall k\le 9$

算法一

排列可以转化为若干个对换，条件2可化简为$a_{i,j}+a_{k,l}=a_{i,l}+a_{k,j}$，即$a_{i,j}-a_{i,l}=a_{k,l}-a_{k,j}$

容易发现$a$可以由$a_{i,1}$和$a_{i,j}-a_{i,j-1}$唯一确定

但是这样并不容易解决非负的限制，考虑设$a_{i,j}=b_i+c_j$

事实上，对于一个特定的$a$，这样的$b_i,c_j$有无数对，我们取$min\{b_i\}=0$作为解

由$min\{b_i\}=0$，可得$a_{i,j}=b_i+c_j\ge min\{b_i\}+c_j=c_j\ge 0$

所以只需$b_i,c_j$均非负，条件1也就迎刃而解

对于条件3，我们可以使用一个常用技巧，$b_i和-c_j$连边来表示约束，这样对于每个连通块分别求解再相乘就是答案

而对于每个连通块，我们任取一个元素，枚举它的大小（注意大小不会超过$max\{k\}$），同时判整个连通块是否合法即可

不过到此为止我们并未保证$min\{b_i\}=0$，考虑使用容斥原理，用类似的做法减掉$min\{b_i\}>0$的情况即可

时间复杂度$O(n^2*max\{k\})$

空间复杂度$O(n^2)$

算法二

算法一最后涉及枚举元素，与$max\{k\}$的大小相关，可以考虑设出连通块某个元素，再将其它元素用该元素表示，直接解出该元素的范围即可

时间复杂度$O(n^2)$

空间复杂度$O(n^2)$

算法三

以上两种算法均可用并查集替换掉搜索，不过输入本身就是$O(n^2)$的所以意义不大……

算法四

考虑一种新的想法。

首先根据之前的结论，条件2等效于对任意 $1\le i,j\le n$，每一行 $x$ 的 $a_{x,i}-a_{x_j}$ 都相同。转化完以后我们就不需要行数和列数相同的条件了。

既然这题最麻烦的是非负性限制，那么能不能通过调整矩阵使问题变简单呢？假如有一列 $i$ 有两个位置 $a_{x,i},a_{y,i}$ 非空（非空的意思是存在条件3的约束），其中 $a_{x,i}\le a_{y,i}$，这时候行 $y$ 的每一列的数都不比行 $x$ 小（意味着不需要对行 $y$ 限制非负性，只限制了列的差），能不能直接把行 $y$ 合并到行 $x$ 里面去呢？

可以！如果已确定了 $a_{y,j}=k$，那么就确定了 $a_{x,j}=k+a_{x,i}-a_{y,i}$，一旦矛盾或出负数则无解返回 $0$。之后就可以把行 $y$ 删掉了。也许你会问：这样会不会丢条件呢？不会！因为这一行不需要约束非负性，所有约束都形如“某两列的差为某定值”，把约束移到行 $x$ 上，所有约束都保留下来了。这样我们合并一些行使得每列只有一个数确定，再合并一些列使得每行只有一个数（显然不可能有空行或空列，否则有无穷多解）。为了方便处理，把第一行的数所在的列交换到第一列（不难说明交换行列不影响答案）。

现在问题就简单多了。记现在有 $n$ 行，$a_i$ 为第 $i$ 列唯一已确定的数，$x_i$ 为第一行第 $i$ 列的数，这时枚举第一行最左边的最小值位置 $m$，以 $m > 1$ 为例，要求 $x_m < a_1$，$x_i > x_m(i < m)$，$x_i\ge x_m(i > m)$，同时只需对所有 $j > 1$ 限制 $a_j$ 所在行最小值 $x_m+a_j-x_j\ge 0$。化简得到 $x_m < x_i\le x_m+a_j(i < m)$，$x_m\le x_i\le x_m+a_j(i > m)$。（$m=1$ 的推导类似）所以方案数为 $\sum_{m=1}^na_1a_2...a_{m-1}(a_{m+1}+1)(a_{m+2}+1)...(a_n+1)$。

合并行列次数不超过 $O(n)$，每次需要 $O(n)$ 时间，计算方案数可以做到 $O(n)$（就算 $O(n^2)$ 也没关系），最终复杂度是 $O(n^2)$。