Score : $600$ points

问题陈述

我们有一个由整数对组成的序列 $A$。初始时，$A = ( (0, 1), (1, 0) )$。

你可以对序列 $A$ 进行任意多次（包括零次）以下操作：

• 选择 相邻 的两个整数对 $(a, b)$ 和 $(c, d)$，并在它们之间插入整数对 $(a + c, b + d)$。

对于一个由整数对组成的序列 $T$，我们定义函数 $f(T)$ 如下：

• 设 $f(T) =$ （使 $T$ 中每个元素都被包含在 $A$ 中所需的最小操作次数）。
  • 我们称“$T$ 中的每个元素都被包含在 $A$ 中”是指，对于 $T$ 中的所有元素 $x$，$x$ 都属于（由 $A$ 中元素构成的集合）。
• 若不存在这样的操作，则令 $f(T) = 0$。

存在一个由 $N$ 个整数对组成的序列 $S = ((a_1, b_1), (a_2, b_2), \dots, (a_N, b_N))$，其中 $S$ 中的所有元素两两不同。
$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))$。求这些子数组中 $f(S_{l,r})$ 的和，取模 $998244353$ 后的结果。
形式上，要求解 $\displaystyle \sum^{N} _ {l=1} \sum^{N} _ {r=l} f(S_{l,r})$，并对结果取模 $998244353$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have a sequence $A$ consisting of integer pairs. Initially, $A = ( (0, 1), (1, 0) )$.

You may perform the following operation on $A$ as many (possibly zero) times as you want:

• choose adjacent two integer pairs $(a, b)$ and $(c, d)$, and insert $(a + c, b + d)$ between them.

For a sequence $T$ consisting of integer pairs, let us define $f(T)$ as follows:

• let $f(T) =$ (the minimum number of operations required to make every element of $T$ contained in $A$).
  • We say that "every element of $T$ is contained in $A$" if, for all elements $x$ contained in $T$, $x$ is contained in (the set consisting of the elements contained in $A$).
• Here, if there are no such operations, let $f(T) = 0$.

There is a sequence $S = ((a_1, b_1), (a_2, b_2), \dots, (a_N, b_N))$ consisting of $N$ integer pairs. Here, all elements of $S$ are pairwise distinct.
There are $\frac{N \times (N+1)}{2}$ possible consecutive subarrays $S_{l,r}=((a_l,b_l),(a_{l+1},b_{l+1}),\dots,(a_r,b_r))$ of $S$. Find the sum, modulo $998244353$, of $f(S_{l,r})$ over those subarrays.
Formally, find $\displaystyle \sum^{N} _ {l=1} \sum^{N} _ {r=l} f(S_{l,r})$, modulo $998244353$.

Constraints

• $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$, if $i \neq j$.

Input

The input is given from Standard Input in the following format:

$N$

$a_1$ $b_1$

$a_2$ $b_2$

$\dots$

$a_N$ $b_N$

Output

Print the answer as an integer.

Sample Input 1

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

Sample Output 1

3511324

• $f(S_{1,1})=2$.
  • We can make $((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)$ is originally contained in $A$.
• $f(S_{l,r})=0$ for all $S_{l,r}$ not mentioned above.
  • We can prove that $A$ can never contain $(0,0)$ or $(6,3)$ regardless of operations.

Therefore, the sum of $f(S_{l,r})$ is $2000000030 = 2 \times 10^9 + 30$, whose remainder when divided by $998244353$ is $3511324$.

update @ 2024/3/10 11:31:40