DRAFT P14364 [CSP-S 2025] 员工招聘
2026-06-30
题目大意
有 n 个应聘者,编号 1 到 n,要从中录用至少 m 人。
小 Z 可以决定面试顺序,即给出一个 1∼n 的排列 p,第 i 天面试编号为 pi 的人。
第 i 天的试题难度为 si∈{0,1},其中 0 表示无人能做出(必拒),1 表示人人能做出(必录)。
每个人有耐心上限 ci:若在他面试前,已有不少于 ci 人被拒绝或放弃面试,则他自己也会放弃(不参加面试)。
只有实际参加面试且做出题目的人才会被录用。
求有多少种排列 p 使得最终录用人数至少为 m,答案对 998244353 取模。
数据范围:1≤m≤n≤500,si∈{0,1},0≤ci≤n。
特殊性质 A:所有 si=1;特殊性质 B:si=1 的位置最多 18 个。
题解
注意:下文中单独的 i 为人的编号,pi 表示挑选的第 i 个人的编号。
注意到数据范围,考虑 DP,这里使用贡献延后计算。
分析一下过程,设没被招聘的人有 cnt 个,若 si=0,大家都不会;若 si=1,则 ci≤cnt 都会摆烂,并且 cnt 不降。这么来看,我们在任何时刻都可以将所有人的 ci 划分为 ci≤cnt 和 ci>cnt 的两个集合(摆烂组和预备组),当 cnt 增加时看哪些从预备组进入摆烂组,在这个时候计算贡献。
我们设 f[i][j][k] 表示当前为第 pi 个位置,摆烂组有 j 个人,在 i 个人中,有 k 个人来自预备组。
令 ai 表示 cpj=i 的人数,bi 表示 cpj≤i 的人数。
现在我们进行转移:
- 若 si=0,大家都考不上,j 一定加一,此时考虑 pi 是否在摆烂组:
- 若 pi 在摆烂组(cpi≤j+1): 枚举在
