设往左走的获胜的概率为 $A$，往右走的获胜的概率为 $B$

不难发现，最终的方案里，一定存在一个分界点，分界点左侧的点往左走，右侧点往右走。

特判掉 $a=0,b=0$ 的情况，两侧的问题可以对称为一个子问题。以左侧问题为例。

先枚举一个前缀 $n'$。考虑一个贡献延后计算的东西，维护一个栈，从后往前 dp，每次遇到 $L$ 就塞进栈，遇到 $R$ 就随机栈顶的几个 $L$。最后希望栈里有 $a$ 个 $L$。

设 $f_{i,j}$ 表示考虑了 $i\sim n'$，其中还剩下 $j$ 个 $L$ 在栈里，不难列出转移式：

$$f_{i,j}=\begin{cases}f_{i+1,j-1} & s_{i}=L \\ f_{i+1,j+x}\times B^x\times A & s_{i}=R\end{cases}$$

第二个转移式子表示一个 $R$ 连续击败了 $k$ 个 $L$ 后被一个 $L$ 击败，注意转移中间 $j=0$ 的情况是非法的，需要特判掉。

但是因为我们最终计算答案要枚举分界点，而我们目前的 dp 是确定了一个前缀后再从后往前 dp，考虑到过来，确定了一个前缀后再从前往后 dp。

倒过来后，不难发现我们是让一些 $R$ 和后面的 $L$ 去匹配，但是有 $a$ 个 $L$ 没有匹配，我们把这些没有匹配的 $L$ 放在一边。

设 $f_{i,j}$ 表示考虑了 $1\sim i$ 还有 $j$ 个 $L$ 能放在一边。然后转移都反过来即可。

最后发现转移的这个 $k$ 很没用，用前缀和优化掉即可，时间复杂度为 $O(n^2)$。