并
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 262144/262144K (Java/Other)
Total Submission(s) : 4 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
平面直角坐标系上有 $n$ 个矩形，其中第 $i$ 个的左上角坐标为 $(x_{i,1},y_{i,1})$，右下角坐标为 $(x_{i,2},y_{i,2})$。
对于 $k \in [1,n]$，求解在 $n$ 个矩形中随机选取 $k$ 个不同的矩形，其所有覆盖部分的并集的面积的期望值，答案对 $998244353$ 取模。
对于 $k \in [1,n]$，求解在 $n$ 个矩形中随机选取 $k$ 个不同的矩形，其所有覆盖部分的并集的面积的期望值，答案对 $998244353$ 取模。
Input
第一行包含 $1$ 个正整数 $n$ （$1 \leq n \leq 2 \times 10^3$）。
之后 $n$ 行，每行给定四个参数 $x_{i,1},y_{i,1},x_{i,2},y_{i,2}$，保证有 $1 \leq x_{i,1} < x_{i,2} \leq 10^9,1 \leq y_{i,1} < y_{i,2 }\leq 10^9$。
之后 $n$ 行，每行给定四个参数 $x_{i,1},y_{i,1},x_{i,2},y_{i,2}$，保证有 $1 \leq x_{i,1} < x_{i,2} \leq 10^9,1 \leq y_{i,1} < y_{i,2 }\leq 10^9$。
Output
输出共 $n$ 行，第 $i$ 行输出 $1$ 个整数，表示 $k=i$ 时的答案。
Sample Input
3 1 1 2 2 3 3 4 4 1 1 4 4
Sample Output
665496239 665496242 9
Source
2024“钉耙编程”中国大学生算法设计超级联赛（1）