#PQJ1854x9633. QOJ 1854_9633

    ID: 2728 传统题 2000ms 2048MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测动态规划

QOJ 1854_9633

标题: 轮盘赌游戏 - Problem - QOJ.ac

#9633. 轮盘赌游戏

Statistics

The problem was used in the following contests:

题目描述

一个有 n 颗子弹的轮盘,子弹依次编号为 0,1,…,n−1,每一颗子弹有一个卡壳概率 pi,表示如果即将激发的子弹是第 i 颗,那么它有 pi 的概率卡壳不能被打出,有 1−pi 的概率成功打出。

轮盘赌游戏的规则如下:均匀随机地从 n 颗子弹中选择一颗子弹开始进行轮盘赌,每一轮都会激发一颗子弹,假设某一轮激发第 i 颗子弹,如果子弹成功打出了,那么游戏结束;否则轮盘会向后旋转 d 颗子弹,游戏进入下一轮,也就是即将激发的子弹会变成第 (i+d)modn 颗。小 X 想要知道轮盘赌游戏结束轮数的期望。

由于子弹的生产都是 m 颗一盒生产的,而且生产质量是一致的,所以可以认为存在一个长度为 m 的序列 pi′,使得对于轮盘里的 n 颗子弹,有:pi=pimodm′ (i=0,1,…,n−1)。

为了增加游戏的乐趣,小 X 找到了 q 枚特殊的子弹,他将会用这些子弹替换掉轮盘中的某一些子弹。小 X 将形式化地告诉你这个替换的过程。

小 X 的每一颗特殊子弹都可以看作是一个二元组 (x,y),表示这一颗子弹可以替换掉轮盘中的编号为 x 子弹,让这一颗子弹的卡壳概率变成 y。

小 X 的每一次替换都可以看作是一个二元组集合 S(保证 S 中的所有二元组 (x,y) 中 x 互不相同),对于所有的 (x,y)∈S,小 X 会将序列上的编号为 x 颗子弹替换掉,让这颗子弹的卡壳概率变成 y。

而对于一个二元组集合 S(也就是一次替换),记 f(S) 为用完成替换之后的子弹进行轮盘赌游戏,游戏结束轮数的期望。

小 X 会以如下方式生成 q+t 个替换:

  • 其中前 q 个替换的生成方式如下:第 i 个替换为 Si=(xi,yi) 。
  • 后 t 个替换的生成方式如下:第 q+j 个替换是给定两个编号比它小且没有被选择过的替换,将其合并得到的结果。具体的,选择第 aj 和 bj 个替换(aj,bj<q+j),那么有第 q+j 个替换为 Sq+j=Saj∪Sbj。

小 X 想要求出 f(∅),以及 f(Si),i=1,2,…,q+t,但是小 X 还要去解决其他的问题,所以他找到了你。

你需要告诉小 X f(∅), f(Si)(i=1,2,…,q+t)乘 n 之后的结果,由于结果可能较大且不一定为整数,所以你只需要输出其对 998244353 取模后的结果。

输入格式

第一行输入五个数 n,m,d,q,t。

第二行输入 m 个数,其中第 i 个数为 pi−1′。

接下来的 q 行,每行两个数 xi,yi,表示 Si=(xi,yi)。

接下来的 t 行,每行两个数 ai,bi,表示 Si+q=Sai∪Sbi。

输出格式

共 1+q+t 行,其中第一行为 n×f(∅),接下来第 i+1 行为 n×f(Si) 。

样例

样例输入 1
3 3 1 2 1
1 499122177 0
0 499122177
1 1
1 2
样例输出 1
5
748683269
6
5
样例解释

12≡499122177(mod998244353),所以可以认为三颗子弹的卡壳概率为 1,12,0。

对于 f(∅),序列为 1,12,0,第一颗子弹进行的期望轮数为 2×12+3×12=52,第二颗子弹进行的期望轮数为 1×12+2×12=32,第三颗子弹的期望轮数为 1,最终答案为 52+32+1=5。

S1=(0,12),替换后的序列为 12,12,0,答案为 (1×12+2×14+3×14)+(1×12+2×12)+1=74,74≡748683269(mod998244353)。

S2=(1,1),替换后的序列为 1,1,0,答案为 3+2+1=6。

S3=S1∪S2=(0,12),(1,1),替换后的序列为 12,1,0,答案为 (1×12+3×12)+2+1=5。

数据范围

对于所有数据满足:1≤d≤n≤1016,m≤5000。1≤q,t≤105,0≤xi<n 且 ∀i≠j,xi≠xj,0≤pi′,yi<998244353,1≤ai,bi<i+q 且保证所有的 ai,bi 均不相同,数据保证 gcd(d,n)=1,且对于任何询问,所有子弹被卡壳的概率之积对 998244353 取模不等于 1。

  • Subtask 1(10 pts):1≤q,t,n≤103。
  • Subtask 2(15 pts):1≤n≤106。
  • Subtask 3(30 pts):d=1。
  • Subtask 4(20 pts):q=t=0。
  • Subtask 5(25 pts):无特殊限制。