题目链接

题意：有一个$n \times m$的01矩阵，第$i$行的数之和为$A_i$，第$j$列的数之和为$B_j$，已知数组$B$的所有元素，求有多少种可能的数组$A$。模$10^9 + 7$。($1 \le n, m \le 50$)

先想如果给定数组$A$、$B$，如何判断是否合法。首先$A$的所有元素之和必定等于$B$的所有元素之和，记这个和为$x$。

之后使用网络流判断，建$n$个点表示行，起点向第$i$个点连容量$A_i$的边。建$m$个点表示列，第$i$个点向终点连容量$B_i$的边。之后表示行的每个点向表示列的每个点连容量为$1$的边。判断最大流是否为$x$即可。

观察这张图的最小割，假设起点连出去的边割了$i$条，连到终点的边割了$j$条，那一定是割了起点连出去容量最小的前$i$条边和连到终点的容量最小的前$j$条边，之后再割掉所有和起点或终点有边相邻的点之间的所有边。

设将$A$排序后的前缀和数组为$A’$，将$B$排序后的前缀和数组为$B’$，那么最小割为$\min \lbrace A’_i + B’_j + (n - i)(m - j) | 0 \le i \le n, 0 \le j \le m \rbrace$。

再考虑原问题，需要求有多少种$A$，满足所有数的和为$x$且上式的值为$x$。容易发现当$i = 0, j = m$时上式的值为$x$，那么只需要保证不存在一对$i, j$使得上式的值$< x$。

可以发现这个问题可以很方便的使用动态规划计算。设$f(i, j, k)$为已经确定了$A$中所有$\le i$的数及其位置关系，$A$中$\le i$的数共$j$个，$A’_j = k$的方案数。转移可以通过枚举$A$中有多少个$= i + 1$的数来实现。

复杂度$O(n^3m^2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
const int maxn = 50, mod = 1e9 + 7;
int n, m, f[maxn + 10][maxn + 10][maxn * maxn + 10], comb[maxn + 10][maxn + 10];
int a[maxn + 10], ans, minv[maxn + 10];

inline void addto(int &x, int y) {
	x += y; if (x >= mod) x -= mod;
}
inline int mul(int x, int y) {
	return 1ll * x * y % mod;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i <= n; ++i) {
		comb[i][0] = 1;
		for (int j = 1; j <= i; ++j) {
			addto(comb[i][j], comb[i - 1][j]);
			addto(comb[i][j], comb[i - 1][j - 1]);
		}
	}
	for (int i = 1; i <= m; ++i) scanf("%d", &a[i]);
	sort(a + 1, a + m + 1);
	for (int i = 1; i <= m; ++i) a[i] += a[i - 1];
	for (int i = 0; i <= n; ++i) {
		minv[i] = 1e9;
		for (int j = 0; j <= m; ++j)
			minv[i] = min(minv[i], a[j] + (n - i) * (m - j));
	}
	f[0][0][0] = 1;
	for (int i = 0; i <= m; ++i)
		for (int j = 0; j <= n; ++j)
			for (int k = 0; k <= n * m; ++k)
				if (f[i][j][k]) {
					int sum = k;
					for (int l = j; l <= n; ++l) {
						if (sum + minv[l] < a[m]) break;
						addto(f[i + 1][l][sum], mul(f[i][j][k], comb[l][j]));
						sum += i;
					}
				}
	printf("%d", f[m + 1][n][a[m]]);
}