专栏文章

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

CCoffee_zzz/xin
P14364题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@min1rsjg
此快照首次捕获于
2025/12/01 19:09
3 个月前
此快照最后确认于
2025/12/01 19:09
3 个月前
查看原文
设集合 U={i∣si=1}U=\{i \mid s_i=1\}，考虑钦定一个集合 S⊆US \subseteq U，满足：
  • 对于所有 i∈Si\in S，第 ii 个位置的人会被录取，即要求 ci>∑j=1i−1[j∉S]c_i \gt \sum\limits_{j=1}^{i-1} [j \notin S]；
  • 对于所有 i∈U∖Si\in U\setminus S，第 ii 个位置的人不会被录取，即要求 ci≤∑j=1i−1[j∉S]c_i \le \sum\limits_{j=1}^{i-1} [j \notin S]。
考虑容斥，把第一个条件的形式与第二个条件统一。具体地，钦定一个集合 T⊆ST \subseteq S，满足：
  • 对于所有 i∈Ti \in T，第 ii 个位置的人不会被录取，即要求 ci≤∑j=1i−1[j∉S]c_i \le \sum\limits_{j=1}^{i-1} [j \notin S]；
  • 对于所有 i∈S∖Ti \in S\setminus T，第 ii 个位置的人没有要求。
容斥系数为 (−1)∣T∣(-1)^{|T|}。
考虑从前往后 dp。设 fi,j,kf_{i,j,k} 表示，考虑到第 ii 个位置，此时一共有 jj 个数在 SS 中，kk 个数在 TT 中，且仅考虑 T∪(U∖S)T \cup (U \setminus S) 中的位置填的数的方案数。初始化 f0,0,0=1f_{0,0,0}=1，设 ai=∑j=1n[cj≤i]a_i=\sum\limits_{j=1}^n [c_j \le i]，bi=∑j=1i[sj=1]b_i=\sum\limits_{j=1}^i [s_j=1]，考虑转移：
  • 若 si+1=0s_{i+1}=0，fi+1,j,k←fi,j,kf_{i+1,j,k} \leftarrow f_{i,j,k}；
  • 若 si+1=1s_{i+1}=1：
    • 令 i+1∈U∖Si+1 \in U\setminus S，fi+1,j,k←fi+1,j,k+fi,j,k×(ai−j−k−bi+j)f_{i+1,j,k} \leftarrow f_{i+1,j,k}+f_{i,j,k} \times (a_{i-j}-k-b_i+j)；
    • 令 i+1∈S∖Ti+1 \in S\setminus T，fi+1,j+1,k←fi+1,j+1,k+fi,j,kf_{i+1,j+1,k} \leftarrow f_{i+1,j+1,k}+f_{i,j,k}；
    • 令 i+1∈Ti+1 \in T，fi+1,j+1,k+1←fi+1,j+1,k+1+fi,j,k×(ai−j−k−bi+j)f_{i+1,j+1,k+1} \leftarrow f_{i+1,j+1,k+1}+f_{i,j,k} \times (a_{i-j}-k-b_i+j)。
其中，系数为 ai−j−k−bi+ja_{i-j}-k-b_i+j 的原因是：当前位置填的数需要小于等于 i−ji-j，且之前已经用了 k+bi−jk+b_i-j 个这样的数。
答案即为 ∑j=mn∑k=0jfn,j,k×(−1)k×(n−bn+j−k)!\sum\limits_{j=m}^n \sum\limits_{k=0}^j f_{n,j,k} \times (-1)^k \times (n-b_n+j-k)!，其中 n−bn+j−kn-b_n+j-k 是满足 i∉T∪(U∖S)i \notin T \cup (U \setminus S) 的 ii 的数量，这些位置上的数可以任意排列。
使用滚动数组优化，空间复杂度 O(n2)\mathcal O(n^2)，时间复杂度 O(n3)\mathcal O(n^3)。
C
const int N=505,mod=998244353;
int n,m,c[N],s[N],a[N],b[N],f[2][N][N],fac[N],ans;
string str;
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
void solve(){
	cin>>n>>m>>str;
	for(int i=1;i<=n;i++) cin>>c[i],a[c[i]]++;
	for(int i=1;i<=n;i++) s[i]=(str[i-1]=='1'),b[i]=b[i-1]+s[i];
	for(int i=0;i<=n;i++) a[i]+=a[i-1];
	f[0][0][0]=1,fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=0;i<n;i++){
		int t=i&1;
		memset(f[t^1],0,sizeof f[t^1]);
		for(int j=0;j<=b[i];j++){
			for(int k=0;k<=j;k++){
				if(s[i+1]==0) add(f[t^1][j][k],f[t][j][k]);
				else{
					add(f[t^1][j+1][k],f[t][j][k]);
					int x=a[i-j]-k-b[i]+j;
					add(f[t^1][j][k],1ll*f[t][j][k]*x%mod);
					add(f[t^1][j+1][k+1],1ll*f[t][j][k]*x%mod);
				}
			}
		}
	}
	for(int j=m;j<=b[n];j++){
		for(int k=0;k<=j;k++){
			int x=n-b[n]+j-k;
			if(k&1) add(ans,mod-1ll*f[n&1][j][k]*fac[x]%mod);
			else add(ans,1ll*f[n&1][j][k]*fac[x]%mod);
		}
	}
	cout<<ans<<endl;
}

评论

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

正在加载评论...