2025 员工招聘 · 方案二三维计数DP

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 3526 字
按耐心分层延迟定人，组合数占位排列数定型收尾
2025
计数DP
正文

// CSP-S 2025 复赛 T4 · 员工招聘（方案二：三维计数 DP，满分）
// 原题：https://oj.yecheng.tv/p/2469
// 题意：同方案一（n ≤ 500，需满分口径）。
// 思路（按耐心分层 + 延迟定人）：
//   dp[i][j][k]：面试 i 场、未录用 j 人、其中耐心 ≤ j 者已定 k 人。
//   核心是「耐心 ≤ j 的人何时定型」：在被拒累计到达 j 之前，他们
//   与耐心更高的人难以区分，故先按组合数 C(i-k, u) 占位，到边界
//   时再用排列数 A(cnt[j+1], u) 把「耐心恰为 j+1」的人定型。
//   转移逐场讨论 s_i 与面试者来源（耐心 > j / ≤ j / = j+1），
//   易题时被拒者可以来自两类，难题时只有更高耐心者可继续。
//   末层对耐心 > j 的人全排列收尾：ans += dp[n][j][pre[j]] * (n - pre[j])!。
//   统计未录用 j 满足 n - j >= m（录用人数 >= m）的方案和，模 998244353。
// 复杂度：O(n^3) 状态转移（常数小），n = 500 约 1e8 内。
// 易错点：
//   1. 录用人数 = n - 未录用人数，统计的是 j <= n - m 的层；
//   2. 「耐心 ≤ j 已定 k」中 k 是历史位置数，组合数从 i-k 里选；
//   3. A(cnt[j+1], u) 是排列数，定型顺序有关；
//   4. dp 用滚动数组防爆内存，每层 memset 清空。
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;

const ll MOD = 998244353;

ll fac[505], inv_[505];

ll qpow(ll a, ll n) {
    ll r = 1;
    while (n) {
        if (n & 1) r = r * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return r;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i <= 500; i++) fac[i] = fac[i - 1] * i % MOD;
    inv_[500] = qpow(fac[500], MOD - 2);
    for (int i = 499; i >= 0; i--) inv_[i] = inv_[i + 1] * (i + 1) % MOD;
}

ll getC(int n, int m) { return fac[n] * inv_[n - m] % MOD * inv_[m] % MOD; }
ll getA(int n, int m) { return fac[n] * inv_[n - m] % MOD; }

int n, m, c[505], cnt_[505], pre_[505];
char s[505];
ll dp[2][505][505];

int main() {
    init();
    scanf("%d %d %s", &n, &m, s);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
        cnt_[c[i]]++;
    }
    pre_[0] = cnt_[0];
    for (int i = 1; i <= n; i++) pre_[i] = pre_[i - 1] + cnt_[i];

    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        int cur = i & 1, nxt = cur ^ 1;
        memset(dp[nxt], 0, sizeof dp[nxt]);
        for (int j = 0; j <= i; j++)
            for (int k = 0, kmax = (i < pre_[j] ? i : pre_[j]); k <= kmax; k++) {
                ll cur_v = dp[cur][j][k];
                if (!cur_v) continue;
                if (s[i] == '1') {
                    if ((n - pre_[j]) - (i - k) > 0) { // 挑耐心 > j 的人面试且录用
                        dp[nxt][j][k] = (dp[nxt][j][k] + cur_v) % MOD;
                    }
                    int umax = (i - k < cnt_[j + 1] ? i - k : cnt_[j + 1]);
                    for (int u = 0; u <= umax; u++) { // 挑耐心 <= j 的人面试且被拒
                        ll add = cur_v * (pre_[j] - k) % MOD * getC(i - k, u) % MOD * getA(cnt_[j + 1], u) % MOD;
                        dp[nxt][j + 1][k + (u + 1)] = (dp[nxt][j + 1][k + (u + 1)] + add) % MOD;
                    }
                } else {
                    int umax = (i - k < cnt_[j + 1] ? i - k : cnt_[j + 1]);
                    for (int u = 0; u <= umax; u++) {
                        if ((n - pre_[j + 1]) - (i - (k + u)) > 0) { // 挑耐心 > j+1 的人面试且被拒
                            ll add = cur_v * getC(i - k, u) % MOD * getA(cnt_[j + 1], u) % MOD;
                            dp[nxt][j + 1][k + u] = (dp[nxt][j + 1][k + u] + add) % MOD;
                        }
                        ll add = cur_v * (pre_[j + 1] - (k + u)) % MOD * getC(i - k, u) % MOD * getA(cnt_[j + 1], u) % MOD;
                        dp[nxt][j + 1][k + (u + 1)] = (dp[nxt][j + 1][k + (u + 1)] + add) % MOD;
                    }
                }
            }
    }

    ll ans = 0;
    for (int j = 0; j <= n - m; j++) { // 未录用 j 人 <=> 录用 n-j >= m 人
        ans = (ans + dp[n & 1][j][pre_[j]] * fac[n - pre_[j]]) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}
2025 员工招聘 · 方案二 三维计数DP

正文

CSP-S 标程 · 复赛真题的其它内容

2025 员工招聘 · 方案二三维计数DP
