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)\)。