[CSP-S 2025] 员工招聘

GitHub 跳转原题关系图返回列表

按失败人数做 DP，用 pending 延后结算大耐心人群，并在阈值增加时用组合数归属具体人员。

OJ: luogu

题目 ID: P14364

难度:省选/NOI-

标签:动态规划组合计数计数DP

日期: 2026-06-22 19:59

题意

有 n 个应聘者，小 Z 可以安排他们的面试顺序。第 i 天的题目由 s_i 决定：

s_i = 1：参加面试的人会被录用；
s_i = 0：参加面试的人会被拒绝。

每个人 x 有耐心上限 c_x。如果在他之前已经有不少于 c_x 人被拒绝或放弃，他会直接放弃。拒绝和放弃都会让失败人数增加。

求有多少个排列能让录用人数至少为 m，答案对 998244353 取模。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAXN = 10;

int n, m;
string s;
int c[MAXN];
int p[MAXN];

bool check_perm() {
    int failed = 0;
    int hired = 0;

    for (int day = 0; day < n; day++) {
        int person = p[day];
        if (failed >= c[person]) {
            failed++;
            continue;
        }

        if (s[day] == '1') {
            hired++;
        } else {
            failed++;
        }
    }

    return hired >= m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    cin >> s;
    for (int i = 0; i < n; i++) {
        cin >> c[i];
        p[i] = i;
    }

    int ans = 0;
    do {
        if (check_perm()) {
            ans++;
            if (ans >= MOD) {
                ans -= MOD;
            }
        }
    } while (next_permutation(p, p + n));

    cout << ans << '\n';
    return 0;
}

暴力枚举所有排列，再按题意模拟。它适合验证，但 n <= 500 时不能使用。

录用人数至少为 m，等价于最终失败人数至多 n-m。一个人是否放弃，只取决于当前失败人数和他的 c，所以可以按耐心值分组。

设：

text

1
2cnt[x] = c_i = x 的人数
pre[x] = c_i <= x 的人数

DP 的核心状态是：

text

1dp[failed][pending]

表示已经处理若干天后，当前失败人数为 failed，并且有 pending 个已经安排过、但还没有确定具体耐心值的人。

为什么可以“不确定具体耐心值”？因为当失败人数是 failed 时，所有 c > failed 的人行为完全相同：他们不会放弃。只有当失败人数涨到 failed+1 时，c = failed+1 的人会从“不会放弃”变成“之后会放弃”，这时才需要把他们从 pending 中结算出来。

当失败人数从 failed 变为 failed+1 时，假设从 pending 个位置中结算出 t 个耐心值为 failed+1 的人，方案数为：

text

1C(pending, t) * C(cnt[failed+1], t) * t!

三部分分别表示：

选择哪些 pending 位置属于这一组；
选择具体是哪 t 个人；
把这些人分配到这些位置。

接着看每天怎么转移。

如果当天 s = 1：

选一个 c > failed 的新人，他会被录用，失败人数不变，加入 pending；
选一个 c <= failed 且还没用过的人，他会放弃，失败人数增加，并结算新阈值。

如果当天 s = 0：

当天一定会产生一个失败；
先结算新阈值 failed+1；
再选择当天这个人：若他仍属于 c > failed+1，他参加面试后被拒绝，加入 pending；否则他立即按具体身份结算。

最后统计答案时，只保留失败人数 failed <= n-m 的状态。并且最终必须满足：

text

1pending = n - pre[failed]

也就是所有 c <= failed 的人已经结算完，剩下的大耐心人都还在 pending 里。它们的具体身份还可以任意排列，所以要乘上 pending!。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;
const int MOD = 998244353;

int n, m;
string s;
int cnt[MAXN], pre[MAXN];
int fac[MAXN], comb[MAXN][MAXN];
int cur[MAXN][MAXN], nxt[MAXN][MAXN];

void add_mod(int &x, long long y) {
    x = (x + y) % MOD;
}

long long choose_pending(int value_c, int k, int t) {
    return 1LL * comb[k][t] * comb[cnt[value_c]][t] % MOD * fac[t] % MOD;
}

void init_comb() {
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fac[i] = 1LL * fac[i - 1] * i % MOD;
    }

    for (int i = 0; i < MAXN; i++) {
        comb[i][0] = comb[i][i] = 1;
    }
    for (int i = 1; i < MAXN; i++) {
        for (int j = 1; j < i; j++) {
            comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
            if (comb[i][j] >= MOD) {
                comb[i][j] -= MOD;
            }
        }
    }
}

void clear_next() {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            nxt[i][j] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init_comb();

    cin >> n >> m;
    cin >> s;

    for (int i = 1; i <= n; i++) {
        int c;
        cin >> c;
        cnt[c]++;
    }

    pre[0] = cnt[0];
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + cnt[i];
    }

    cur[0][0] = 1;

    for (int day = 0; day < n; day++) {
        clear_next();

        for (int failed = 0; failed <= day; failed++) {
            for (int pending = 0; pending <= day; pending++) {
                int val = cur[failed][pending];
                if (val == 0) {
                    continue;
                }

                if (s[day] == '1') {
                    // 选一个 c > failed 的人，他会被录用；具体是谁先延后统计。
                    if (n - pre[failed] - pending > 0) {
                        add_mod(nxt[failed][pending + 1], val);
                    }

                    // 选一个 c <= failed 的人，他会放弃，失败人数增加。
                    int available_small = pre[failed] - (day - pending);
                    if (available_small > 0) {
                        int max_t = min(cnt[failed + 1], pending);
                        for (int t = 0; t <= max_t; t++) {
                            long long ways = choose_pending(failed + 1, pending, t);
                            ways = ways * available_small % MOD;
                            add_mod(nxt[failed + 1][pending - t], 1LL * val * ways % MOD);
                        }
                    }
                } else {
                    // 题目太难，必定失败；失败人数从 failed 变成 failed + 1。
                    int max_t = min(cnt[failed + 1], pending);
                    for (int t = 0; t <= max_t; t++) {
                        long long ways = choose_pending(failed + 1, pending, t);
                        int after_pending = pending - t;

                        // 当天这个人若 c > failed + 1，继续作为待结算人员。
                        if (n - pre[failed + 1] - after_pending > 0) {
                            add_mod(nxt[failed + 1][after_pending + 1],
                                    1LL * val * ways % MOD);
                        }

                        // 当天这个人若 c <= failed + 1，立即结算具体身份。
                        int available_small = pre[failed + 1] - (day - after_pending);
                        if (available_small > 0) {
                            add_mod(nxt[failed + 1][after_pending],
                                    1LL * val * ways % MOD * available_small % MOD);
                        }
                    }
                }
            }
        }

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                cur[i][j] = nxt[i][j];
            }
        }
    }

    int ans = 0;
    for (int failed = 0; failed <= n - m; failed++) {
        int pending = n - pre[failed];
        if (pending >= 0 && pending <= n) {
            add_mod(ans, 1LL * cur[failed][pending] * fac[pending] % MOD);
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

滚动 DP 数组和组合数表都是 $O(n^2)$ 空间。

转移中会枚举结算数量 t，最坏时间复杂度可写作：

text

1O(n^4)

实际实现会跳过零状态，并且 t 受 pending 和 cnt[failed+1] 限制。

总结

本题难点在于不能直接记录每个耐心值用了多少人。pending 的作用是把当前还不会放弃的人暂时合并，等失败人数增长到某个阈值时，再用组合数一次性结算对应耐心值的人。

只要把“失败人数增加”视为状态边界，整个计数过程就能按天推进。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P14364 [CSP-S 2025] 员工招聘

题目背景

由于评测机性能差异，本题时限提升 1 秒。

题目描述

小 Z 和小 H 想要合伙开一家公司，共有 $n$ 人前来应聘，编号为 $1 \sim n$ 。小 Z 和小 H 希望录用至少 $m$ 人。

小 H 是面试官，将在接下来 $n$ 天每天面试一个人。小 Z 负责决定应聘人前来面试的顺序。具体地，小 Z 可以选择一个 $1 \sim n$ 的排列 $p$ ，然后在第 $i$ ( $1 \leq i \leq n$ ) 天通知编号为 $p_i$ 的人前来面试。

小 H 准备了 $n$ 套难度不一的面试题。由于 $n$ 个前来应聘的人水平大致相同，因此对于同一套题，所有人的作答结果是一致的。具体地，第 $i$ ( $1 \leq i \leq n$ ) 天的面试题的难度为 $s_i \in \{0,1\}$ ，其中 $s_i = 0$ 表示这套题的难度较高，没有人能够做出； $s_i = 1$ 表示这套题的难度较低，所有人都能做出。小 H 会根据面试者的作答结果决定是否录用，即如果面试者没有做出面试题，则会拒绝，否则会录用。

然而，每个人的耐心都有一定的上限，如果在他面试之前未录用的人数过多，则他会直接放弃参加面试。具体地，编号为 $i$ ( $1 \leq i \leq n$ ) 的人的耐心上限可以用非负整数 $c_i$ 描述，若在他之前已经有不少于 $c_i$ 人被拒绝或放弃参加面试，则他也将放弃参加面试。

小 Z 想知道一共有多少种面试的顺序 $p$ 能够让他们录用至少 $m$ 人。你需要帮助小 Z 求出，能够录用至少 $m$ 人的排列 $p$ 的数量。由于答案可能较大，你只需要求出答案对 $998\,244\,353$ 取模后的结果。

输入格式

输入的第一行包含两个正整数 $n, m$ ，分别表示前来应聘的人数和希望录用的人数。

输入的第二行包含一个长度为 $n$ 的字符串 $s_1 \dots s_n$ ，表示每一天的面试题的难度。

输入的第三行包含 $n$ 个非负整数 $c_1, c_2, \dots, c_n$ ，表示每个人的耐心上限。

输出格式

输出一行一个非负整数，表示能够录用至少 $m$ 人的排列 $p$ 的数量对 $998\,244\,353$ 取模后的结果。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

1
2
310 5
1101111011
6 0 4 2 1 2 5 4 3 3

输出 #2

text

12204128

说明/提示

【样例 1 解释】

共有以下 2 种面试的顺序 $p$ 能够让小 Z 和小 H 录用至少 2 人:

$p = [1,2,3]$ , 依次录用编号为 1 的人和编号为 3 的人;
$p = [2,1,3]$ , 依次录用编号为 2 的人和编号为 3 的人。

【样例 3】

见选手目录下的 $\textbf{\textit{employ/employ3.in}}$ 与 $\textbf{\textit{employ/employ3.ans}}$ 。

该样例满足测试点 6 ~ 8 的约束条件。

【样例 4】

见选手目录下的 $\textbf{\textit{employ/employ4.in}}$ 与 $\textbf{\textit{employ/employ4.ans}}$ 。

该样例满足测试点 12 ~ 14 的约束条件。

【样例 5】

见选手目录下的 $\textbf{\textit{employ/employ5.in}}$ 与 $\textbf{\textit{employ/employ5.ans}}$ 。

该样例满足测试点 18 ~ 21 的约束条件。

【数据范围】

对于所有测试数据，保证:

$1 \leq m \leq n \leq 500$ ;
对于所有 $1 \leq i \leq n$ ，均有 $s_i \in \{0,1\}$ ;
对于所有 $1 \leq i \leq n$ ，均有 $0 \leq c_i \leq n$ 。

::cute-table{tuack}

测试点编号	$n \leq$	$m$	特殊性质
$1,2$	$10$	$\leq n$	无
$3 \sim 5$	$18$	^	^
$6 \sim 8$	$10^2$	^	A
$9 \sim 11$	^	^	无
$12 \sim 14$	$500$	$=1$	^
$15$	^	$=n$	^
$16,17$	^	$\leq n$	A
$18 \sim 21$	^	^	B
$22 \sim 25$	^	^	无

特殊性质 A: 对于所有 $1 \leq i \leq n$ ，均有 $s_i = 1$ 。

特殊性质 B: 在 $s_1, s_2, \dots, s_n$ 中最多只有 18 个取值为 1，即 $\sum_{i=1}^{n} s_i \leq 18$ 。