Problem 4079 --幸福前方的物语

4079: 幸福前方的物语

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

"想要传达的,仅仅只有一件是将瞬间保存下来的永远。"

小 A 曾经是绘画的天才,他可以奇迹般地将他所见的一切通过绘画记录下来。但如今的他因为事故失去了用惯用手作画的能力。不过,好在是小 A 还没有放弃绘画,他尝试用自己曾经锻炼出来的技巧以及他的毅力再一次向绘画挑战。

具体的,小 A 定义一副画的价值为 f(l, r) (lr , ),表示在集合 S = {l, l + 1, ..., r} 中选取一些数,满足选出的数字的乘积为完全平方数的方案数。小 A 画出一副价值为 f(l, r) 的画,意味着小 A 把绘画中的每个元素与数字中的 {l, l + 1, ..., r} 一一对应。对于一个选取方案 U = {x0, ..., xk} () 满足  为完全平方数,小 A 认为这对应了一种艺术审美视角,因此会使画的价值提升。注意:其中空集也算一种合法的选法。

曾经的小 A 可以控制参数 l, r ,但如今他失去了曾经的能力。不过好在他的身体替他记住了曾经的绘画技巧,于是他可以控制绘画的大体走向,但是小范围的细节仍然会有波动。也就是现在他所做出的画实际的价值为 f(l + x, r - y)。其中 x , y 是两个随机的参数。对于每一个正整数 i (1 ≤ in),x = i 的概率为 piy = i 的概率为 qi

设 l' = l + x, r' = r - y, d = r' - l', 小 A 想知道,对于所有的 d = r - l - 2n + 1, r - l - 2n + 2, ..., r - l - 1 ,其中画作的期望权值为多少。

答案对 998244353 取模后输出。

设答案的最简真分数形式可以表示成 ,输出 P × Q - 1 ± od {998244353} 的结果。数据保证 Q 不为 998244353 的倍数。

第一行输入三个正整数,n, l, r 分别表示随机参数的范围以及两个固定的参数。(1 ≤ n ≤ 105,1 ≤ l, r ≤ 107,r - l ≥ 5 × 105 , )。

第二行输入 n 个正整数 pi' (1 ≤ pi' ≤ 103),其中真实的 pi 即随机参数 x = i 的概率可以表示为 

第三行输入 n 个正整数 qi' (1 ≤ qi' ≤ 103),其中真实的 qi 即随机参数 y = i 的概率可以表示为 

输出总共 2 × n - 2 个整数,第 i 个整数表示对于 d = r - l - 2n + i 的画作的期望权值对 998244353 取模后的结果。
3 1 10000000
1 2 3
1 2 3
508205151 356969383 262200854 808707295 903475824 

推荐代码 查看4079 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战

赛题来源/所属竞赛 2023年中国大学生程序设计竞赛女生专场 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛