题解：AT_mujin_pc_2018_f チーム分け

神秘题目被神秘搬题人搬到 NOIP 模拟赛 T1。（所以模拟赛成了全原题模拟赛，难度：紫紫紫紫）

以为是签到题，做了 1h 30min 还是只会枚举。

可以考虑设计状态

f(i, j)

表示当前考虑了所有

a_k \ge i

的人，其中

j

人还未被匹配的方案数。

令

c(i)

为所有

a_k \ge i

的人的数量。

转移：考虑枚举

k

（当前新组成多少个人数为

i

的组），然后考虑转移的系数，很显然要首先从

j + c(i)

中选出

ki

个人，然后排列这

ki

个人成

k

组，但是会算重组内的排列和组间的排列方案数也就是

(i!)^k k!

。

f(i, j + c(i) - ki) \longleftarrow f(i + 1, j) \times \displaystyle\binom{j + c(i)}{ki} \frac{(ki)!}{(i!)^k k!}

注：转移可以化简为

f(i, j + c(i) - ki) \longleftarrow f(i + 1, j) \times \displaystyle \frac{j + c(i)}{(j + c(i) - ki)!(i!)^k k!}

\large{\mathbf{Code}}

CPP

123456789101112131415161718192021222324252627282930313233343536373839#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e3 + 10, mod = 998244353;
int n, x, cnt[N], f[N][N], fact[N], infact[N];
int qmi(int a, int k) {
	int res = 1;
	while(k) {
		if(k & 1) res = (LL)res * a % mod;
		a = (LL)a * a % mod;
		k >>= 1;
	}
	return res;
}
int main()
{
	scanf("%d", &n);
	fact[0] = infact[0] = 1;
	for(int i = 1; i <= n; i ++) {
		fact[i] = (LL)fact[i - 1] * i % mod;
		infact[i] = qmi(fact[i], mod - 2);
	}
	for(int i = 0; i < n; i ++) {
		scanf("%d", &x);
		cnt[x] ++;
	}
	f[n][0] = 1;
	for(int i = n; i; i --)
		for(int j = 0; j <= n; j ++)
			if(f[i][j]) {
				int v = j + cnt[i];
				int inv = (LL)f[i][j] * fact[v] % mod;
				for(int k = 0, t = 0; t <= v; k ++, t += i) {
					f[i - 1][v - t] = (f[i - 1][v - t] + (LL)inv * infact[k] % mod * infact[v - t] % mod) % mod;
					inv = (LL)inv * infact[i] % mod;
				}
			}
	printf("%d\n", f[0][0]);
	return 0;
}

题解：AT_mujin_pc_2018_f チーム分け

文章操作

相关推荐

评论

题解：AT_mujin_pc_2018_f チーム分け