博弈

题目大意

有一个字符集 $S$，两人轮流等概率的从中取出字符拼接到自己原本的空串后面，求先手的字典序严格大于后手的概率对 $998244353$ 取模的结果。

其中数据范围满足，$1\le T\le 26,1\le \lvert S\rvert \le 10^7$，不保证 $\sum\lvert S\rvert\le 10^7$。

思路

设 $k=\lfloor\frac{n}{2}\rfloor$，Alice、Bob 的字符串分别为 $A,B$，$S$ 表示字符集合，$cnt_c$ 表示字符 $c$ 的数量。

先考虑 $n$ 为偶数的情况，我们发现，对于每一种 $A<B$ 的方案，把他们反转过来，则有相应的 $A>B$ 的方案，且概率相等，则有：

\begin{align} Pr[A>B]&=Pr[A<B]\\ &=1-Pr[A=B]-Pr[A>B]\\ &=\dfrac{1-Pr[A=B]}{2} \end{align}

考虑怎么求 $A=B$ 的概率，首先要满足每个字符出现次数都是偶数。

由于他一共有 $\dfrac{n!}{\prod\limits_{c\in S}cnt_c!}$ 种方案，$A=B$ 的方案有 $\dfrac{k!}{\prod\limits_{c\in S}(cnt_c/2)!}$。

上面表示把相同的字符看作不同的时候所有方案，下面在去重，最后就是后面除以前面就是：

$\dfrac{k!\prod\limits_{c\in S}cnt_c!}{n!\prod\limits_{c\in S}(cnt_c/2)!}$

那么考虑一下 $n$ 为奇数的情况，唯一变化的就是 $A$ 序列的长度比 $B$ 多了 $1$，我们设 $A'=A_{1,\cdots, k}$，则有：

\begin{align} Pr[A>B]&=Pr[A'>B]+Pr[A'=B]\\ &=Pr[A'<B]+Pr[A'=B]\\ &=Pr[A<B]+Pr[A'=B]\\ &=1-Pr[A>B]+Pr[A'=B]\\ &=\dfrac{1+Pr[A'=B]}{2} \end{align}

还是类似上面求即可，唯一一个出现了奇数次的放最后。

Source code - Virtual Judge (vjudge.net.cn)