题意： 给定长度为 nnn 的 010101 串： * 111 的位置可以录取人 * 000 的位置一定不能录取人 共有 nnn 个人，第 xxx 个人忍耐度为 cxc_xcx 。为所有人分配应聘顺序：若某人在应聘时，前方录取失败人数超过 cxc_xcx ，则他一定不会被录取。 求所有方案中，录取人数超过 mmm 的方案数。 思路： 预处理：只考虑 111 位置 000 位置对“能否录取”不产生可控贡献（必失败），可用“特殊元素优先处理”： 1. 先把所有 111 位置安排并计数； 2. 剩下的位置再乘上排列数补回。 下文“位置”均指 111 的位置。 定义： * wiw_iwi ：前 iii 个字符中 000 的个数 * tit_iti ：前 iii 个字符中，有多少个 111 位置最终无法录取 * viv_ivi ：第 iii 个位置能录取所需的最小忍耐度 则： vi=ti+wiv_i=t_i+w_i vi =ti +wi ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Step 1：先看 m=1m=1m=1 当“录取人数超过 111”，可先算“全都录取不了”的方案数 resresres，再做： ans=∣Ω∣−res,∣Ω∣=n!ans = |\Omega| - res,\qquad |\Omega|=n! ans=∣Ω∣−res,∣Ω∣=n! 令计数函数： S(p)=∣{x∣cx≤p}∣S(p)=\left|\{x\mid c_x\le p\}\right| S(p)=∣{x∣cx ≤p}∣ 若记第 rrr 个 111 的原下标为 posrpos_rposr ，则“全不录取”的乘法计数可写成类似： res=∏r=1k(S(posr−1)−(r−1))res=\prod_{r=1}^{k}\left(S(pos_r-1)-(r-1)\right) res=r=1∏k (S(posr −1)−(r−1)) 其中 kkk 为 111 的总数。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Step 2：出现反向限制，用容斥统一方向 枚举某个状态 sss（二进制表示哪些 111 位置录取）： * 若位置录取：要求 vi≤cxv_i \le c_xvi ≤cx * 若位置不录取：要求 vi>cxv_i > c_xvi >cx 两类条件方向相反，直接计数困难。定义事件 AiA_iAi ：位置 iii “无法录取”。则需求为： ∣⋂i∈sAi‾∣\left|\bigcap_{i\in s}\overline{A_i}\right| i∈s⋂ Ai 利用补集与容斥： ∣⋂i∈sA‾i∣=∣Ω∣−∣⋃i∈sAi∣\left|\bigcap_{i\in s}\overline A_i\right| = |\Omega|-\left|\bigcup_{i\in s}A_i\right| i∈s⋂ Ai =∣Ω∣− i∈s⋃ Ai 注意空集合 T=∅T=\varnothingT=∅ 时： ⋂i∈∅Ai=Ω\bigcap_{i\in \varnothing} A_i = \Omega i∈∅⋂ Ai =Ω 并写成标准容斥形式（含空集）： ∣⋂i∈sAi‾∣=∑T⊆s(−1)∣T∣∣⋂i∈TAi∣\left|\bigcap_{i\in s}\overline{A_i}\right| = \sum_{T\subseteq s}(-1)^{|T|} \left|\bigcap_{i\in T}A_i\right| i∈s⋂ Ai =T⊆s∑ (−1)∣T∣ i∈T⋂ Ai 做法：对每个状态 sss，枚举其子集 TTT，计算 ∣⋂i∈TAi∣\left|\bigcap_{i\in T}A_i\right| ⋂i∈T Ai 并按 (−1)∣T∣(-1)^{|T|}(−1)∣T∣ 加减。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Step 3：把重复的子集枚举用 DP 计算 在 Step 2 中，很多量会被重复计算，因此用 DP 代替“对每个 sss 枚举所有 TTT”。 示例状态： dpi,j,k:前 i 个 1 中，j 个钦定不录取，k 个因容斥而不录取dp_{i,j,k}: \text{前 } i \text{ 个 } 1 \text{ 中，} j \text{ 个钦定不录取，} k \text{ 个因容斥而不录取} dpi,j,k :前 i 个 1 中，j 个钦定不录取，k 个因容斥而不录取 把容斥求和结构嵌入 dpdpdp 递推即可。

解析 令 (hi)(h_i)(hi )( 表示前 iii 天中，难度较高的天数的数量。令 (fi)(f_i)(fi ) 表示 (cj)(c_j)(cj ) 小于等于 iii 的 jjj 的数量。我们考虑对于难度较高的天，先不分配具体是谁参加面试。最后答案乘以 (hn!)(h_n!)(hn !) 即可。令 (gi,j,k)(g_{i, j, k})(gi,j,k ) 表示前 iii 天中，有 jjj 天是不录用人的，且剩下 (i−j)(i-j)(i−j) 天中有 kkk 天是没有确定具体是谁去面试的方案数。我们称 (ck≤j)(c_k \leq j)(ck ≤j) 的人为 “弱人”，其它人为 “强人”。若 (si+1=0)(s_{i + 1} = 0)(si+1 =0)，(gi+1,j+1,k−l+=gi,j,k∗(cj+1−cjl)∗(kl)∗l!)(g_{i + 1, j + 1, k - l} += g_{i, j, k} * \binom{c_{j + 1} - c_{j}}{l} * \binom{k}{l} * l!)(gi+1,j+1,k−l +=gi,j,k ∗(lcj+1 −cj )∗(lk )∗l!)。若 (si+1=1)(s_{i + 1} = 1)(si+1 =1)，且下一天录用人，(gi+1,j,k+1+=gi,j,k)(g_{i + 1, j, k + 1} += g_{i, j, k})(gi+1,j,k+1 +=gi,j,k ) 。若 (si+1=1)(s_{i + 1} = 1)(si+1 =1)，且下一天不录用人， (gi+1,j+1,k−l+=gi,j,k∗(fj−(j−hi))∗(cj+1−cjl)∗(kl)∗l!)(g_{i + 1, j + 1, k - l} += g_{i, j, k} * (f_j - (j - h_i)) * \binom{c_{j + 1} - c_j}{l} * \binom{k}{l} * l!)(gi+1,j+1,k−l +=gi,j,k ∗(fj −(j−hi ))∗(lcj+1 −cj )∗(lk )∗l!)。时间复杂度 (O(n3))(O(n^3))(O(n3))。 答案