P14364 [CSP-S 2025] 员工招聘 / employ

我场上最后 30min 想到了的！！！但是一堆分讨没时间了/ll

思路：

你发现排列的计数，一般状态是重点；这题对排列的限制在

c

这里，于是考虑把

c

这个东西压进状态里。

于是想到

dp_{i, j, k}

表示考虑前

i

天，前面有

j

个人 fail 了，然后其中有

k

个人

c > j

的方案数（此时这些人具体是谁是没有必要的，因为只要他的

c > j

就不会造成影响），于是前面

i

天选了

i - k

个

c \le j

的，进行分讨（这里设

w_i

表示

c

等于

i

的人的数量，

s_i

表示

c

小于等于

i

的人的数量）：

若 $s_{i} = 1$ ：

此时若放一个 $c \le j$ 的人来，方案数是 $w_j - i + k + 1$ ，它会 fail，那么会使 $j \gets j + 1$ ，然后 $k$ 的变化不太清楚，所以考虑枚举前面恰好选了 $l$ 个 $c$ 是 $j + 1$ 的： $dp_{i - 1, j, k} (s_j - i + k + 1) \binom{w_{j + 1}}{l} \binom{k}{l} l! \to dp_{i, j + 1, k - l}$
否则放一个 $c > j$ 的人来，于是 $j$ 不变， $k$ 加一： $dp_{i - 1, j, k} \to dp_{i, j, k + 1}$

若 $s_i = 0$ ：

此时随便放一个都是 fail，所以 $j \gets j + 1$ ，同时也要枚举前面恰好选了 $l$ 个 $c$ 是 $j + 1$ 的，于是考虑若放 $c \le j + 1$ 进来，方案数是 $s_{j + 1} - i + k + 1 - l$ ： $dp_{i - 1, j, k} (s_{j + 1} - i + k + 1 - l) \binom{w_{j + 1}}{k} \binom{k}{l} l! \to dp_{i, j + 1, k - l}$
若是放 $c > j + 1$ 进来，则 $k$ 要多加 $1$ ：

dp_{i - 1, j ,k} \binom{w_{j + 1}}{k} \binom{k}{l} l ! \to dp_{i, j + 1, k - l + 1}

你发现所有枚举的

\sum l = n

，于是时间复杂度是

O(n^3)

的。

完整代码：

CPP

#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 505, mod = 998244353;
inline ll read(){
	ll x = 0, f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-')
			f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = (x << 1) + (x << 3) + (c ^ 48);
		c = getchar();
	}
	return x * f;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}
int n, m, ans;
int dp[N][N][N], w[N], s[N], C[N][N], fac[N];
char op[N];
int c[N];
inline void getadd(int &x, int y){
	x = (x + y >= mod) ? (x + y - mod) : (x + y);
}
inline int add(int x, int y){
	return (x + y >= mod) ? (x + y - mod) : (x + y);
}
bool End;
int main(){
	n = read(), m = read();
	scanf("%s", op + 1);
	for(int i = 1; i <= n; ++i){
		c[i] = read();
		++w[c[i]];
	}
	fac[0] = 1;
	s[0] = w[0];
	for(int i = 1; i <= n; ++i){
		s[i] = s[i - 1] + w[i];
		fac[i] = 1ll * fac[i - 1] * i % mod;
//		cerr << s[i] << ' ';
	}
	for(int i = 0; i <= n; ++i){
		C[i][0] = 1;
		for(int j = 1; j <= i; ++j)
		  C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
	}
	dp[0][0][0] = 1;
	for(int i = 1; i <= n; ++i){
		for(int j = 0; j <= i - 1; ++j){
			for(int k = 0; k <= i - 1; ++k){
				if(!dp[i - 1][j][k])
				  continue;
//				cerr << "Yes\n" << ' ' << i - 1 << ' ' << j << ' ' << k << ' ' << dp[i - 1][j][k] << '\n';
				if(op[i] == '1'){
//					if(s[j] != n)
//					cerr << i << ' ' << j << ' ' << k + 1 << '\n';
					getadd(dp[i][j][k + 1], dp[i - 1][j][k]);
					if(s[j] - i + k + 1 < 0)
					  continue;
					for(int l = 0; l <= min(k, w[j + 1]); ++l)
					  getadd(dp[i][j + 1][k - l], 1ll * dp[i - 1][j][k] * (s[j] - i + k + 1) % mod * C[w[j + 1]][l] % mod * C[k][l] % mod * fac[l] % mod);
				}
				else{
					for(int l = 0; l <= min(k, w[j + 1]); ++l){
//						if(s[j + 1] != n)
						getadd(dp[i][j + 1][k - l + 1], 1ll * dp[i - 1][j][k] * C[w[j + 1]][l] % mod * C[k][l] % mod * fac[l] % mod);
						if(s[j + 1] - i + k + 1 - l > 0)
						  getadd(dp[i][j + 1][k - l], 1ll * dp[i - 1][j][k] * (s[j + 1] - i + k + 1 - l) % mod * C[w[j + 1]][l] % mod * C[k][l] % mod * fac[l] % mod);
					}
				}
			}
		}
	}
	for(int i = 0; i <= n - m; ++i)
	  getadd(ans, 1ll * fac[n - s[i]] * dp[n][i][n - s[i]] % mod);
	write(ans);
//chrr << '\n' << abs(&Bhgin - &End) / 1048576 << "MB";
	return 0;
}

P14364 [CSP-S 2025] 员工招聘 / employ

文章操作

思路：

完整代码：

相关推荐

评论

P14364 [CSP-S 2025] 员工招聘 / employ