博弈
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 524288/524288K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
小马给出了一个可重小写字符集合 $S$。
Alice 初始时有空串 $A$，Bob 初始时有空串 $B$。
两人轮流等概率取出集合 $S$ 中的一个字符 $c$，将它拼接到自己的字符串的后面，直至 $S$ 为空，每个字符只能被取一次，Alice 先手。
如果最终 $A$ 的字典序严格大于 $B$，则 Alice 胜利，求其获胜的概率，答案对 $998244353$​ 取模。
Alice 初始时有空串 $A$，Bob 初始时有空串 $B$。
两人轮流等概率取出集合 $S$ 中的一个字符 $c$，将它拼接到自己的字符串的后面，直至 $S$ 为空，每个字符只能被取一次，Alice 先手。
如果最终 $A$ 的字典序严格大于 $B$，则 Alice 胜利，求其获胜的概率，答案对 $998244353$​ 取模。
Input
本题共 $T$ 组数据，第一行一个正整数 $T$。
之后对于每组数据，第一行一个正整数 $n$。
之后 $n$ 行，每行给出字符 $c_i$ 和一个正整数 $h_{c_i}$，表示集合 $S$ 中有 $h_{c_i}$ 个字符 $c_i$。（$1 \leq T \leq 10^4,1 \leq n \leq 26,1 \leq \sum_{i=1}^n h_{c_i }\leq 10^7$）
之后对于每组数据，第一行一个正整数 $n$。
之后 $n$ 行，每行给出字符 $c_i$ 和一个正整数 $h_{c_i}$，表示集合 $S$ 中有 $h_{c_i}$ 个字符 $c_i$。（$1 \leq T \leq 10^4,1 \leq n \leq 26,1 \leq \sum_{i=1}^n h_{c_i }\leq 10^7$）
Output
对于每组数据，输出一行，包含一个整数，表示答案。
Sample Input
1 2 a 2 b 1
Sample Output
665496236
Hint
$A=ba,B=a$ 或 $A=ab,B=a$ 满足条件，两种情况概率均为 $\frac{1}{3}$，获胜概率为 $\frac{2}{3}$。
Source
2024“钉耙编程”中国大学生算法设计超级联赛（1）