← 返回题目列表

Codeforces · 2045/E

E. 较窄的通道

中文机器翻译题面 查看原题

你是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]$$$。

连通区域 $$$[u, v]$$$ 的强度可以计算如下。设$$$m_1$$$和$$$m_2$$$分别为连通区域第一排和第二排士兵的最大力量。形式上,$$$m_r = \max (P_{r, u}, P_{r, u + 1}, \dots, P_{r, v})$$$ 对于 $$$r \in \{ 1, 2\}$$$。如果 $$$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

3
8 4 5
5 4 8

输出 #1

249561092

输入 #2

5
10 20 5 8 5
5 20 7 5 8

输出 #2

811073541

注意

示例输入/输出#1 的说明

该通道有 $$$8$$$ 种可能的情况。

每种情况发生的可能性相同。因此,预期总强度为 $$$(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}$$$。