专栏文章

题解：P14364 [CSP-S 2025] 员工招聘 / employ（暂无数据）

220_200
P14364题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minfhtci
此快照首次捕获于
2025/12/02 01:33
3 个月前
此快照最后确认于
2025/12/02 01:33
3 个月前
查看原文
按照天的顺序加人。以下定义一个人未被录用为，该人主动放弃或者因为 si=0s_i=0 被拒绝。
当进行完 ii 天时，如果参与完面试的人已经有 jj 个未录用，那么后面所有 cx≤jc_x\le j 的人一定不会被录用，cx>jc_x>j 的人有可能被录用。所以对于每一个 0≤j≤n0\le j\le n 和所有 1≤x≤n1\le x\le n，定义 cx>jc_x>j 的是有用人，cx≤jc_x\le j 的是无用人。
设每个 jj 对应的有用人数量 dj=∑i=1n[ci≥j]d_j=\sum\limits_{i=1}^n[c_i\ge j]。
设计 dp 状态 fi,j,kf_{i,j,k} 表示进行完 ii 天面试，参与完面试的人已经有 jj 个未被录用，且所有参与完面试的 ii 个人中当前的有用人数量为 kk 时，只选择无用人的方案数。相当于有 kk 个空位留给有用人，具体是哪个人待定，先把无用人选了。
考虑从 fi−1,j,kf_{i-1,j,k} 如何转移到 fi,∗,∗f_{i,*,*} 。
第 ii 天如果选一个对于 jj 来说的无用人参加面试，那么完成后该人一定不会被录用，j←j+1j\gets j+1 。这个时候，原本那些 cx=j+1c_x=j+1 的人就从有用人变成了无用人，而这样的人有 dj+1−dj+2d_{j+1}-d_{j+2} 个。那么我们枚举有 yy 个 cx=j+1c_x=j+1 的人，在 fi−1,j,kf_{i-1,j,k} 的状态中被作为有用人参与面试，现在选择这些人之前留的填入空位。因为第 ii 天录用的是对于 jj 无用的人，所以对于 j+1j+1 也一定不会有用，不影响 cx=j+1c_x=j+1 的从有用变无用的转移。可以选的无用人有 (d0−dj+1−(i−1−k))(d_0-d_{j+1}-(i-1-k)) 个。
fi,j+1,k−y←fi−1,j,k×(d0−dj+1−(i−1−k))×(dj+1−dj+2y)×(ky)×y!f_{i,j+1,k-y}\gets f_{i-1,j,k}\times(d_{0}-d_{j+1}-(i-1-k))\times\binom{d_{j+1}-d_{j+2}}{y}\times\binom{k}{y}\times y!
第 ii 天如果选择一个有用人，那么 si=1s_i=1 的时候他会被录用，否则不会被录用。
si=1s_i=1 时，jj 不变，不会使得有用人变成无用人，并且添加一个有用人的时候只需留出位置不需计算方案数，那么转移是简单的。
fi,j,k+1←fi−1,j,kf_{i,j,k+1}\gets f_{i-1,j,k}
si=0s_i=0 时，j←j+1j\gets j+1。这个时候，应该先增加一个给 jj 对应的有用人的空位，即 k←k+1k\gets k+1。然后再考虑 cx=j+1c_x=j+1 的有用人变为无用人的时候，有多少个是属于 kk 的，使用和无用人的转移一样的方法，枚举有 yy 个 cx=j+1c_x=j+1 的人在 fi−1,j,kf_{i-1,j,k} 和当前 ii 选择的这个人的状态中被作为有用人参与面试。
fi,j+1,k+1−y←fi−1,j,k×(dj+1−dj+2y)×(k+1y)×y!f_{i,j+1,k+1-y}\gets f_{i-1,j,k}\times\binom{d_{j+1}-d_{j+2}}{y}\times\binom{k+1}{y}\times y!
最后统计答案，对于每个 jj，由于每个人都参与过一次了，所以 k=dj+1k=d_{j+1} 。这些未分配方案数的人任意排列即可。
ans=∑j=0n−mfn,j,dj+1×dj+1!ans=\sum\limits_{j=0}^{n-m}f_{n,j,d_{j+1}}\times d_{j+1}!
以上各条转移的取值范围，应该满足任何时刻任何变量（包括各种系数、下标、中间变量）都 ≥0\ge 0，并且 k≤min⁡(i,dj+1)k\le\min(i,d_{j+1})。
虽然有 i,j,k,yi,j,k,y 四层循环，但是由于 y≤dj+1−dj+2y\le d_{j+1}-d_{j+2}，所以 jj 和 yy 两个循环实际上只会计算 ∑(dj+1−dj+2)=d1=O(n)\sum(d_{j+1}-d_{j+2})=d_1=O(n) 次，因此时间复杂度是 O(n3)O(n^3) 的。
这也算是比较典的 dp 套路了。状态存不下且相互之间暂时没区别的东西，可以先留空，等到后面再算贡献。
注意事项
5003=1.25×108500^3=1.25\times 10^8，有取模阶乘组合数，1s 可能过不去。所以应该所有的循环都只在合法范围内做，并且只转移非 0 状态，这样常数极小，跑的飞快。
直接开 5003500^3 个 long long 类型会爆 512MB 内存限制，所以需要滚动数组优化空间。不知道有没有人因为这个 100→0100\to0 。
代码CPP
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pii pair<ll,ll>
#define ve vector<ll>
#define mid ((l+r)>>1)
#define lx (x<<1)
#define rx (x<<1|1)
using namespace std;
const ll N=502,P=998244353;
ll n,m,ans,d[N],fc[N],c[N][N],f[2][N][N];
string s;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>s,s=" "+s;
	for(ll i=1,x;i<=n;i++)cin>>x,d[x]++;
	for(ll i=n;i>=0;i--)d[i]+=d[i+1];
	f[0][0][0]=1;
	for(ll i=0;i<=n;i++){
		fc[i]=(i?fc[i-1]*i:1)%P;
		for(ll j=0;j<=i;j++)
			c[i][j]=(j?c[i-1][j]+c[i-1][j-1]:1)%P;
	}
	for(ll i=1;i<=n;i++){
		memset(f[i&1],0,sizeof(f[i&1]));
		for(ll j=0;j<i;j++)
			for(ll k=0;k<=min(i-1,d[j+1]);k++){
				ll t=i&1,x=f[!t][j][k];
				if(!x)continue;
				if(k<d[j+1]){
					if(s[i]=='1')(f[t][j][k+1]+=x)%=P;
					else for(ll y=max(k+1-d[j+2],0ll);y<=min(d[j+1]-d[j+2],k+1);y++)
						(f[t][j+1][k+1-y]+=x*c[d[j+1]-d[j+2]][y]%P*c[k+1][y]%P*fc[y])%=P;
				}
				if(i-1-k<d[0]-d[j+1])
					for(ll y=max(k-d[j+2],0ll);y<=min(d[j+1]-d[j+2],k);y++)
						(f[t][j+1][k-y]+=x*(d[0]-d[j+1]-(i-1-k))%P*c[d[j+1]-d[j+2]][y]%P*c[k][y]%P*fc[y])%=P;
			}
	}
	for(ll i=0;i<=n-m;i++)(ans+=f[n&1][i][d[i+1]]*fc[d[i+1]])%=P;
	cout<<(ans+P)%P;
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...