P10286 "RiOI-03" A Journey to the Moonlight (Enhanced Version)

Compared with [P9919](/problem/P9919), this problem has a larger Constraints range.

For a bipartite graph $G$ with $m$ vertices on the right side, define its weight $w(G)$ as follows: - Choose a matching scheme, and mark the first matched right-side vertex. If no such vertex exists, then mark the first unmatched right-side vertex. - Each time, randomly choose a permutation of $1,2,\cdots,m$. Stop when the unmatched right-side vertices and the marked vertex **appear as a contiguous segment in the permutation in increasing label order**. - $w(G)$ is the **minimum value** of the expected number of operations over all matching schemes. Define this bipartite graph $G$ to be **$k$-valid** if and only if: - The degree of every left-side vertex is between $k$ and $\color{red}2$. - There do not exist two different left-side vertices whose sets of adjacent vertices are identical. Let $f(k,x)$ be the sum of $w(G)$ over all $k$-valid bipartite graphs $G$ with $x$ right-side vertices, where left-side vertices are not distinguished. Given $n,k,a_{0\sim n}$, compute $\sum\limits^n_i a_i f(k,i) \bmod998244353$.

The first line contains two positive integers $n,k$. The second line contains $n+1$ non-negative integers, representing $a_{0\sim n}$.

Output one non-negative integer, the answer.

By convention, a left-side vertex connected to right-side vertices numbered $x,y$ is denoted as $(x,y)$. #### [Sample 1 Explanation] For $n=0,1$, the answers are clearly $1,2$. For $n=2$, the possible bipartite graphs are (represented by the tuple formed by the neighbors of each left-side vertex): $()$ $(1),(2),(1,2)$ $\{(1),(2)\},\{(1,2),(2)\},\{(1,2),(1)\},\{(1,2),(1),(2)\}$ Graphs with the same expectation are grouped together. The answer is $\dfrac21+\dfrac21\times3+\dfrac22\times4=12$, so the output is $1\times1+1\times2+1\times12=15$. #### [Sample 2 Explanation] For $n=0,1,2$, the answers are $1,1,4$. For $n=3$, the possible bipartite graphs are (represented by the tuple formed by the neighbors of each left-side vertex): $()$ $(1,2),(1,3),(2,3)$ $\{(1,2),(1,3)\},\{(1,2),(2,3)\},\{(1,3),(2,3)\}$ $\{(1,2),(2,3),(1,3)\}$ The answer is $\dfrac61+\dfrac61\times3+\dfrac62\times3+\dfrac66=34$. #### [Constraints] For $100\%$ of the testdata, $0\le n\le10^5$, $1\le k\le2$, $0\le a_i