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

upd：转移 1 和转移 2 写反了，已修改。

第一次秒计数题，可惜

500^3

long long ，

100pts\to 0pts

。

直接 DP。

记

cnt_x=\sum_{i}{[c_i=x]}

，

sm_x

为

cnt_x

的前缀和。

@Lqh_xy 大神说，解决这种带权值排列的方法一般是从值域入手。

我们跟着大神走，

f_{i,j,k}

为

i

个人没通过，选取的人有

j

个

c\le i

，

k

个

c> i

，选了

(j+k)

个人的方案数，暂时忽略

k

的系数。

三种转移：

左边选了一个，转移到 $f_{i+1,j+1+x,k-x}$ ， $x$ 是 $cnt_{i+1}$ 取的个数，系数为 $(sm_i-j)\times \frac{cnt_{i+1}!}{(cnt_{i+1}-x)!}\times \binom{k}{x}$ 。
$s_{j+k+1}=0$ ，在右边选了一个，转移到 $f_{i+1,j+x,k+1-x}$ ， $x$ 是 $cnt_{i+1}$ 取的个数，转移系数为 $\frac{cnt_{i+1}!}{(cnt_{i+1}-x)!}\times \binom{k+1}{x}$ 。
选了右边的，直接转移到 $f_{i,j,k+1}$ ，系数为 $1$ 。

前两个转移需要枚举

x\le cnt_i

，总和为

n

，所以复杂度为

\mathcal{O}(n^3)

。

最后答案为

\sum_{i=0}^{i=n-m}{f_{i,sm_i,n-sm_i}\times (n-sm_i)!}

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll1;
const ll1 mod=998244353;
const int N=505;
ll1 fac[N],ifac[N];
ll1 ksm(ll1 x,ll1 y){ll1 res=1;for(;y;y>>=1,x=x*x%mod)if(y&1)res=res*x%mod;return res;}
void add(int &x,ll1 y){x=x+y<mod?x+y:x+y-mod;}
int n,m;
char s[N];
int cnt[N],sm[N];
int f[N][N][N];
//有 i 个没被录取，且 cnt\in[1,i] 的填了 j 个，其余填了 k 个。
//注意不算 k 的贡献！
ll1 C(ll1 x,ll1 y){
	if(x<0||y<0||x<y)return 0;
	return fac[x]*ifac[x-y]%mod*ifac[y]%mod;
}
ll1 A(ll1 x,ll1 y){
	if(x<0||y<0||x<y)return 0;
	return fac[x]*ifac[x-y]%mod;
}
int main(){
	//freopen("employ.in","r",stdin);
	//freopen("employ.out","w",stdout);
	n=500;
	fac[0]=ifac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
	ifac[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	for(int i=1,x;i<=n;i++)scanf("%d",&x),cnt[x]++;
	sm[0]=cnt[0];
	for(int i=1,x;i<=n;i++)sm[i]=sm[i-1]+cnt[i];
	memset(f,0,sizeof f);
	f[0][0][0]=1;
	for(int i=0;i<=n-m;i++)
	for(int j=0;j<=sm[i];j++)
	for(int k=0;k<=n-sm[i];k++){
		int nw=j+k+1;
		if(s[nw]=='0'){//不可录取。
			if(k<n-sm[i]){//你很强，但是你完了
				//i+1,枚举 k+1 分布在 i+1 的个数
				//->f[i+1][j+?][k+1-?]
				for(int c=0;c<=cnt[i+1]&&c<=k+1;c++)
					add(f[i+1][j+c][k+1-c],1ll*f[i][j][k]*A(cnt[i+1],c)%mod*C(k+1,c)%mod);
			}
		}else{//可以录取。
			if(k<n-sm[i])add(f[i][j][k+1],1ll*f[i][j][k]);
		}
		if(j<sm[i]){
			//菜鸡！它一定退役！
			//i+1，枚举 k 分布在 i+1 的个数
			//->f[i+1][j+1+?][k-?]
			for(int c=0;c<=cnt[i+1]&&c<=k;c++)
				add(f[i+1][j+1+c][k-c],1ll*f[i][j][k]*(sm[i]-j)%mod*1ll*A(cnt[i+1],c)%mod*1ll*C(k,c)%mod);
		}
	}
	int Ans=0;
	for(int i=0;i<=n-m;i++)add(Ans,1ll*f[i][sm[i]][n-sm[i]]*fac[n-sm[i]]%mod);
	printf("%d\n",Ans);
	return 0;
}

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

文章操作

相关推荐

评论

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