CF1948F.Rare Coins

有 $n$ 个袋子，编号从 $1$ 到 $n$，第 $i$ 个袋子中有 $a_i$ 个金币和 $b_i$ 个银币。

每个金币的价值为 $1$。每个银币的价值独立地为 $0$ 或 $1$，其中价值为 $0$ 的概率为 $\frac{1}{2}$，价值为 $1$ 的概率也为 $\frac{1}{2}$。

你需要回答 $q$ 个独立的询问。每个询问如下：

• $l$ $r$ — 计算编号从 $l$ 到 $r$ 的袋子中硬币总价值严格大于其他所有袋子中硬币总价值的概率。

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 3 \cdot 10^5$），分别表示袋子的数量和询问的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^6$），表示第 $i$ 个袋子中的金币数量。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$0 \le b_i \le 10^6$），表示第 $i$ 个袋子中的银币数量。

接下来的 $q$ 行，每行包含两个整数 $l_j$ 和 $r_j$（$1 \le l_j \le r_j \le n$），表示第 $j$ 个询问。

输入的额外限制：

• 数组 $a$ 的元素和不超过 $10^6$；
• 数组 $b$ 的元素和不超过 $10^6$。

对于每个询问，输出一个整数，表示编号从 $l$ 到 $r$ 的袋子中硬币总价值严格大于其他所有袋子中硬币总价值的概率，结果对 $998244353$ 取模。

形式化地说，概率可以表示为最简分数 $\frac{x}{y}$。你需要输出 $x \cdot y^{-1} \bmod 998244353$，其中 $y^{-1}$ 是满足 $y \cdot y^{-1} \bmod 998244353 = 1$ 的整数。

在第一个样例的两个询问中，答案都是 $\frac{1}{4}$。

由 ChatGPT 4.1 翻译