P10792 『SpOI - R1』笑起来最帅的小孩题目描述本题包含多组数据。有一个数字序列a aa长度为n nn。序列中每一项均为0 00到9 99的数字。另有一个空数字序列b bbb 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_XEX∈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输入 #11 2 4 1 2 1输出 #133输入输出样例 #2输入 #21 3 1 2 3 1 7 2输出 #21204285426说明/提示数据范围本题开启子任务捆绑和子任务依赖。令n ∑ i 1 k l i n\sum\limits_{i1}^k l_ini1∑kli。对于100 % 100\%100%的数据保证1 ≤ T ≤ 15 1\leq T\leq 151≤T≤151 ≤ n ≤ 2 × 10 9 1\leq n\leq 2\times 10^91≤n≤2×1091 ≤ k ≤ 10 5 1\leq k\leq 10^51≤k≤105且对于任意i ii均有0 ≤ a i ≤ 9 0\leq a_i\leq 90≤ai≤91 ≤ l i ≤ 2 × 10 9 1\leq l_i\leq 2\times 10^91≤li≤2×109。SubtaskT ≤ T\leqT≤n ≤ n\leqn≤特殊性质得分子任务依赖115 15152 × 10 9 2\times 10^92×109A AA10 1010无215 1515100 100100无15 1515无35 552000 20002000无15 1515245 5510 6 10^6106无15 15152,355 552 × 10 9 2\times 10^92×109无45 45451,2,3,4特殊性质A AA保证在解压缩后的a aa中任意一个数字都出现了最多一次。C实现#includeiostreamusingnamespacestd;typedeflonglongll;constll mod2007072007;constintK1e57;intk;structnode{ll x,l;}a[K];llksm(ll x,ll y){ll ans1;x%mod;while(y){if(y1)ansans*x%mod;xx*x%mod;y1;}returnans;}intmain(){intT;cinT;while(T--){cink;ll part10,part2,part3;ll n0;for(inti1;ik;i){cina[i].xa[i].l;na[i].l;part1(part1a[i].x*a[i].l%mod)%mod;}part2((ksm(10,n)-1)%modmod)%mod*ksm(9,mod-2)%mod;part3ksm(n,mod-2);cout((part1*part2)%mod*part3)%modendl;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容