幻想世界(dream)
题目背景
小 K 喝完毒奶后,很向往美丽的幻想世界,于是小 C 带他前去游玩。他们遇到了擅长魔法的少女小 ω。为了迎接二人,小 ω 决定举办篝火晚会,她生成火焰的过程让小 C 想到了一道题。
题目描述
小 ω 使用彗星和陨石生成火焰。开始时有 n 颗彗星和 n 块陨石。她不断执行以下过程,直到材料耗尽:
- 如果只剩 k 颗彗星、没有陨石,则消耗全部彗星,生成 ak 单位火焰。
- 如果只剩 k 块陨石、没有彗星,则消耗全部陨石,生成 bk 单位火焰。
- 如果两种材料都有,则以概率 p 消耗一颗彗星并生成 α 单位火焰,以概率 q 消耗一块陨石并生成 β 单位火焰,以概率 1−p−q 直接丢弃全部剩余材料;丢弃材料不产生火焰。
设 f(i,j) 表示从 i 颗彗星、j 块陨石开始,最终生成的火焰总量的期望。因此 f(0,0)=0,f(i,0)=ai,f(0,j)=bj,其中 1≤i,j≤n。
小 K 想知道整个 (n+1)×(n+1) 矩阵 f 的哈希值。给定底数 h,请计算
$$\left(\sum_{i=0}^{n}\sum_{j=0}^{n}h^{i(n+1)+j}f(i,j)\right)\bmod998244353.$$
期望值是有理数。模意义下的除法使用分母在模 998244353 下的乘法逆元。
输入格式
第一行四个整数 n,h,α,β。
第二行四个整数 pa,pb,qa,qb,表示 p=pa/pb、q=qa/qb。
第三行 n 个整数 a1,a2,…,an。
第四行 n 个整数 b1,b2,…,bn。
输出格式
输出一个整数,表示矩阵 f 的哈希值。
样例 1 输入
1 10 1 4
1 2 1 3
8
9
样例 1 输出
9890
样例 1 解释
f=(0899).
其他样例
原题另给出以下选手目录中的样例文件;当前本地题目附件未包含这些公开样例:
| 样例 |
输入文件 |
答案文件 |
满足的子任务 |
| 2 |
dream/dream2.in |
dream/dream2.ans |
1 |
| 3 |
dream/dream3.in |
dream/dream3.ans |
4 |
| 4 |
dream/dream4.in |
dream/dream4.ans |
5 |
数据范围与子任务
所有数据满足:
- 1≤n≤2×105。
- 0≤α,β,ak,bk<998244353。
- 0≤pa,qa<998244353,1≤pb,qb<998244353。
- 作为实数概率,0≤p+q≤1。
- 2≤h<998244353。
定义 γ=(pα+qβ)mod998244353。
| 子任务 |
分值 |
特殊约定 |
依赖的子任务 |
| 1 |
10 |
n≤1000 |
无 |
| 2 |
3 |
p=γ=0 |
| 3 |
7 |
p=0 |
2 |
| 4 |
20 |
γ=0 |
| 5 |
所有 ak=bk=0 |
无 |
| 6 |
40 |
无 |
1、2、3、4、5 |