当前位置：首页 > news >正文

打卡信奥刷题（3495）用C++实现信奥题 P10792 『SpOI - R1』笑起来最帅的小孩

news 2026/8/8 8:33:16

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

题目描述

本题包含多组数据。

有一个数字序列a aa，长度为n nn。序列中每一项均为0 00到9 99的数字。

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

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

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

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

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

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

在本题，你可以对期望的理解：对于一个变量可能的结果X XX，若其权值为v X v_XvX，得到该结果的概率为p X p_XpX，则对于结果集S SS，变量的期望E = ∑ X ∈ S p X v X E=\sum\limits_{X\in S}p_Xv_XE=X∈S∑pXvX。

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

输入格式

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

对于每组数据：

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

接下来共k kk行，每行两个整数x i , l i x_i,l_ixi,li，表示在上一项所得a aa序列的基础上，在末尾增加l i l_ili个数字x i x_ixi得到新的a aa序列。你可以用这种方式解压缩真正的a aa序列。

输出格式

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

输入输出样例 #1

输入 #1

1 2 4 1 2 1

输出 #1

输入输出样例 #2

输入 #2

1 3 1 2 3 1 7 2

输出 #2

1204285426

说明/提示

数据范围

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

令n = ∑ i = 1 k l i n=\sum\limits_{i=1}^k l_in=i=1∑kli。

对于100 % 100\%100%的数据，保证1 ≤ T ≤ 15 1\leq T\leq 151≤T≤15，1 ≤ n ≤ 2 × 10 9 1\leq n\leq 2\times 10^91≤n≤2×109，1 ≤ k ≤ 10 5 1\leq k\leq 10^51≤k≤105，且对于任意i ii均有0 ≤ a i ≤ 9 0\leq a_i\leq 90≤ai≤9，1 ≤ l i ≤ 2 × 10 9 1\leq l_i\leq 2\times 10^91≤li≤2×109。

Subtask	T ≤ T\leqT≤	n ≤ n\leqn≤	特殊性质	得分	子任务依赖
1	15 1515	2 × 10 9 2\times 10^92×109	A AA	10 1010	无
2	15 1515	100 100100	无	15 1515	无
3	5 55	2000 20002000	无	15 1515	2
4	5 55	10 6 10^6106	无	15 1515	2,3
5	5 55	2 × 10 9 2\times 10^92×109	无	45 4545	1,2,3,4

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

C++实现

#include<iostream>usingnamespacestd;typedeflonglongll;constll mod=2007072007;constintK=1e5+7;intk;structnode{ll x,l;}a[K];llksm(ll x,ll y){ll ans=1;x%=mod;while(y){if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;}returnans;}intmain(){intT;cin>>T;while(T--){cin>>k;ll part1=0,part2,part3;ll n=0;for(inti=1;i<=k;i++){cin>>a[i].x>>a[i].l;n+=a[i].l;part1=(part1+a[i].x*a[i].l%mod)%mod;}part2=((ksm(10,n)-1)%mod+mod)%mod*ksm(9,mod-2)%mod;part3=ksm(n,mod-2);cout<<((part1*part2)%mod*part3)%mod<<endl;}return0;}