#P6774. [2019备战noi]幻想世界

    ID: 6594 传统题 1500ms 512MiB 尝试: 7 已通过: 2 难度: 8 上传者: 标签>难度分类提高+/省选-动态规划期望 DP组合数学贡献法构造与建模交换求和顺序格路计数排序与序列处理一维前缀和阶乘逆元预处理多项式与生成函数卷积转化NTTCF2500

[2019备战noi]幻想世界

幻想世界(dream)

题目背景

小 K 喝完毒奶后,很向往美丽的幻想世界,于是小 C 带他前去游玩。他们遇到了擅长魔法的少女小 ω\omega。为了迎接二人,小 ω\omega 决定举办篝火晚会,她生成火焰的过程让小 C 想到了一道题。

题目描述

小 ω\omega 使用彗星和陨石生成火焰。开始时有 nn 颗彗星和 nn 块陨石。她不断执行以下过程,直到材料耗尽:

  • 如果只剩 kk 颗彗星、没有陨石,则消耗全部彗星,生成 aka_k 单位火焰。
  • 如果只剩 kk 块陨石、没有彗星,则消耗全部陨石,生成 bkb_k 单位火焰。
  • 如果两种材料都有,则以概率 pp 消耗一颗彗星并生成 α\alpha 单位火焰,以概率 qq 消耗一块陨石并生成 β\beta 单位火焰,以概率 1−p−q1-p-q 直接丢弃全部剩余材料;丢弃材料不产生火焰。

设 f(i,j)f(i,j) 表示从 ii 颗彗星、jj 块陨石开始,最终生成的火焰总量的期望。因此 f(0,0)=0f(0,0)=0,f(i,0)=aif(i,0)=a_i,f(0,j)=bjf(0,j)=b_j,其中 1≤i,j≤n1\le i,j\le n。

小 K 想知道整个 (n+1)×(n+1)(n+1)\times(n+1) 矩阵 ff 的哈希值。给定底数 hh,请计算

$$\left(\sum_{i=0}^{n}\sum_{j=0}^{n}h^{i(n+1)+j}f(i,j)\right)\bmod998244353.$$

期望值是有理数。模意义下的除法使用分母在模 998244353998244353 下的乘法逆元。

输入格式

第一行四个整数 n,h,α,βn,h,\alpha,\beta。

第二行四个整数 pa,pb,qa,qbp_a,p_b,q_a,q_b,表示 p=pa/pbp=p_a/p_b、q=qa/qbq=q_a/q_b。

第三行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

第四行 nn 个整数 b1,b2,…,bnb_1,b_2,\ldots,b_n。

输出格式

输出一个整数,表示矩阵 ff 的哈希值。

样例 1 输入

1 10 1 4
1 2 1 3
8
9

样例 1 输出

9890

样例 1 解释

f=(0989).f=\begin{pmatrix}0&9\\8&9\end{pmatrix}.

其他样例

原题另给出以下选手目录中的样例文件;当前本地题目附件未包含这些公开样例:

样例 输入文件 答案文件 满足的子任务
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×1051\le n\le2\times10^5。
  • 0≤α,β,ak,bk<9982443530\le\alpha,\beta,a_k,b_k<998244353。
  • 0≤pa,qa<9982443530\le p_a,q_a<998244353,1≤pb,qb<9982443531\le p_b,q_b<998244353。
  • 作为实数概率,0≤p+q≤10\le p+q\le1。
  • 2≤h<9982443532\le h<998244353。

定义 γ=(pα+qβ) mod 998244353\gamma=(p\alpha+q\beta)\bmod998244353。

子任务 分值 特殊约定 依赖的子任务
1 1010 n≤1000n\le1000 无
2 33 p=γ=0p=\gamma=0
3 77 p=0p=0 2
4 2020 γ=0\gamma=0
5 所有 ak=bk=0a_k=b_k=0 无
6 4040 无 1、2、3、4、5