AtCoder Beginner Contest 136
翻译中…
Problem Statement
翻译中…
We have a set $S$ of $N$ points in a two-dimensional plane. The coordinates of the $i$-th point are $(x_i, y_i)$. The $N$ points have distinct $x$-coordinates and distinct $y$-coordinates.
翻译中…
For a non-empty subset $T$ of $S$, let $f(T)$ be the number of points contained in the smallest rectangle, whose sides are parallel to the coordinate axes, that contains all the points in $T$. More formally, we define $f(T)$ as follows:
翻译中…
$f(T) :=$(the number of integers$i$$(1 \leq i \leq N)$such that$a \leq x_i \leq b$and$c \leq y_i \leq d$, where$a$,$b$,$c$, and$d$are the minimum$x$-coordinate, the maximum$x$-coordinate, the minimum$y$-coordinate, and the maximum$y$-coordinate of the points in$T$)
翻译中…
Find the sum of $f(T)$ over all non-empty subset $T$ of $S$. Since it can be enormous, print the sum modulo $998244353$.
翻译中…
Constraints
翻译中…
$1 \leq N \leq 2 \times 10^5$$-10^9 \leq x_i, y_i \leq 10^9$$x_i \neq x_j (i \neq j)$$y_i \neq y_j (i \neq j)$- All values in input are integers.
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
N
x_1 y_1
:
x_N y_N翻译中…
Output
翻译中…
Print the sum of $f(T)$ over all non-empty subset $T$ of $S$, modulo $998244353$.
翻译中…
样例
Input #1
3
-1 3
2 1
3 -2
Output #1
13
Let the first, second, and third points be $P_1$, $P_2$, and $P_3$, respectively. $S = \{P_1, P_2, P_3\}$ has seven non-empty subsets, and $f$ has the following values for each of them:
- $f(\{P_1\}) = 1$
- $f(\{P_2\}) = 1$
- $f(\{P_3\}) = 1$
- $f(\{P_1, P_2\}) = 2$
- $f(\{P_2, P_3\}) = 2$
- $f(\{P_3, P_1\}) = 3$
- $f(\{P_1, P_2, P_3\}) = 3$
The sum of these is $13$.
Input #2
4
1 4
2 1
3 3
4 2
Output #2
34
Input #3
10
19 -11
-3 -12
5 3
3 -15
8 -14
-9 -20
10 -9
0 2
-7 17
6 -6
Output #3
7222
Be sure to print the sum modulo $998244353$.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。