P10718 [MX-X1-T6] "KDOI-05" A Simple Graph Problem.

Original link: 。

You are given an edge-biconnected graph with $n$ vertices and $m$ edges, and the coordinates of each vertex are given. It is guaranteed that any two edges do not intersect, or only overlap at their endpoints. You are given $k$ simple cycles on the graph $C_1,C_2,\dots,C_k$. Define $G_i$ as the graph consisting of only the vertices and edges inside $C_i$. For $S\subseteq\{1,2,\dots,k\},S=\{s_1,s_2,\dots,s_t\}$, define $f(S)$ as the number of connected components in the intersection of all $G_{s_i}$. There are $q$ queries. Each time you are given a $z$, output $\sum_{S\subseteq\{1,2,\dots,k\},|S|=z}f(S)$. Take the result modulo $998244353$.

The first line contains three positive integers $n,m,k$. The next $n$ lines each contain two integers $(x_i,y_i)$, representing the coordinates of the $i$-th vertex. It is guaranteed that for all $1\leq i

Output $q$ lines. Each line contains one integer, the value of $\sum_{S\subseteq\{1,2,\dots,k\},|S|=z}f(S)$ modulo $998244353$.

**Sample Explanation \#1** The data of sample $1$ is shown in the figure:  **Constraints** **This problem uses bundled testdata.** | Subtask ID | Score | $n\leq$ | Special Property | |:--:|:--:|:--:|:--:| | $1$ | $15$ | $10$ | None | | $2$ | $30$ | $1000$ | None | | $3$ | $30$ | $4\times10^4$ | It is guaranteed that the planar graph is a triangulation of a convex hull | | $4$ | $15$ | $4\times10^4$ | None | | $5$ | $10$ | $10^5$ | None | For $100\%$ of the data: $1\leq n,\sum l_i\leq10^5$, $1\leq m\leq 3n-6$, $3\leq l_i$, $0\leq |x_i|,|y_i|\leq 10^9$, $1\leq q\leq 20$, $1\leq u_i,v_i\leq n$, $u_i\neq v_i$, $1\leq z_i\leq k$. It is guaranteed that for all $1\leq i