U229851 [sxyz NOIP 模拟赛]3 字符重排（string）

[sxyz NOIP 模拟赛]3 字符重排（string）T3 ------------ 2s 512MB

给定一个长度为 n 的仅包含大小写字母的字符串，其中 n 是偶数，字符串的下标从 1 开始 你可以将这个字符串的字符进行重排，我们定义一个重排合法，当且仅当对于所有在字符串中出现过的同种字符，其重排后均分布于字符串的左半部分或右半部分。 接下来你需要回答 q 次询问，每次询问会给出两个下标 x, y，你需要求出所有合法的重排方案中，sx, sy 被排到同一半（都是左半或都是右半）的方案数是多少。由于答案可能很大，你只需要输出答案对 998244353 取模的结果即可。两种重排方案是不同的，当且仅当重排后的两个字符串是不同的。

第一行一个字符串 第二行一个整数 q 接下来 q 行，每行两个整数，表示一次询问

对于每次询问输出一行一个整数，表示答案。

3.4 数据范围与提示 对于 20% 的数据，n ≤ 10, q = 1 对于 40% 的数据，n ≤ 20 对于 80% 的数据，n ≤ $10^4$ 对于所有数据，2 ≤ n ≤ $10^5$, 1 ≤ q ≤ $10^5$, 1 ≤ x, y ≤ n