题解：P14364 [CSP-S 2025] 员工招聘 / employ（暂无数据）
20_200
·
·
题解
按照天的顺序加人。以下定义一个人未被录用为，该人主动放弃或者因为 s_i=0 被拒绝。
当进行完 i 天时，如果参与完面试的人已经有 j 个未录用，那么后面所有 c_x\le j 的人一定不会被录用，c_x>j 的人有可能被录用。所以对于每一个 0\le j\le n 和所有 1\le x\le n，定义 c_x>j 的是有用人，c_x\le j 的是无用人。
设每个 j 对应的有用人数量 d_j=\sum\limits_{i=1}^n[c_i\ge j]。
设计 dp 状态 f_{i,j,k} 表示进行完 i 天面试，参与完面试的人已经有 j 个未被录用，且所有参与完面试的 i 个人中当前的有用人数量为 k 时，只选择无用人的方案数。相当于有 k 个空位留给有用人，具体是哪个人待定，先把无用人选了。
考虑从 f_{i-1,j,k} 如何转移到 f_{i,*,*} 。
第 i 天如果选一个对于 j 来说的无用人参加面试，那么完成后该人一定不会被录用，j\gets j+1 。这个时候，原本那些 c_x=j+1 的人就从有用人变成了无用人，而这样的人有 d_{j+1}-d_{j+2} 个。那么我们枚举有 y 个 c_x=j+1 的人，在 f_{i-1,j,k} 的状态中被作为有用人参与面试，现在选择这些人之前留的填入空位。因为第 i 天录用的是对于 j 无用的人，所以对于 j+1 也一定不会有用，不影响 c_x=j+1 的从有用变无用的转移。可以选的无用人有 (d_0-d_{j+1}-(i-1-k)) 个。
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!
第 i 天如果选择一个有用人，那么 s_i=1 的时候他会被录用，否则不会被录用。
$$f_{i,j,k+1}\gets f_{i-1,j,k}$$
$s_i=0$ 时，$j\gets j+1$。这个时候，应该**先增加**一个给 $j$ 对应的有用人的空位，即 $k\gets k+1$。然后再考虑 $c_x=j+1$ 的有用人变为无用人的时候，有多少个是属于 $k$ 的，使用和无用人的转移一样的方法，枚举有 $y$ 个 $c_x=j+1$ 的人在 $f_{i-1,j,k}$ 和当前 $i$ 选择的这个人的状态中被作为有用人参与面试。
$$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!$$
最后统计答案，对于每个 $j$，由于每个人都参与过一次了，所以 $k=d_{j+1}$ 。这些未分配方案数的人任意排列即可。
$$ans=\sum\limits_{j=0}^{n-m}f_{n,j,d_{j+1}}\times d_{j+1}!$$
以上各条转移的取值范围，应该满足任何时刻任何变量（包括各种系数、下标、中间变量）都 $\ge 0$，并且 $k\le\min(i,d_{j+1})$。
虽然有 $i,j,k,y$ 四层循环，但是由于 $y\le d_{j+1}-d_{j+2}$，所以 $j$ 和 $y$ 两个循环实际上只会计算 $\sum(d_{j+1}-d_{j+2})=d_1=O(n)$ 次，因此时间复杂度是 $O(n^3)$ 的。
这也算是比较典的 dp 套路了。**状态存不下且相互之间暂时没区别的东西，可以先留空，等到后面再算贡献。**
::::warning[注意事项]
$500^3=1.25\times 10^8$，有取模阶乘组合数，1s 可能过不去。所以应该所有的循环都只在合法范围内做，并且只转移非 0 状态，这样常数极小，跑的飞快。
直接开 $500^3$ 个 long long 类型会爆 512MB 内存限制，所以需要滚动数组优化空间。不知道有没有人因为这个 $100\to0$ 。
::::
::::success[代码]
```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;
}
```
::::