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
33输入输出样例 #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;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
