都落ち

模拟赛题。令 $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)$，可以通过。