证明

给定两个非负整数数列 \(p_1 \ge p_2 \ge \dots \ge p_n\) 以及 \(q_1 \ge q_2 \ge \dots \ge q_m\) 满足 \(\sum_{i = 1}^n p_i = \sum_{i = 1}^m q_i\)，存在一个简单二分图使得左部点的度数分别为 \(p_1, p_2, \dots, p_n\)、右部点的度数分别为 \(q_1, q_2, \dots, q_m\) 的充要条件为 \(\forall k \in [1, n], \sum_{i = 1}^k p_i \le \sum_{i = 1}^m \min\{q_i, k\}\)。

必要性

记该二分图的左部点为 \(x_1, x_2, \dots, x_n\)、右部点为 \(y_1, y_2, \dots, y_m\)，不妨设 \(\forall i \in [1, n], deg(x_i) = p_i, \forall i \in [1, m], deg(y_i) = q_i\)。

对于左部的任意 \(k\) 个点，考察它们的度数之和。对于每一个右部点 \(y_i\)，它最多和左部的 \(k\) 个点中的 \(\min\{q_i, k\}\) 个有边相连。因此左部任意的 \(k\) 个点度数之和 \(\le \sum_{i = 1}^m \min\{q_i, k\}\)。

所以 \(\forall k \in [1, n], \sum_{i = 1}^k p_i \le \sum_{i = 1}^m \min\{q_i, k\}\)。

充分性

考虑归纳构造出该二分图。

若我们已经构造出一个简单二分图满足 \(deg(x_k) < p_k, \forall i \in [1, k - 1], deg(x_i) = p_i, \forall i \in [k + 1, n], deg(x_i) = 0, \forall i \in [1, m], deg(y_i) \le q_i\)，考虑如何添加或修改若干条边使得 \(deg(x_k) \leftarrow deg(x_k) + 1\)，且除了 \(deg(x_k) < p_k\) 以外的所有条件仍然满足。

我们必然能找到一个 \(y_a\) 使得 \(deg(y_a) < \min\{q_a, k\}\)，否则 \(\sum_{i = 1}^k p_i > deg(x_k) + \sum_{i = 1}^{k - 1} p_i = \sum_{i = 1}^m deg(y_i) = \sum_{i = 1}^m \min\{q_i, k\}\)，矛盾。

如果还没有边 \((x_k, y_a)\)，则加入该边。

否则根据抽屉原理，必然存在 \(b \in [1, k - 1]\) 使得没有边 \((x_b, y_a)\)。又因为 \(deg(x_b) = p_b \ge p_k > deg(x_k)\)，所以一定存在 \(y_c\) 使得有边 \((x_b, y_c)\)、没有边 \((x_k, y_c)\)。删去边 \((x_b, y_c)\)，加入边 \((x_b, y_a), (x_k, y_c)\)。

不难发现上述操作是使得 \(deg(x_k) \leftarrow deg(x_k) + 1\) 的一个合法构造。

初始 \(k = 1, \forall i \in [1, n], deg(x_i) = 0\)，当 \(deg(x_k) < p_k\) 时不断调用上述构造，然后令 \(k \leftarrow k + 1\)。此时若 \(k = n + 1\) 则我们已经构造出一个满足条件的二分图。

容易发现上述充分性的构造实际上是在模拟网络流的增广路算法。

例题

CF1740F

观察发现最后 \(\{a_i\}\) 划分成的每一个集合中数两两不同，并且每一种集合中数两两不同的划分方案都可以通过题目中的操作构造出来。

设 \(\{a_i\}\) 中值为 \(x\) 的数有 \(b_x\) 个，可以发现 \(M\) 能被构造出来的充要条件是能够构造出一个二分图使得左部点的度数可重集为 \(\{b_i\}\)，右部点的度数可重集为 \(M\)。

考虑使用 Gale-Ryser 定理进行判定，即将 M 中的数从大到小排序后每一个前缀和都需要满足一个上限。\(dp_{i, j, k}\) 表示从大到小写了 \(i\) 个数，和为 \(j\)，最后一个数为 \(k\) 的方案数。

因为 \(k \le \frac{j}{i}\)，所以状态数是 \(O(n^2 \log n)\) 的。直接枚举上一个数转移时间复杂度 \(O(n^3 \log n)\)，可以前缀和优化成 \(O(n^2 \log n)\)。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128;
using u128 = unsigned __int128;
template <typename T>
void chkmax(T &x, const T &y) {
  if (x < y) x = y;
}
template <typename T>
void chkmin(T &x, const T &y) {
  if (y < x) x = y;
}
constexpr int MAXN = 2010, MOD = 998244353;
void inc(int &x, int y) { x += y, x >= MOD && (x -= MOD); }
int add(int x, int y) { return x += y, x >= MOD ? x - MOD : x; }
int n, a[MAXN], lim[MAXN], dp[MAXN][MAXN], suf[MAXN][MAXN];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for (int i = 1, x; i <= n; ++i) {
    cin >> x;
    ++a[x];
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) lim[i] += min(a[j], i);
  for (int i = 1; i <= lim[1]; ++i) dp[i][i] = 1;
  int ans = (lim[1] == n);
  for (int i = 2; i <= n; ++i) {
    for (int j = i - 1; j <= lim[i - 1]; ++j) {
      int up = j / (i - 1);
      suf[j][up] = dp[j][up];
      for (int k = up - 1; k >= 1; --k) suf[j][k] = add(suf[j][k + 1], dp[j][k]);
    }
    for (int j = i; j <= lim[i]; ++j) {
      for (int k = 1; k * i <= j; ++k)
        dp[j][k] = (j - k <= lim[i - 1] ? suf[j - k][k] : 0);
    }
    if (lim[i] == n)
      for (int k = 1; k * i <= n; ++k) inc(ans, dp[n][k]);
  }
  cout << ans << "\n";
  return 0;
}
// g++ CF1470F.cpp -o CF1470F -Wall -Wextra -Wshadow -O2 -std=c++14 -fsanitize=address,undefined