[CSP-S 2025] 员工招聘

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

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

OJ: luogu

题目 ID: P14364

难度:省选/NOI-

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

创建: 2026-06-22 19:59

更新: 2026-10-07 10:45

形式化题目

$n$ 个人来应聘，面试顺序是一个排列 $p$ 。第 $i$ 天的题目难度 $s_i \in \{0,1\}$ ： $s_i = 1$ 时当天面试者被录用， $s_i = 0$ 时被拒绝。

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

求有多少个排列能让录用人数至少为 $m$ ，答案对 $998\,244\,353$ 取模。

暴力解法

思路

枚举所有排列，按题意逐天模拟：失败人数已不少于 $c_i$ 就放弃，否则按当天题目难度录用或拒绝。统计录用人数至少为 $m$ 的排列数。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-06-22 19:59
 * update_at: 2026-10-01 22:48
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 枚举所有面试顺序排列，按题意模拟录用/拒绝/放弃，只适合 n <= 9 左右。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

int n, m;
string s;
int c[MAXN]; // c[i]：第 i 个人的耐心上限
int p[MAXN]; // 当前枚举的面试顺序排列

// 按题意模拟当前排列：统计录用人数是否至少为 m
bool check_perm() {
    int failed = 0;
    int hired = 0;

    for (int day = 0; day < n; day++) {
        int person = p[day];

        // 之前失败人数已不少于 c_i，这个人直接放弃
        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;
    }

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

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

复杂度

时间： $O(n! \cdot n)$
空间： $O(n)$

瓶颈

阶乘级枚举， $n \leqslant 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 > \mathit{failed}$ 的人行为完全相同：他们不会放弃。只有当失败人数涨到 failed+1 时， $c = \mathit{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 > \mathit{failed}$ 的新人，他会被录用，失败人数不变，加入 pending；
选一个 $c \leqslant \mathit{failed}$ 且还没用过的人，他会放弃，失败人数增加，并结算新阈值。

如果当天 $s = 0$ ：

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

最后统计答案时，只保留失败人数 $\mathit{failed} \leqslant n-m$ 的状态。并且最终必须满足

\mathit{pending} = n - pre[\mathit{failed}]

也就是所有 $c \leqslant \mathit{failed}$ 的人已经结算完，剩下的大耐心人都还在 pending 里。它们的具体身份还可以任意排列，所以要乘上 $\mathit{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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-06-22 19:59
 * update_at: 2026-10-01 22:48
 */
// main.cpp：按失败人数做 DP，用 pending 延后结算大耐心人群，
// 失败人数阈值增加时用组合数把具体人员归属结算出来。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

int n, m;
string s;

int cnt[MAXN]; // cnt[x]：耐心上限恰好为 x 的人数
int pre[MAXN]; // pre[x]：耐心上限 <= x 的人数前缀和

ll fac[MAXN];          // fac[t]：t 的阶乘（模 MOD）
ll comb[MAXN][MAXN];   // comb[i][j]：组合数 C(i, j)（模 MOD）
ll cur[MAXN][MAXN];    // cur[failed][pending]：当前天结束后的方案数
ll nxt[MAXN][MAXN];    // 下一天的滚动数组

// 模意义下加法：x = (x + y) % MOD，要求 y < MOD
void add_mod(ll &x, ll y) {
    x += y;
    if (x >= MOD) {
        x -= MOD;
    }
}

// 从 pending 个未结算位置里结算出 t 个耐心值恰为 value_c 的人：
// 选位置 C(k, t) * 选人 C(cnt[value_c], t) * 分配 t!
ll choose_pending(int value_c, int k, int t) {
    return 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] = 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;
            }
        }
    }
}

// 清零滚动数组 nxt（只清会用到的 0..n 范围）
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++) {
                ll 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++) {
                            ll ways = choose_pending(failed + 1, pending, t);
                            ways = ways * available_small % MOD;
                            add_mod(nxt[failed + 1][pending - t], val * ways % MOD);
                        }
                    }
                }
                else {
                    // 题目太难，必定失败；失败人数从 failed 变成 failed + 1。
                    int max_t = min(cnt[failed + 1], pending);
                    for (int t = 0; t <= max_t; t++) {
                        ll 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], 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],
                                    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];
            }
        }
    }

    // 录用至少 m 人 <=> 失败人数 <= n - m；
    // 最终所有 c <= failed 的人已结算完，剩余 pending 个大耐心人可任意排列。
    ll ans = 0;
    for (int failed = 0; failed <= n - m; failed++) {
        int pending = n - pre[failed];
        if (pending >= 0 && pending <= n) {
            add_mod(ans, cur[failed][pending] * fac[pending] % MOD);
        }
    }

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

复杂度

滚动 DP 数组和组合数表都是 $O(n^2)$ 空间
转移中枚举结算数量 $t$ ，最坏时间复杂度 $O(n^4)$

实际实现会跳过零状态，并且 $t$ 受 pending 和 $cnt[\mathit{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$ 。