P15672 [ICPC 2024 Jakarta R] Narrower Passageway

你是 ICPC 王国的一名战略家。你收到情报，王国附近的一条狭窄通道将遭受怪物袭击。这条狭窄通道可以表示为一个有 $2$ 行（编号从 $1$ 到 $2$）和 $N$ 列（编号从 $1$ 到 $N$）的网格。记 $(r, c)$ 为第 $r$ 行第 $c$ 列的单元格。每天，都会有一名力量为 $P_{r, c}$ 的士兵被指派保护 $(r, c)$。 已知该通道雾气很重。在一天之内，通道中的每一列都有 $50\%$ 的概率被雾气笼罩。如果一列被雾气笼罩，那么当天指派到该列的两名士兵就不会被部署。否则，指派的士兵将被部署。 定义一个**连通区域** $[u, v]$（$u \leq v$）为一个从 $u$ 到 $v$（包含两端）的、最大的连续列集合，使得该集合中的每一列都没有被雾气笼罩。下图是连通区域的一个示例。灰色单元格表示被雾气笼罩的单元格。共有 $4$ 个连通区域：$[1, 2]$、$[4, 6]$、$[9, 9]$ 和 $[11, 11]$。 :::align{center}  ::: 一个连通区域 $[u, v]$ 的**强度**可以按如下方式计算。设 $m_1$ 和 $m_2$ 分别为该连通区域第一行和第二行中士兵力量的最大值。形式化地，对于 $r \in \{1, 2\}$，有 $m_r = \max (P_{r, u}, P_{r, u + 1}, \dots, P_{r, v})$。如果 $m_1 = m_2$，则强度为 $0$。否则，强度为 $\min (m_1, m_2)$。 部署的**总强度**是所有连通区域的强度之和。请确定任意一天部署的期望总强度。

第一行包含一个整数 $N$（$1 \leq N \leq 100\,000$）。 接下来的两行，每行包含 $N$ 个整数 $P_{r, c}$（$1 \leq P_{r, c} \leq 200\,000$）。

令 $M = 998\,244\,353$。可以证明，期望总强度可以表示为一个不可约分数 $\frac{x}{y}$，其中 $x$ 和 $y$ 是整数，且 $y \not\equiv 0 \pmod{M}$。在一行中输出一个整数 $k$，满足 $0 \leq k < M$ 且 $k \cdot y \equiv x \pmod{M}$。

**样例输入/输出 #1 的解释** 通道有 $8$ 种可能的情况。 :::align{center}  ::: 每种情况发生的概率相等。因此，期望总强度为 $(0 + 5 + 10 + 5 + 5 + 0 + 5 + 0) / 8 = \frac{15}{4}$。由于 $249\,561\,092 \cdot 4 \equiv 15 \pmod{998\,244\,353}$，所以本样例的输出是 $249\,561\,092$。 **样例输入/输出 #2 的解释** 期望总强度为 $\frac{67}{16}$。 翻译由 DeepSeek V3.2 完成