CSP-S2025 员工招聘
设 \(f_{i,j,k}\) 表示考虑前 \(i\) 天，有 \(j\) 个人未录用，对于 \(c_p\le j\) 的 \(p\) 有 \(k\) 个填在 \([i+1,n]\)。设 \(cnt_x\) 表示 \(c_p=x\) 的数量，\(pre_x\) 为 \(cnt\) 的前缀和。
边界：\(f_{0,0,cnt_0}=1\)。
从 \(i\) 转移到 \(i+1\)。\([1,i]\) 中有 \(rest=i-pre_j+k\) 个空位。
-
从 \(k\) 个人中选一个填到 \(i+1\)，这时 \(j'=j+1\)，枚举 \(cnt_{j+1}\) 个数中有 \(l\) 个填在 \([i+1,n]\)：
\(f_{i,j,k}\times k\times A^{rest}_{cnt_{j+1}-l}\times \binom{cnt_{j+1}}l\to f_{i+1,j+1,k-1+l}\)
-
\(s_{i+1}=1\)，\(j'=j\)：
\(f_{i,j,k}\to f_{i+1,j,k}\)
-
\(s_{i+1}=0\)，\(j'=j+1\)，从 \(cnt_{j+1}\) 个数中选择一个填在 \(i+1\)，同样枚举 \(l\in [0,cnt_{j+1}-1]\)：
\(f_{i,j,k}\times cnt_{j+1}\times A^{rest}_{cnt_{j+1}-1-l}\times \binom{cnt_{j+1}-1}l\to f_{i+1,j+1,k+l}\)
-
\(s_{i+1}=0\)，\(j'=j+1\)，此时把 \(i+1\) 空出来不填，枚举 \(l\in [0,cnt_{j+1}]\)：
\(f_{i,j,k}\times A^{rest}_{cnt_{j+1}-l}\times \binom{cnt_{j+1}}l\to f_{i+1,j+1,k+l}\)
那么 \(Ans=\sum_{i=0}^{n-m}f_{n,i,0}\times (n-pr_i)!\)。时间复杂度 \(O(n^3)\)。
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N=505,mod=998244353;
int n,m,x,c[N],pr[N],a[N];
ll f[2][N][N],fc[N],iv[N];
void init(){iv[0]=iv[1]=fc[0]=1;for(int i=2;i<=n;i++) iv[i]=iv[mod%i]*(mod-mod/i)%mod;for(int i=1;i<=n;i++) fc[i]=fc[i-1]*i%mod,iv[i]=iv[i-1]*iv[i]%mod;
}
ll A(int n,int m){if(n<m) return 0;return fc[n]*iv[n-m]%mod;
}
ll C(int n,int m){if(n<m) return 0;return fc[n]*iv[n-m]%mod*iv[m]%mod;
}
char s[N];
void tr(ll &x,ll y){x+=y;if(x>=mod) x-=mod;
}
int main(){freopen("employ.in","r",stdin);freopen("employ.out","w",stdout);scanf("%d%d%s",&n,&m,s+1);for(int i=1;i<=n;i++) scanf("%d",&x),c[x]++;pr[0]=c[0];for(int i=1;i<=n;i++) pr[i]=pr[i-1]+c[i];init();f[0][0][c[0]]=1;for(int i=1;i<=n;i++){int u=i&1,v=u^1;memset(f[u],0,sizeof(f[u]));for(int j=0;j<i;j++)for(int k=0;k<=pr[j];k++){int rest=i-1-pr[j]+k;if(k){for(int l=0;l<=c[j+1];l++)tr(f[u][j+1][k-1+l],f[v][j][k]*k%mod*A(rest,c[j+1]-l)%mod*C(c[j+1],l)%mod);}if(s[i]=='1') tr(f[u][j][k],f[v][j][k]);else{for(int l=0;l<c[j+1];l++)tr(f[u][j+1][k+l],f[v][j][k]*c[j+1]%mod*A(rest,c[j+1]-1-l)%mod*C(c[j+1]-1,l)%mod);for(int l=0;l<=c[j+1];l++)tr(f[u][j+1][k+l],f[v][j][k]*A(rest,c[j+1]-l)%mod*C(c[j+1],l)%mod);}}}ll ans=0;for(int i=0;i<=n-m;i++)tr(ans,f[n&1][i][0]*fc[n-pr[i]]%mod);printf("%lld\n",ans);return 0;
}