都落ち

Erine · 2025-07-29 15:53:02 · 题解

模拟赛题。令 a_i 为 t_i 能在 s 中匹配到的最大位置。先对 a_i 排序。将 A 类点称作左部点，B 即右部。考虑对于没有被匹配的右部点找出一个最大的记为 p，那么状态是极大的匹配等同于 1\sim a_p 的左部点都被匹配。那么 1\sim p-1 的右部点有一部分会被匹配，p+1\sim n 的右部点全部会被匹配。一个右部点被匹配，等价于选定一个 1\le b_i\le a_i 且 b_i 两两不同。那么我们条件就是 \operatorname{mex}\gt a_p（此处 \operatorname{mex} 定义为最小的未出现的正整数）。

看起来一般的 dp 不太有前途。考虑容斥。 钦定一个集合 S\subseteq \{1,2,3,\dots,a_p\} 没有在 b 中出现。容斥系数是 (-1)^{|S|}。那么方案数只需要对右部点从前往后 dp，记录前面选了几个点，已经 ban 了几个不出现的数即可。由此得到 dp 状态：

令 f_{i,j,k} 表示考虑 [1,i] 的右部点，[1,a_i] 的左部点，其中选了 j 个右部点和左部点做匹配，以及 [1,a_i] 中有 k 个左部点被我们 ban 掉了。转移分类讨论 a_{i+1}-a_i 里有多少个 ban 的，以及选不选当前点匹配即可。

发现我们统计答案只关心 j+k 的值和 k 的奇偶性。所以可以对 dp 状态进行修改。其次是不需要枚举 p，因为 <p-1 的转移是简单的。对于 p-1\to p 的转移可以特殊计算。后面的转移是唯一的，可以预处理一些下降幂状物。

记得特别处理全部匹配上的情况。

考虑分析复杂度，设 w_i=a_i-a_{i-1}，复杂度是 \sum_{i<j}w_iw_j=\Theta(n^2)，可以通过。