102737: [AtCoder]ABC273 Ex - Inv(0,1)ving Insert(1,0)n
Description
Score : $600$ points
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$.
Input
Output
分数：$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$中"，如果$T$中包含的所有元素$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}$种可能。对于这些子数组，求$f(S_{l,r})$的和，模$998244353$。
正式地说，求$\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$或$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)$或$(6,3)$。
因此，$f(S_{l,r})$的和为$2000000030 = 2 \times 10^9 + 30$，将其除以$998244353$的余数为$3511324$。