luogu#P10792. 『SpOI - R1』笑起来最帅的小孩
『SpOI - R1』笑起来最帅的小孩
题目描述
本题包含多组数据。
有一个数字序列 ,长度为 。序列中每一项均为 到 的数字。
另有一个空数字序列 , 中会出现一个光标(你可以理解为能够出现在数字之间,或整个数字序列之前,或整个数字序列之后的细线),此时光标前后均没有数字。
现在向 中依次输入数字序列 。每输入一个数字,数字立即出现在光标之后。
接下来光标立即随机地移动到任意一个数字之前或所有数字之后。随机是均匀的。换句话说,光标移动到所有可移动到的位置的概率是均等的。
现在告诉你数字序列 。你需要输出的是,最终得到的 直接转为十进制后的大小(无视前导零)的期望,对质数 取模。
由于 可能很长,所以本题采用压缩输入。
具体来说,最开始 是空的数字序列,输入会给你一个 长的二元组数组,其中第 项为 ,表示数字 连续出现 次接在之前的 之后。你可以用此方法解压缩真正的 ,再解决问题。
在本题,你可以对期望的理解:对于一个变量可能的结果 ,若其权值为 ,得到该结果的概率为 ,则对于结果集 ,变量的期望 。
如果你不知道如何对有理数取模:请查看此题。
输入格式
第一行一个整数 ,表示数据组数。
对于每组数据:
一行一个整数 ,表示 压缩后得到的二元组数组包含多少项。
接下来共 行,每行两个整数 ,表示在上一项所得 序列的基础上,在末尾增加 个数字 得到新的 序列。你可以用这种方式解压缩真正的 序列。
输出格式
对于每组数据,输出一行一个整数,表示在光标每次都随机移动的情况下,可能得到的 转化为十进制后的大小(无视前导零)的期望,对质数 取模的值。
1
2
4 1
2 1
33
1
3
1 2
3 1
7 2
1204285426
提示
数据范围
本题开启子任务捆绑和子任务依赖。
令 。
对于 的数据,保证 ,,,且对于任意 均有 ,。
Subtask | 特殊性质 | 得分 | 子任务依赖 | ||
---|---|---|---|---|---|
1 | 无 | ||||
2 | 无 | ||||
3 | 2 | ||||
4 | 2,3 | ||||
5 | 1,2,3,4 |
特殊性质 :保证在解压缩后的 中,任意一个数字都出现了最多一次。