专栏文章

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

sshiruoyu114514
P14364题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minfgd2x
此快照首次捕获于
2025/12/02 01:32
3 个月前
此快照最后确认于
2025/12/02 01:32
3 个月前
查看原文
考虑从左往右进行填数，并且记录当前已经有多少个没有被录用的人。
初步令 dpi,jdp_{i,j} 为填完第 ii 个人的时候，有 jj 个人没有录用的方案数。此时会分成两类人：第一类是 c≤jc \le j 的——一定不会被录用。第二类是 c>jc > j 的：只有 si=0s_i=0 的时候才不会被录用。
令 SiS_i 为有多少个人的 c≤ic \le i，TiT_i 为有多少个人的 c=ic=i。
发现这玩意会假掉，毕竟你没法假定你需要从多少个第二类人中选一个。于是考虑这样的策略：每次要么填一个第一类人，要么填一个“空穴”，之后在第二类人转化为第一类人的时候往空穴里面补。
状态：令 dpi,j,kdp_{i,j,k} 为填完第 ii 个人之后，有 jj 个没有录用，有 kk 个空穴的方案数。
转移：
  1. si=1s_i=1
此时要么选择一个第一类人让没有被录用的人数 +1+1：
dpi+1,j+1,k−l←(Si−(i−k))(kl)(Tj+1l)l!dpi,j,kdp_{i+1,j+1,k-l} \leftarrow (S_i-(i-k))\binom{k}{l}\binom{T_{j+1}}{l}l!dp_{i,j,k}
要么填入一个空穴：
dpi+1,j,k+1←dpi,j,kdp_{i+1,j,k+1} \leftarrow dp_{i,j,k}
  1. si=0s_i=0
要么选择一个第一类人：
dpi+1,j+1,k−l←(Si−(i−k))(kl)(Tj+1l)l!dpi,j,kdp_{i+1,j+1,k-l} \leftarrow (S_i-(i-k))\binom{k}{l}\binom{T_{j+1}}{l}l!dp_{i,j,k}
要么填入一个空穴：
dpi+1,j+1,k−l+1←(k+1l)(Tj+1l)l!dpi,j,kdp_{i+1,j+1,k-l+1} \leftarrow \binom{k+1}{l}\binom{T_{j+1}}{l}l!dp_{i,j,k}
注意顺序可以认为：先填写，再填穴。此时上面转移的 ll 的范围可以达到 k+1k+1。
统计答案的时候，当没有被雇佣的人数达到 jj 的时候，cc 在 [j+1,n][j+1,n] 的所有人都没有考虑到。此时应该有 (Sn−Sj)(S_n-S_j) 个空穴让其填入，于是答案为：
∑i=mndpn,i,Sn−Si(Sn−Si)!\sum \limits_{i=m}^{n} dp_{n,i,S_n-S_i}(S_n-S_i)!
注意到对于一个 dpi,j,∗dp_{i,j,*} 而言，合法的 ll 至多 O(Tj+1)O(T_{j+1}) 个，而 ∑Tj=n\sum T_j=n，所以对于 dpi,∗,∗dp_{i,*,*} 而言，合法的转移是 O(n2)O(n^2) 级别的。于是时间复杂度为 O(n3)O(n^3)。
CPP
#include<bits/stdc++.h>

using namespace std;

#define int long long

constexpr int maxn=500;
constexpr int mod=998244353;

int dp[2][maxn+5][maxn+5];
int c[maxn+5];
int sum[maxn+5];
int ton[maxn+5];
string s;
int n,m;

int frac[maxn+5];
int inv[maxn+5];

int ksm(int a,int b){
	int ans=1;
	while(b){
		if(b&1){
			ans=ans*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}

void veradd(int& x,int y){
	x=x+y-(x+y>=mod)*mod;
}

int add(int x,int y){
	return x+y-(x+y>=mod)*mod;
}

int binom(int n,int m){
	return frac[n]*inv[m]%mod*inv[n-m]%mod;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cin>>n>>m;
	frac[0]=1;
	for(int i=1;i<=n;i++){
		frac[i]=frac[i-1]*i%mod;
	}
	inv[n]=ksm(frac[n],mod-2);
	for(int i=n-1;i>=0;i--){
		inv[i]=inv[i+1]*(i+1)%mod;
	}
	cin>>s;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		ton[x]++;
	}
	sum[0]=ton[0];
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+ton[i];
	}
	dp[0][0][0]=1;
	for(int i=0,p=0;i<n;i++,p^=1){
		for(int j=0;j<=i;j++){
			for(int k=0;k<=i;k++){
				if(!dp[p][j][k]){
					continue;
				}
				if(s[i]=='1'){
					veradd(dp[p^1][j][k+1],dp[p][j][k]);
					for(int l=0;l<=min(k,ton[j+1]);l++){
						veradd(dp[p^1][j+1][k-l],dp[p][j][k]*binom(k,l)%mod*binom(ton[j+1],l)%mod*frac[l]%mod*(sum[j]-(i-k))%mod);
					}
				}
				else{
					for(int l=0;l<=min(k+1,ton[j+1]);l++){
						veradd(dp[p^1][j+1][k+1-l],dp[p][j][k]*binom(k+1,l)%mod*binom(ton[j+1],l)%mod*frac[l]%mod);
					}
					for(int l=0;l<=min(k,ton[j+1]);l++){
						veradd(dp[p^1][j+1][k-l],dp[p][j][k]*(sum[j]-(i-k))%mod*binom(k,l)%mod*binom(ton[j+1],l)%mod*frac[l]%mod);
					}
				}
			//	cout<<i<<" "<<j<<" "<<k<<" "<<dp[p][j][k]<<"\n";
				dp[p][j][k]=0;
			}
		}
	}
	int ans=0,sm=0;
	for(int i=n;i>=0;i--){
		if(i<=n-m){
			veradd(ans,dp[n&1][i][sm]*frac[sm]%mod);
		}
		sm+=ton[i];
	}
	cout<<ans;
}

评论

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

正在加载评论...