Ex - Inv(0,1)ving Insert(1,0)n 解説 /

実行時間制限: 6 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

整数組からなる列 A があります。はじめ A = ( (0, 1), (1, 0) ) です。

あなたは A に対して次の操作を 0 回以上何度でも行うことができます。

  • 隣り合う 2 つの整数組 (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 の連続部分列 S_{l,r}=((a_l,b_l),(a_{l+1},b_{l+1}),\dots,(a_r,b_r)) として考えられるものは \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
  • i \neq j ならば、 a_i \neq a_j または b_i \neq b_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 に含まれています。
  • 上述されていない S_{l,r} について、 f(S_{l,r})=0 です。
    • A にどのように操作を行っても、 (0,0) や (6,3) が含まれる状態にはできないことが証明できます。

以上より、 f(S_{l,r}) の総和は 2000000030 = 2 \times 10^9 + 30 であり、それを 998244353 で割った余りは 3511324 です。

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.