题解：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)

，但此时已经可以通过这道题了：

CPP

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

秒，所以我还额外卡了下常：

CPP

#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;
}

题解：AT_mujin_pc_2018_f チーム分け

文章操作

相关推荐

评论

题解：AT_mujin_pc_2018_f チーム分け