Problem 1D. 随机坏道

Problem 1D. 随机坏道

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem D. 随机坏道

Limits

时间限制:1000ms

内存限制:256MB

Background

南京师范大学为了存储120周年校庆的录像,委托设备自动化部门的小F购买了一个特制磁盘。很不幸的是,粗心的小F买到了一个次品磁盘,现在他遇到了一点麻烦……

Description

小F的磁盘上有\(n\)个扇区,每个扇区末尾都会有\(L,R\)两个指针。每个指针可以指向一个扇区或者留空。这些扇区恰好形成了一颗二叉树。现在有一个读取程序,它将从\(1\)号扇区开始读取,读到扇区末时会 等概率地 任选一个指针进行跳转。如果选择了空指针,那么不会发生跳转,读取程序退出。

有一天,小F发现有一个扇区损坏了。具体而言,\(k\)号扇区的\(L\)指针指向了\(m\)号扇区。现在小F想知道,扇区损坏后,读取程序退出前发生跳转次数的数学期望。答案对\(998244353\)取模。

Input

第1行,\(1\)个数\(n\),表示扇区个数;

第2行,\(n\)个数,依次表示各扇区的尾部的\(L\)指针指向的扇区编号,\(L_1,L_2,…,L_n\);

第3行,\(n\)个数,依次表示各扇区的尾部的\(R\)指针指向的扇区编号,\(R_1,R_2,…,R_n\),

第4行,\(2\)个数,分别表示\(k,m\);

注意:扇区编号从\(1\)开始,\(0\)表示空指针;

Output

一个数,表示所求数学期望对\(998244353\)取模的值;

Samples

Sample Input

6
2 4 0 0 0 0
3 5 6 0 0 0
2 3

Sample Output

124780546

提示:即\(\frac{15}{8}\)。

Sample Input 1

6
2 4 0 0 0 0
3 5 6 0 0 0
4 2

Sample Output 2

582309208

提示:即\(\frac{25}{12}\)。

Data range

测试点 \(n\) 特殊性质
1,2 \(\le 500\) 扇区损坏后一定可以停止读取
3,4 \(\le 500\)
5,6 \(\le 5\times10^5\) 扇区损坏后一定可以停止读取
7,8,9,10 \(\le 5\times10^5\)

对于100%数据,\(1\le k\le n\le 5\times10^5\),\(0\le L_i,R_i,m\le n\)。

Hints

有理数\(\frac{a}{b}\)对质数\(P\)取模的结果是整数\(c\),\(c\)满足\(0\le c<P\)且\(c \cdot b\equiv a(mod\ P)\)。

悬赏令第一周

未参加
状态
已结束
规则
OI
题目
4
开始于
2022-09-25 18:00
结束于
2022-10-02 00:00
持续时间
150.0 小时
主持人
参赛人数
127