官方题解只能做到 $O((n+m)k^4)$？玩的太差了。记 这题可以做到 $O((n+m)k)$ 时间、$O(n+m+k)$ 空间，包括排序在内不需要额外的 $\log N$。下面通过状态消元和对角线递推，把关于 $k$ 的依赖降到线性。([QOJ][1])

关键有两步：先把炸弹相关的二维状态压成一个 $k+1$ 次多项式，再把一种点数的整批转移化成只访问相邻系数的递推。

从对局计数压成一元多项式

先考虑不含炸弹的两个序列。定义 $f(S)$ 为 $S$ 中从右往左扫描得到的非严格后缀最大值，仍按原来的先后顺序排列。例如 $f(5,3,2,4,5,3,4,2,1)=(5,5,4,2,1)$。

两个序列对战的结果，就是比较 $f(A)$ 与 $f(B)$ 的字典序。证明可以按照最大值递归：最大值不同，较大的一方必胜；最大值相同但出现次数不同，次数多的一方必胜；否则双方最后一个最大值会同时消失，接下来只需比较它们后面的后缀。([QOJ][1])

我们只统计“小 Y 获胜”和“平局”，小 X 获胜的概率最后用 $1$ 减出来。这两种情况下，小 X 的全部炸弹都必须被消耗。

按照炸弹把小 X 的序列分成 $k+1$ 段，并按照每个炸弹实际炸掉的棋子，把小 Y 的序列同步分段。考虑某个炸弹前的两个普通棋子段 $A,B$，设这个炸弹炸掉的棋子是 $C$。这段分解合法，当且仅当 $f(A)=f(B)$，或者 $f(B)< f(A)< f(B+C)$：前一种情况是两个普通段恰好同时清空；后一种情况是小 X 先打完 $B$，然后被 $C$ 打完，最后炸弹与 $C$ 同归于尽。([QOJ][1])

从大到小加入各个点数。一个炸弹对应的段，只需要区分三种情况：它所匹配的 $C$ 尚未加入；$C$ 已加入，但前面的两个普通段仍然平局；$C$ 已加入，且前面的普通段已经确定由小 X 获胜。分别给前两种情况赋标记 $\xi,\eta$，第三种情况赋权 $1$。最后一个不含炸弹的段，若仍然平局则赋标记 $\tau$，若已经确定小 Y 获胜则赋权 $1$。

初始所有段为空，所以计数多项式是 $\xi^k\tau$。

接下来写出加入一种点数时的生成函数。设已经加入了 $A$ 个小 X 的普通棋子、$B$ 个小 Y 的棋子，令 $K=k+1$、$a=A+K$、$b=B+1$。用形式变量 $u,v$ 分别记录本次加入双方的棋子数。

在序列的一个自由空隙中插入任意多个当前点数，分别贡献 $(1-u)^{-1}$、$(1-v)^{-1}$；在仍然平局的两个段末尾，同时添加任意多对当前点数，贡献 $(1-uv)^{-1}$。按这些空隙计数，可以把整批插入写成公共因子 $(1-u)^{-a}(1-v)^{-b}$，以及下面的标记替换：

$\xi\mapsto \dfrac{(1-u)(\xi+v\eta)}{1-uv}$。其中 $\xi$ 表示继续不确定匹配对象，$v\eta$ 表示把当前点数作为匹配对象。

$\eta\mapsto \dfrac{(1-v)((1-u)\eta+u)}{1-uv}$。其中前一项继续保持平局，后一项表示在小 X 的段末尾多放一个当前点数，使其确定获胜。匹配对象是之前加入的更大点数，因此仍然能够打败这一段。

$\tau\mapsto \dfrac{(1-u)((1-v)\tau+v)}{1-uv}$。其中前一项保持平局，后一项表示在小 Y 的最后一段末尾多放一个当前点数，使小 Y 确定获胜。

这些替换直接维护会产生二维状态，但它们有一个重要的不变量：替换后，$\xi'+\eta'-1=\dfrac{1-u}{1-uv}(\xi+\eta-1)$。而最终要求全部炸弹都有匹配对象，恰好是代入 $\xi=0,\eta=1$，满足 $\xi+\eta=1$。

因此，可以从一开始就代入 $\eta=1-\xi$，而不会影响答案。

令 $\xi=x,\tau=t$。消元之后，$x,t$ 都进行同一个仿射替换 $\phi(z)=\dfrac{(1-u)((1-v)z+v)}{1-uv}$。

于是两变量计数多项式始终可以表示成 $G(x,t)=R(x)+\dfrac{t-x}{K}R'(x)$，其中 $R$ 是次数不超过 $K$ 的一元多项式。初始取 $R(x)=x^K$，右侧正好等于 $x^kt$；之后因为 $\phi(t)-\phi(x)$ 等于 $\phi$ 的斜率乘以 $t-x$，这个关系在每次替换及取系数后都会保持。

设当前点数在双方分别出现 $p,q$ 次，那么只需要执行：

$$ R_{\mathrm{new}}(x) = [u^pv^q]\, (1-u)^{-a}(1-v)^{-b} R\!\left(\frac{(1-u)((1-v)x+v)}{1-uv}\right). $$

处理完所有点数以后，代入 $x=0$，得到 $G(0,t)=R(0)+tR'(0)/K$。所以小 Y 获胜的方案数是 $[x^0]R$，平局的方案数是 $[x^1]R/K$。

注意，消元后的 $R$ 的系数可以为负，它们并不是逐状态的概率；只有最终取出的上述两项具有对应的计数含义。

把整批转移做到 $O((p+q)K)$

如果直接展开上面的取系数式，仍然会出现多重求和。接下来利用它的特殊形式，把求和消掉。

固定本轮开始时的 $a,b$ 和旧多项式，记加入 $p,q$ 个当前点数后的结果为 $H_{p,q}$。这里的 $p,q$ 暂时作为局部递推下标，$a,b$ 在这一轮中始终不变。

只有单侧加入棋子时，递推很简单。设当前多项式系数为 $h_i$，已经单独加入了 $t$ 个棋子，那么再加入一个小 X 的棋子，对应 $h_i\gets (a+t-i)h_i/(t+1)$；再加入一个小 Y 的棋子，对应 $h_i\gets ((b+t-i)h_i+(i+1)h_{i+1})/(t+1)$。每一步只需要 $O(K)$ 时间。

因此，可以先走到 $H_{r,0}$ 或 $H_{0,r}$，其中 $r$ 是双方数量差的绝对值。剩下的问题是如何沿着固定 $p-q$ 的对角线，同时增加两边的数量。

定义微分算子 $\mathcal L_{\alpha,\beta}F=x(1-x)F''+(1-\alpha+(\alpha+\beta-2)x)F'$。它对单项式的作用为 $\mathcal L_{\alpha,\beta}x^i=i(\alpha+\beta-1-i)x^i+i(i-\alpha)x^{i-1}$，所以作用到一个 $K$ 次多项式上，只需要 $O(K)$ 时间。

关键递推是：

$$ pq\,H_{p,q} = \bigl(C_{p,q}-\mathcal L_{\alpha,\beta}\bigr)H_{p-1,q-1} - D_{p,q}H_{p-2,q-2}, $$

其中 $\alpha=a+p-q$、$\beta=b-p+q$，$C_{p,q}=(a+p-1)(b+q-1)+(p-1)(q-1)$，$D_{p,q}=(a+p-2)(b+q-2)$。出现负下标的多项式视为零。

这个恒等式可以直接由转移生成函数证明。令 $H=(1-u)^{-a}(1-v)^{-b}R(\phi(x))$，并记 $D_u=u\partial_u$、$D_v=v\partial_v$。按链式法则求导，$R,R',R''$ 的系数分别抵消，得到：

$$ (1-uv)\bigl(D_uD_v-uv(a+D_u)(b+D_v)\bigr)H + uv\bigl(\mathcal L_{a,b}-(D_u-D_v)\partial_x\bigr)H =0. $$

取 $u^pv^q$ 的系数，就是上述对角线递推。其中 $\mathcal L_{a,b}-(p-q)\partial_x=\mathcal L_{a+p-q,b-p+q}$，这也解释了递推中 $\alpha,\beta$ 的来源。

落实到系数上，设 cur 是 $H_{p-1,q-1}$，prev 是 $H_{p-2,q-2}$，那么：

$$ \mathrm{next}_i= \frac{ \bigl(C_{p,q}-i(a+b-1-i)\bigr)\mathrm{cur}_i +(i+1)(\alpha-i-1)\mathrm{cur}_{i+1} -D_{p,q}\mathrm{prev}_i }{pq}. $$

这只访问当前多项式的两个相邻系数，以及前一个多项式的同位置系数。

因此，加入一整种点数时，先做 $|p-q|$ 次单侧递推，再做 $\min(p,q)$ 次对角线递推，总共 $\max(p,q)$ 次，每次 $O(K)$。

同值棋子不能随意当成不同点数依次处理。 上面的单侧递推只是对角线的初始条件；当双方都有当前点数时，必须使用对角线递推处理相等棋子同归于尽的影响。

复杂度与 C++ 实现

所有点数的 $\max(p,q)$ 之和不超过 $n+m$，因此多项式计算总时间为 $O((n+m)(k+1))$。

题面中棋子点数不超过 $10^5$。把点数及所属方编码成 $(\text{value}\ll1)\mathbin{|}\text{side}$，编码小于 $2^{18}$，可以用两趟九位基数排序，在 $O(n+m)$ 时间内完成分组，避免比较排序的对数因子。([QOJ][2])

设点数 $v$ 在双方的出现次数分别为 $p_v,q_v$。所有不同的序列对等概率，总方案数为 $\Omega=\dfrac{(n+k)!,m!}{k!\prod_v p_v!\prod_v q_v!}$。最后将两个计数除以 $\Omega$，并用补集得到小 X 获胜的概率。

整体时间复杂度为 $O((n+m)k)$，空间复杂度为 $O(n+m+k)$。当 $k$ 视为常数时，时间复杂度达到读取输入的线性下界。

实现：https://qoj.ac/submission/2936508 ，ucup finals 的题目就是简单。