← 返回题目列表

AtCoder · abc273_h

Ex. 反转 (0,1) 插入 (1,0)n

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

分数: 600 点

问题陈述

我们有一个序列 A 由整数对组成。 最初, A = ( (0, 1), (1, 0) ).

您可以对 A 任意次数(可能为零):

  • 选择 相邻 两个整数对 (a, b) 和 (c, d),然后插入 (a + c, b + d) 他们之间。

对于序列 T 由整数对组成,让我们定义 f(T) 如下:

  • 让 f(T) = (使每个元素所需的最少操作数 T 包含在 A).
    • 我们说“每个元素 T 包含在 A" 如果,对于所有元素 x 包含在 T, x 包含在(由包含在的元素组成的集合中) A).
  • 这里,如果没有这样的操作,让 f(T) = 0.

有一个序列 S = ((a_1, b_1), (a_2, b_2), \dots, (a_N, b_N)) 组成 N 整数对。 在这里,所有元素 S 成对不同。
有 \frac{N \times (N+1)}{2} 可能的连续子数组 S_{l,r}=((a_l,b_l),(a_{l+1},b_{l+1}),\dots,(a_r,b_r)) of S。 求总和,取模 998244353,属于 f(S_{l,r}) 在这些子数组上。
正式地,找到 \displaystyle \sum^{N} _ {l=1} \sum^{N} _ {r=l} f(S_{l,r}),模数 998244353.

约束

  • 1 \le N \le 10^5
  • 0 \le a_i,b_i \le 10^9
  • a_i \neq a_j or b_i \neq b_j,如果 i \neq j.

输入

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

N
a_1 b_1
a_2 b_2
\dots
a_N b_N

输出

将答案打印为整数。


示例输入 1

7
1 2
3 7
3 5
0 0
1000000000 1
0 1
6 3

示例输出 1

3511324
  • f(S_{1,1})=2.
    • 我们可以使 ((0,1),(1,0)) \rightarrow ((0,1),(1,1),(1,0)) \rightarrow ((0,1),(1,2),(1,1),(1,0)).
  • f(S_{1,2})=5.
  • f(S_{1,3})=7.
  • f(S_{2,2})=5.
  • f(S_{2,3})=7.
  • f(S_{3,3})=4.
  • f(S_{5,5})=1000000000 = 10^9.
  • f(S_{5,6})=1000000000 = 10^9.
  • f(S_{6,6})=0.
    • (0, 1) 最初包含在 A.
  • f(S_{l,r})=0 对于所有人 S_{l,r} 上面没有提到。
    • 我们可以证明 A 永远不能包含 (0,0) or (6,3) 无论操作如何。

因此,总和 f(S_{l,r}) is 2000000030 = 2 \times 10^9 + 30,除以后的余数 998244353 is 3511324.