luogu#P10792. 『SpOI - R1』笑起来最帅的小孩

『SpOI - R1』笑起来最帅的小孩

题目描述

本题包含多组数据。

有一个数字序列 aa,长度为 nn。序列中每一项均为 0099 的数字。

另有一个空数字序列 bbbb 中会出现一个光标(你可以理解为能够出现在数字之间,或整个数字序列之前,或整个数字序列之后的细线),此时光标前后均没有数字。

现在向 bb 中依次输入数字序列 aa。每输入一个数字,数字立即出现在光标之后。

接下来光标立即随机地移动到任意一个数字之前或所有数字之后。随机是均匀的。换句话说,光标移动到所有可移动到的位置的概率是均等的。

现在告诉你数字序列 aa。你需要输出的是,最终得到的 bb 直接转为十进制后的大小(无视前导零)的期望,对质数 20070720072007072007 取模。

由于 aa 可能很长,所以本题采用压缩输入。

具体来说,最开始 aa 是空的数字序列,输入会给你一个 kk 长的二元组数组,其中第 ii 项为 (xi,li)(x_i,l_i),表示数字 xix_i 连续出现 lil_i 次接在之前的 aa 之后。你可以用此方法解压缩真正的 aa,再解决问题。


在本题,你可以对期望的理解:对于一个变量可能的结果 XX,若其权值为 vXv_X,得到该结果的概率为 pXp_X,则对于结果集 SS,变量的期望 E=XSpXvXE=\sum\limits_{X\in S}p_Xv_X

如果你不知道如何对有理数取模:请查看此题

输入格式

第一行一个整数 TT,表示数据组数。

对于每组数据:

一行一个整数 kk,表示 aa 压缩后得到的二元组数组包含多少项。

接下来共 kk 行,每行两个整数 xi,lix_i,l_i,表示在上一项所得 aa 序列的基础上,在末尾增加 lil_i 个数字 xix_i 得到新的 aa 序列。你可以用这种方式解压缩真正的 aa 序列。

输出格式

对于每组数据,输出一行一个整数,表示在光标每次都随机移动的情况下,可能得到的 bb 转化为十进制后的大小(无视前导零)的期望,对质数 20070720072007072007 取模的值。

1
2
4 1
2 1
33
1
3
1 2
3 1
7 2
1204285426

提示

数据范围

本题开启子任务捆绑和子任务依赖。

n=i=1klin=\sum\limits_{i=1}^k l_i

对于 100%100\% 的数据,保证 1T151\leq T\leq 151n2×1091\leq n\leq 2\times 10^91k1051\leq k\leq 10^5,且对于任意 ii 均有 0ai90\leq a_i\leq 91li2×1091\leq l_i\leq 2\times 10^9

Subtask TT\leq nn\leq 特殊性质 得分 子任务依赖
1 1515 2×1092\times 10^9 AA 1010
2 100100 1515
3 55 20002000 2
4 10610^6 2,3
5 2×1092\times 10^9 4545 1,2,3,4

特殊性质 AA:保证在解压缩后的 aa 中,任意一个数字都出现了最多一次。