P12488 [集训队互测 2024] 轮盘赌游戏

一个有 $n$ 颗子弹的轮盘，子弹依次编号为 $0,1,\dots n-1$，每一颗子弹有一个卡壳概率 $p_i$，表示如果即将激发的子弹是第 $i$ 颗，那么它有 $p_i$ 的概率卡壳不能被打出，有 $1-p_i$ 的概率成功打出。 轮盘赌游戏的规则如下：均匀随机地从 $n$ 颗子弹中选择一颗子弹开始进行轮盘赌，每一轮都会激发一颗子弹，假设某一轮激发第 $i$ 颗子弹，如果子弹成功打出了，那么游戏结束；否则轮盘会向后旋转 $d$ 颗子弹，游戏进入下一轮，也就是即将激发的子弹会变成第 $(i+d)\bmod n$ 颗。小 X 想要知道轮盘赌游戏结束轮数的期望。 由于子弹的生产都是 $m$ 颗一盒生产的，而且生产质量是一致的，所以可以认为存在一个长度为 $m$ 的序列 $p_i'$，使得对于轮盘里的 $n$ 颗子弹，有：$p_i=p_{i\bmod m}',i=0,1\dots n-1$。 为了增加游戏的乐趣，小 X 找到了 $q$ 枚特殊的子弹，他将会用这些子弹替换掉轮盘中的某一些子弹。小 X 将形式化地告诉你这个替换的过程。 小 X 的每一颗特殊子弹都可以看作是一个二元组 $(x,y)$，表示这一颗子弹可以替换掉轮盘中的编号为 $x$ 子弹，让这一颗子弹的卡壳概率变成 $y$。 小 X 的每一次替换都可以看作是一个二元组集合 $S$（保证 $S$ 中的所有二元组 $(x,y)$ 中 $x$ 互不相同），对于所有的 $(x,y)\in S$，小 X 会将序列上的编号为 $x$ 颗子弹替换掉，让这颗子弹的卡壳概率变成 $y$。 而对于一个二元组集合 $S$（也就是一次替换），记 $f(S)$ 为用**完成替换之后**的子弹进行轮盘赌游戏，游戏结束轮数的期望。 小 X 会以如下方式生成 $q+t$ 个替换： * 其中前 $q$ 个替换的生成方式如下：第 $i$ 个替换为 $S_i=\{(x_i,y_i)\}$ 。 * 后 $t$ 个替换的生成方式如下：第 $q+j$ 个替换是给定两个编号比它小且**没有被选择过**的替换，将其合并得到的结果。具体的，选择第 $a_j$ 和 $b_j$ 个替换（$a_j,b_j

第一行输入五个数 $n,m,d,q,t$。 第二行输入 $m$ 个数，其中第 $i$ 个数为 $p'_{i-1}$。 接下来的 $q$ 行，每行两个数 $x_i,y_i$，表示 $S_i=\{(x_i,y_i)\}$。 接下来的 $t$ 行，每行两个数 $a_i,b_i$，表示 $S_{i+q}=S_{a_i}\cup S_{b_i}$。

共 $1+q+t$ 行，其中第一行为 $n\times f(\varnothing)$，接下来第 $i+1$ 行为 $n\times f(S_i)$ 。

#### 样例解释 $\dfrac{1}{2}\equiv 499122177\pmod {998244353}$，所以可以认为三颗子弹的卡壳概率为 $1,\dfrac{1}{2},0$。 对于 $f(\varnothing)$，序列为 $1,\dfrac{1}{2},0$，第一颗子弹进行的期望轮数为 $2\times \dfrac{1}{2}+3\times \dfrac{1}{2}=\dfrac{5}{2}$，第二颗子弹进行的期望轮数为 $1\times \dfrac{1}{2}+2\times \dfrac{1}{2}=\dfrac{3}{2}$，第三颗子弹的期望轮数为 $1$，最终答案为 $\dfrac{5}{2}+\dfrac{3}{2}+1=5$。 $S_1=\{(0,\dfrac{1}{2})\}$，替换后的序列为 $\dfrac{1}{2},\dfrac{1}{2},0$，答案为 $(1\times \dfrac{1}{2}+2\times \dfrac{1}{4}+3\times \dfrac{1}{4})+(1\times \dfrac{1}{2}+2\times \dfrac{1}{2})+1=\dfrac{17}{4}$，$\dfrac{17}{4}\equiv 748683269\pmod {998244353}$。 $S_2=\{(1,1)\}$，替换后的序列为 $1,1,0$，答案为 $3+2+1=6$。 $S_3=S_1\cup S_2=\{(0,\dfrac{1}{2}),(1,1)\}$，替换后的序列为 $\dfrac{1}{2},1,0$，答案为 $(1\times \dfrac{1}{2}+3\times \dfrac{1}{2})+2+1=5$。 ### 数据范围 对于所有数据满足：$1\le d\le n\le 10^{16}$，$m\le 5000$。$1\le q,t\le 10^5$，$0\le x_i< n$ 且 $\forall i\neq j,x_i\neq x_j$，$0\le p'_i,y_i