F. 稀有硬币 详细题解

题目核心理解

有 $n$ 个袋子，第 $i$ 个袋子中有 $a_i$ 枚金币、$b_i$ 枚银币。

• 金币价值固定为 $1$；
• 每枚银币价值独立随机为 $0$ 或 $1$，概率均为 $\dfrac12$。

每次询问给定区间 $[l,r]$，求区间内硬币总价值严格大于区间外总价值的概率。 答案以分数模 $998244353$ 形式输出。

---

核心思路

1. 关键性质

设：

• $A$：区间内金币总数，$A'$：区间外金币总数；
• $S$：区间内银币总数，$S'$：区间外银币总数；
• $m=S+S'$：全场银币总数，固定不变；
• $x$：区间内有效银币数，$y$：区间外有效银币数。

合法条件为：

$$A+x>A'+y$$

整理可得：

$$(A-A')+x-y>0$$

2. 转化规则

每枚银币等价于有 $\dfrac12$ 概率让差值减 $1$。 令初始差值：

$$st=(A-A')+S$$

合法方案数等价于：减 $1$ 的次数不超过 $st-1$ 次。

3. 最终计算

合法方案数为组合数前缀和：

$$sum=\sum_{i=0}^{st-1}\dbinom{m}{i}$$

答案为合法方案数占总方案的比例：

$$ans=\dfrac{sum}{2^m}$$

---

算法流程

1. 预处理阶乘、逆元、组合数及前缀和；
2. 预处理金币、银币的前缀和数组；
3. 对每组询问 $[l,r]$：
   • 求出区间金币和 $A$、银币和 $S$；
   • 计算初始值 $st=2A-totA+S$；
   • 若 $st\le0$，答案为 $0$；
   • 若 $st>m$，答案为 $1$；
   • 否则答案为 $sum[st-1]\times inv(2^m)\bmod 998244353$。

---

公式与复杂度分析

答案公式：

$$ans=\dfrac{1}{2^m}\sum_{i=0}^{\min(st-1,\,m)}\dbinom{m}{i} $$

复杂度

• 预处理：$O(m)$
• 单次询问：$O(1)$
• 总体：$O(n+q+m)$

可轻松处理 $n,q\le 3\times10^5$、$\sum a_i,\sum b_i\le 10^6$ 的数据范围。