U590277 y.y Medians

zr2665

给定一个排列 $p$ ．要求计算 $p$ 的每个前缀的中位数． $n$ 个数的中位数是这些数中第 $\lceil n / 2\rceil$ 小的数． 举个例子 $\{1,2,3,4,5,6\}$ 的中位数是 $3,\{1,2,4,8,16\}$ 的中位数是 4 ． 因为输入量很大，排列用以下方法生成 $$ a_i=\left(a_{i-1} * 998244353+10^9+7\right) \bmod \left(10^9+9\right), p_i=i $$ 然后 $i$ 从 1 到 $n$ ，交换 $p_i$ 和 $p_{\left(a_i \bmod i\right)+1}$ 这样就得到了排列 $p$ ．

一行两个整数 $n$ 和 $a_0$

记 $a n s_i$ 表示 $p_{1 . . . i}$ 的中位数，输出 $\sum\left(a n s_i * 19^i\right) \bmod 998244353$ ．

$\begin{aligned} & a_0 \leq 10^9 \\ & \text { subtask1(30pts): } n \leq 1000 \\ & \text { subtask2(20pts): } n \leq 6000 \\ & \text { subtask3(30pts): } n \leq 100000 \\ & \text { subtask4(20pts): } n \leq 10^7\end{aligned}$