[CSP-S 2025] 员工招聘

退役了可以对着题目毫无心理压力地bb好爽（

CF1437F Emotional Fishermen 带给我们的启示：带限制的排列计数问题一般都很困难，我们可以使用 dp，容斥等手段约束整理限制，将限制整理成易于使用组合数计算排列数量的形式。

录取至少 \(m\) 个人没有什么好的转化手段，那么就以录取的状态为着手点，考虑给定一个状态 \(S\)，其中第 \(i\) 次面试是否成功已经被钦定，此时有多少种满足状态 \(S\) 的排列。

考虑第 \(i\) 次面试 (\(s_i=1\))，前面已经录取了 \(j\) 个人，那么第 \(i\) 位的限制有一下几种：

• 钦定录取：\(c_i>i-1-j\)。
• 钦定不录取：\(c_i\le i-1-j\)。

我们按照这些限制填入对应的人，剩下 \(s_i=0\) 的位置就是一个全排列。

但现在还是非常难做，原因在于限制的类型不一样，一个 \(c_i>i-1-j\) 一个 \(c_i\le i-1-j\) 搞得人很难受。

「LibreOJ NOI Round #2」不等关系 告诉我们，我们可以用容斥的方式扭转限制！

具体地，针对 \(c_i>i-1-j\) 的限制，我们有两种处理：

• 假装不存在，把它归到最后的全排列里。
• 把它归于 \(c_i\le i-1-j\) 的限制，同时给方案数乘上一个 \(-1\) 的系数。

这个时候所有限制都变成了 \(c_i\le i-1-j\)，并且你发现 \(i\) 变大时 \(i-1-j\) 必然单调不减，原先满足限制的人在 \(i\) 变大后仍然满足限制。

整理一下思路，我们现在希望同时刻画状态录取状态 \(S\) 和容斥的过程，考虑如何用 dp 完成这一点：

设 \(sum_i=\sum\limits_{j=1}^n [c_j\le i]\)，\(f_{i,j,k}\) 表示前 \(i\) 次面试，钦定录取了 \(j\) 个人，并且已经确定了 \(k\) 个人的方案数。转移分几种：

• 第 \(i+1\) 次面试钦定为录取，且无视这次限制：\(f_{i,j,k}\to f_{i+1,j+1,k}\)。
• 第 \(i+1\) 次面试钦定为录取，且考虑这次限制的容斥系数：\(-(sum_{i-j}-k)f_{i,j,k}\xrightarrow[]{} f_{i+1,j+1,k+1}\)。
• 第 \(i+1\) 次面试钦定为不录取：\((sum_{i-j}-k)f_{i,j,k}\xrightarrow[]{} f_{i+1,j,k+1}\)。

答案即为 \(\sum\limits_{x\ge m}\sum\limits_{y\le n} f_{n,x,y}\times (n-y)!\)。时间复杂度 \(\mathcal O(n^3)\)，使用滚动数组控制空间复杂度即可。

#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec secondusing i64 = long long;
using pii = std::pair<int, int>;constexpr int mod = 998244353;
void add(int& x, int y) { if ((x += y) >= mod) x -= mod; return; }
void sub(int& x, int y) { if ((x -= y) < 0) x += mod; return; }
int inc(int x, int y) { return (x + y) >= mod ? (x + y - mod) : (x + y); }
int dec(int x, int y) { return (x - y) < 0 ? (x - y + mod) : (x - y); }namespace binomial {std::vector<int> fac, ifac, inv;void init(int n) {fac.resize(n + 5, 0);ifac.resize(n + 5, 0);inv.resize(n + 5, 0);fac[0] = fac[1] = ifac[0] = ifac[1] = inv[1] = 1;for (int i = 2; i <= n; ++i) {fac[i] = 1ll * fac[i - 1] * i % mod;inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;ifac[i] = 1ll * ifac[i - 1] * inv[i] % mod;}return;}int C(int n, int m) {if (n < 0 || m < 0 || n < m) return 0;return 1ll * fac[n] * ifac[n - m] % mod * ifac[m] % mod;}
}int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int n, m;std::cin >> n >> m;std::string s;std::cin >> s;std::vector<int> c(n), sum(n + 1, 0);for (int i = 0; i < n; ++i) std::cin >> c[i], ++sum[c[i]];for (int i = 1; i <= n; ++i) sum[i] += sum[i - 1];std::vector<std::vector<int>> dp(n + 1, std::vector<int>(n + 1, 0)), f(n + 1, std::vector<int>(n + 1, 0));dp[0][0] = 1;for (int i = 0; i < n; ++i) {if (s[i] == '0') continue;for (int j = 0; j <= i; ++j) {for (int k = 0; k <= i; ++k) {if (!dp[j][k]) continue;// 决定这个人录取add(f[j + 1][k], dp[j][k]);if (sum[i - j] > k) sub(f[j + 1][k + 1], 1ll * dp[j][k] * (sum[i - j] - k) % mod);// 决定这个人不录取if (sum[i - j] > k) add(f[j][k + 1], 1ll * dp[j][k] * (sum[i - j] - k) % mod);}}f.swap(dp);for (int j = 0; j <= i; ++j)for (int k = 0; k <= i; ++k)if (f[j][k]) f[j][k] = 0;}int ans = 0;binomial::init(n);for (int x = m; x <= n; ++x) {for (int y = 0; y <= n; ++y) {if (!dp[x][y]) continue;add(ans, 1ll * dp[x][y] * binomial::fac[n - y] % mod);}}std::cout << ans << '\n';return 0;
}