这个只是暂时保存一下，并不作为题解

题解

• 未录用人数 $j$ 单调不减。当已有 $j$ 人未录用时：$c\le j$ 的人必放弃，$c>j$ 的人能否录用只取决于 $s$。
• 因此把人分成「$c\le j$」（身份必须当场确定，因为影响结果）和「$c>j$」（只关心个数，身份可延后确定）。这就是贡献延后计算：过程中 $c>j$ 的人不指定是谁，只记占位数 $k$；当 $j$ 加一时，把 $c=j+1$ 这批人从 $k$ 个占位中剥离 $t$ 个、当场确定身份。

$dp[i][j][k]$：已面试 $i$ 人，其中 $j$ 人未录用，已录用者中恰有 $k$ 人满足 $c>j$，且只计算了 $c\le j$ 的人的贡献。

辅助：$cnt_v=\#\{c=v\}$，$pre_v=\#\{c\le v\}$。

已面试 $i$ 人中有 $j$ 未录、$i-j$ 已录；其中 $k$ 个已录者 $c>j$，所以已录者里 $c\le j$ 的有 $i-j-k$ 人。剩余可选：

• $c\le j$ 未选：$pre_j-(i-k)$ 人；
• $c>j$ 未选：$n-pre_j-k$ 人。

若 $s_{i+1}=1$（必录用）：

1. 放一个 $c>j$ 的人：必录用，$k\to k+1$，系数 $1$（身份延后）：

$$dp[i+1][j][k+1]\mathrel{+}=dp[i][j][k]$$

2. 放一个 $c\le j$ 的人：必放弃，$j\to j+1$。先剥离 $t$ 个占位实为 $c=j+1$（$\binom{k}{t}\binom{cnt_{j+1}}{t}t!$ 种 $*$），当前人从 $pre_j-(i-k)$ 个未选者中挑一个：

$$dp[i+1][j+1][k-t]\mathrel{+}=dp[i][j][k]\cdot \binom{k}{t}\binom{cnt_{j+1}}{t}t!\cdot \big(pre_j-(i-k)\big)$$

若 $s_{i+1}=0$（必拒绝），$j\to j+1$：。

1. 放 $c>j+1$ 的人：必拒绝，$k\to k-t+1$：

$$dp[i+1][j+1][k-t+1]\mathrel{+}=dp[i][j][k]\cdot\binom{k}{t}\binom{cnt_{j+1}}{t}t!$$

2. 放 $c\le j$ 的人：必拒绝，$k\to k-t$，当前人从 $pre_{j+1}-(i-(k-t))$ 个未选者中挑：

$$dp[i+1][j+1][k-t]\mathrel{+}=dp[i][j][k]\cdot \binom{k}{t}\binom{cnt_{j+1}}{t}t!\cdot \big(pre_{j+1}-(i-(k-t))\big)$$

$*$：设有 $t$ 个人满足他们的 $c=j+1$，从耐心值刚爆（$c_p=j+1$）中选 $t$ 个为 $\binom{cnt_{j+1}}{t}$，从没有确定位置的 $k$ 个人选 $t$ 个为 $\binom{k}{t}t!$，则有 $\binom{k}{t}\binom{cnt_{j+1}}{t}t!$ 种方案数。

答案： 结束时已录的 $n-j$ 人全是 $c>j$，占位数 $k=n-pre_j$，他们之间还有 $(n-pre_j)!$ 种排列未计入：

$$\text{ans}=\sum_{j=0}^{n-m} dp[n][j][n-pre_j]\cdot (n-pre_j)!$$

代码

阶乘和组合数预处理一下。

时间复杂度：$\Theta(n^3)$，空间如果直接转移是 $\Theta(n^3)$，会MLE，所以要滚动数组优化，实际空间复杂度：$\Theta(n^2)$。

// [CSP-S 2025] 员工招聘
#include <iostream>
using namespace std;

#define MOD 998244353
int n, m, dp[2][505][505], fac[505], comb[505][505], cnt[505], pre[505], ans;
char s[505];

int main() {
    freopen("employ.in", "r", stdin);
    freopen("employ.out", "w", stdout);
    cin >> n >> m >> (s + 1);
    fac[0] = 1;
    for (int i = 1, c; i <= n; ++i) {
        cin >> c;
        fac[i] = 1ll * fac[i - 1] * i % MOD;
        cnt[c]++;
    }
    pre[0] = cnt[0];
    for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + cnt[i];
    for (int i = 0; i <= n; ++i) {
        comb[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
    }
    dp[0][0][0] = 1;
    for (int i = 0; i < n; ++i) {
        int cur = i & 1, nxt = cur ^ 1;
        for (int j = 0; j <= i; ++j)
            for (int k = 0; k <= i; ++k)
                dp[nxt][j][k] = 0;
        for (int j = 0; j <= i; ++j) {
            for (int k = 0; k <= i; ++k) {
                if (s[i + 1] == '0') {
                    for (int t = 0; t <= min(cnt[j + 1], k); ++t) {
                        // c > j + 1
                        int num = 1ll * comb[cnt[j + 1]][t] * fac[t] % MOD * comb[k][t] % MOD;
                        int dp_cur = 1ll * num * dp[cur][j][k] % MOD;
                        dp[nxt][j + 1][k - t + 1] = (dp[nxt][j + 1][k - t + 1] + dp_cur) % MOD;
                        // c <= j + 1
                        int choose = pre[j + 1] - (i - (k - t));
                        if (choose > 0) {
                            dp_cur = 1ll * dp_cur * choose % MOD;
                            dp[nxt][j + 1][k - t] = (dp[nxt][j + 1][k - t] + dp_cur) % MOD;
                        }
                    }
                } else {
                    // c <= j
                    int choose = pre[j] - (i - k);
                    if (choose > 0) {
                        for (int t = 0; t <= min(cnt[j + 1], k); ++t) {
                            int num = 1ll * comb[cnt[j + 1]][t] * comb[k][t] % MOD * fac[t] % MOD;
                            int dp_cur = 1ll * choose * num % MOD * dp[cur][j][k] % MOD;
                            dp[nxt][j + 1][k - t] = (dp[nxt][j + 1][k - t] + dp_cur) % MOD;
                        }
                    }
                    // c > j
                    if (n - pre[j] - k > 0)
                        dp[nxt][j][k + 1] = (dp[nxt][j][k + 1] + dp[cur][j][k]) % MOD;
                }
            }
        }
    }
    for (int j = 0; j <= n - m; ++j)
        ans = (ans + 1ll * dp[n & 1][j][n - pre[j]] * fac[n - pre[j]] % MOD) % MOD;
    cout << ans << '\n';
    return 0;
}