题解：AT_mujin_pc_2018_f チーム分け

· · 题解

神经 NOIP 模拟赛把这题放 T1，以为是道签到题结果两个小时才做出来，给我急死了。

首先因为 a 的顺序不重要，所以把 a 从大到小排序可以保证从前往后处理时，只有当前的 a_i 才是唯一真正的限制（前面已经处理过的限制不会在因为 a_i 而不合法之前就导致方案不合法）。这个 trick 应当是不难想到的。

然后是难点：发现这是一个 DP，并且设计出 DP 状态。（我是试出来的，大家不要学我。）

总之 DP 状态是：f(i, j) 表示前 i 个人中，对其中 j 个人分组的合法方案数。

枚举 i,j，对于 f(i, j) 的转移来源，首先考虑第 i 个人是否被算到这 j 个人当中。

如果不算，那么结果和 f(i - 1, j) 是一样的。

如果算，那么枚举 i 所在组的人数 k，此时 j - k 就是选出的 j 人中除去 i 所在组的人数。

接下来需要一些组合数知识，我们先把这剩下的 (j - k) 人分好组，方案为 f(i - 1, j - k)。接着我们需要在剩下的 (i - 1 - (j - k)) 人中选出 (k - 1) 个人与第 i 个人拼成一组，方案数为 \binom{i - 1 -(j - k)}{k - 1}。

这时事先把 a 从小到大排序的作用就体现出来了，这可以保证当前正在处理的 a_i 无论与前面的人怎么分组，这个 a_i 都一定是组内最小的。只要让 k \le a_i，就能保证组内所有人的条件都能满足。

综上所述，总的状态转移方程如下：

f(i,j) = f(i-1,j) + \sum_{k=1}^{\min(a_i,j)} f(i - 1, j - k) \times \binom{i - 1 - (j - k)}{k - 1}

直接计算的时间复杂度是 O(n^3)，但此时已经可以通过这道题了：

f[0][0] = 1;
for (int i = 1; i <= n; i++)
{
  f[i][0] = 1, f[i][1] = i;
  for (int j = 2; j <= i; j++)
  {
    f[i][j] = f[i - 1][j];
    for (int k = 1; k <= min(a[i], j); k++)
      (f[i][j] += f[i - 1][j - k] * C[i - 1 - (j - k)][k - 1]) %= MOD;
  }
}

但是模拟赛考场上毒瘤出题人搬题人不知道是不是为了卡 O(n^3)，把 n 开到了 2000，时间也缩减成了 1 秒，所以我还额外卡了下常：

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

typedef unsigned long long ULL;
constexpr int MAXN = 1005;
constexpr ULL MOD = 998244353;
int n, a[MAXN];

ULL f[MAXN][MAXN], C[MAXN][MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= i; j++)
            C[i][j] = j ? (C[i - 1][j] + C[i - 1][j - 1]) % MOD : 1;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1, greater<int>());
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        f[i][0] = 1, f[i][1] = i;
        for (int j = 2; j <= i; j++)
        {
            f[i][j] = f[i - 1][j];
            int ul = min(a[i], j);
            for (int k = 1, cnt = 0; k <= ul; k++)
            {
                f[i][j] += f[i - 1][j - k] * C[i - 1 - (j - k)][k - 1];
                if (++cnt == 17) f[i][j] %= MOD, cnt = 0;
            }
            f[i][j] %= MOD;
        }
    }
    cout << f[n][n] << '\n';
    return 0;
}