牛客网周赛120

牛客周赛Round120题解

A 无穷无尽的力量

略

B 无穷无尽的字符串

略

C 无穷无尽的力量2.0

稍加思考，发现 3*3 的棋盘可以跳到除中间外的任意点（止步于此）而 3*4 以上的棋盘就能跳到任意点

对于 1*n 的棋盘，显然只能在初始格

对于 2*n 的棋盘，显然可以从第 1 列开始依次跳到第 3 列，第 5 列，一直到第 n 列 / 第 n-1 列，即可跳（n+1)/2 格

代码略

D 无穷无尽的小数

从简到难，先考虑两个小数循环节长度相同，大减小的情况

稍加思考发现结果的循环节事实上就是 大数循环节 - 小数循环节 的结果，而循环节长度最长为 100，超出了long long 的范围，因此采用高精度减法解决

接着考虑长度不同怎么搞？

由于循环节重复若干次组成的依然是循环节，因此直接取两个循环节的最小公倍数，将两个数扩大到相同长度即可，这样最大长度也才 10^4 ，数组完全装得下，高精减没问题

最后如果是小减大呢？

在计算器中试了一下，如果是 0.a-0.b(a<b) 的情况下，会得到 -0.(b-a) 的结果

这里拿 0.2222222 - 0.333333 为示例

得到 -0.1111111 ，循环节的 1 可以看成是 3 - 2 得到的

而本题不考虑负数，因此加一个1，对循环节来说，原本的循环节 x 变成了 9-x

事实上原本的 a - b 看成 1 + a - b 而小数位为了凑 1 需要每一位都凑一个 9

比如 - 0 . 1234 ，加一个1就相当于用 0.99999 去减这个数，也就成了 0.8765

本题错误点：循环节0与循环节9不相等（出题人估计没考虑到

代码略

E 无穷无尽的树

树形dp模板题，叶子节点没有贡献在dfs时直接判断入度为一的非根节点直接跳过即可

主要考虑一下怎么转移状态

我们定义两个数组 smd (son's max depth) 和 smn (son's max deep number) (蹩脚英文这一块，梦到什么取啥名) 用于记录每个节点子树删除叶子节点后最大深度与最大深度的节点数目

考虑每个点的初始化，一个孤独的非叶子节点最大深度显然是该点深度，节点数自然是 1

由于每个点的答案来自于子树，我们采取dfs递归，搜索完节点 u 的子树后再来更新 u 点的答案

对于一个节点 u 与它的子节点 v ，考虑三种情况

smd[v] > smd[u] : 说明 u 之前的子树最大深度不够大，更新最大深度与数目

smd[u] = smd[v] ;

smn[u] = smn[v] ;
smd[v]==smd[u] : 累计节点数即可

smn[u] += smn[v] ;
smd[v] < smd[u] : 显然 v 的子树对 u 的答案无贡献，忽略即可

本体错误点：无向图链表开双倍空间。。。（what can I say

F 无穷无尽的数

快速幂与前缀和

算是一道典型的数论题，难度不算高，恶心程度视考试剩余时间与红温程度改变（数论题都这样的说

考虑一般情况，l 和 r 之间可以分为三部分：（事实上拆分成两头的碎块和中间的完整部分）

l 到第一次结束循环节的位置（记为 lnxt
最后一个循环节（r 所在的循环节）的开头（记为 rlst）到 r
lnxt +1 到 rlst-1 （即中间所有的完整循环节

先考虑碎块怎么处理

由于碎块长度不超过 10^5 ，直接前缀与后缀的方式以 o(n) 效率秒了，代码如下

     lld tm=1;//存10的次幂
     for(int i=1;i<=n;i++){
         int fnow=s[(i-1)%n]-'0';
         fm[i]=(fm[i-1] *10 %Mod +fnow) %Mod;//fm[i]表示 前i位组成的数%Mod 的结果
         int bnow=s[(n-i)%n]-'0';
         bm[i]=(bm[i-1] +bnow *tm %Mod) %Mod;//bm[i]表示 后i位组成的数%Mod 的结果
         tm=(tm*10) %Mod;
     }

接着考虑中间的完整块怎么搞

假设中间完整块总共有 num 个，每块长为 n，一块完整循环节 %Mod 的结果是 x ，于是我们把这 num 块拆开来看就成了：

x+x10^n+x10^{2n}+...+x10^{(num-1)n}

显然是个等比数列，采用等比数列求和化简为：

x*(\frac{{10^n}^{num}-1}{10^n -1})

考虑怎么求模998244353意义下的这一堆

x 可以在之前求前缀的时候顺手求了，10^n 乃至 {10^n}^{num} 显然采用快速幂的方法肥肠搞笑，而这里的除法也能用逆元的思想直接改为求 {10^n}^{Mod-2} 再乘起来就行（毕竟10^n-1 肯定和998244353互质

代码实现如下：

     lld Pow(lld a,lld b){
         lld ans=1;
         while(b){
             if(b&1) ans=ans*a%Mod;
             a=a*a%Mod;
             b>>=1;
         }
         return ans%Mod;
     }
     
     //下面是main函数中的一部分
     lld num=((rlst-1)-(lnxt+1)+1)/n;//块数
     lld q=Pow(10,n);//公比
     lld p=(Pow(q,num)-1)%Mod * Pow(q-1,Mod-2) %Mod; //等比数列化简后括号里那一坨
     ans=fm[n] *p %Mod;//fm[n] 就是一个完整循环节%Mod的结果