← 返回题目列表

AtCoder · arc158_e

E. 所有对最短路径

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

分数: 800 点

问题陈述

我们有一个网格 2 行和 N 列。让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。 (i,j) 有一个正整数 x_{i,j} 。

据说两个正方形是 相邻 当他们分享立场时。

A 路径 芯片的 来自广场 X to Y 是一个序列 (P_1, \ldots, P_n) 不同的正方形使得 P_1 = X, P_n = Y,和 P_i 和 P_{i+1} 与每个相邻 1\leq i \leq n-1。此外, 重量 该路径的 是写入的整数之和 P_1, \ldots, P_n.

对于两个正方形 X 和 Y,让 f(X, Y) 表示从 X to Y。求总和 f(X, Y) 在所有方块对上 (X,Y),模数 998244353.

约束

  • 1\leq N\leq 2\times 10^5
  • 1\leq x_{i,j} \leq 10^9

输入

输入由标准输入按以下格式给出:

N
x_{1,1} \ldots x_{1,N}
x_{2,1} \ldots x_{2,N}

输出

打印总和 f(X, Y) 在所有方块对上 (X,Y),模数 998244353.


示例输入 1

1
3
5

示例输出 1

24

您应该找到以下四个值的总和。

  • 对于 X = (1,1), Y = (1,1): f(X, Y) = 3.
  • 对于 X = (1,1), Y = (2,1): f(X, Y) = 8.
  • 对于 X = (2,1), Y = (1,1): f(X, Y) = 8.
  • 对于 X = (2,1), Y = (2,1): f(X, Y) = 5.

示例输入 2

2
1 2
3 4

示例输出 2

76

示例输入 3

5
1 1000000000 1 1 1
1 1 1 1000000000 1

示例输出 3

66714886