Ex - Inv(0,1)ving Insert(1,0)n

AtCoder

IDabc273_h

Time6000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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

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$.

API Response (JSON)

{
  "problem": {
    "name": "Ex - Inv(0,1)ving Insert(1,0)n",
    "description": {
      "content": "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 **adjacen",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc273_h"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have a sequence $A$ consisting of integer pairs. Initially, $A = ( (0, 1), (1, 0) )$.\nYou may perform the following operation on $A$ as many (possibly zero) times as you want:\n\n*   choose **adjacen...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments