2022.8.9 模拟赛

T0

  小清新签到题，直接暴力 $bfs$ 就过掉了，但是中间要记录每个字母有没有被走过，走过就不走了。不然如果整张图全都是同一个字母的话时间复杂度就炸掉了 就在这里挂掉 9 分。

T1 杰哥的数论

  让你很快的判断分数 $\frac{p}{q}$ 在 $b$ 进制下是否为无限循环小数。

  根据一些常识，我们知道 $\frac{p}{q}$ 是否循环跟 $p$ 没啥关系，所以我们先给她们约分一下然后只关注 $q$（这里要特判 $p=0$）。

  然后我们发现给一个数 $\frac{1}{q}$ 乘上一个 $b$ 就相当于在 $b$ 进制下把小数点右移一位。所以如果这个小数是有限的的，那么就存在一个 $k\in N^{\ast }$ 使得 $q\mid b^k$。

  于是我们就考虑一直给 $q$ 除上 $\gcd (q,b)$，直到这俩玩意儿互质。此时如果 $q=1$ 那么就说明 $q$ 的质因子 $b$ 都有。那么也就是说存在 $k$ 使得 $q\mid b^k$，时间复杂度是 $O(T{\log }^{2}q)$ 的。

T2 杰哥刷墙

20pts

  有 $20pts$ 是矩形的情况，据机房大佬 $cmy$ 说这一部分的规律比较好找，答案就是：

$$ans=2^n+2^h-2$$

  就直接 $O(\log n)$ 快速幂就做完了。

T3 杰哥的数据结构

10pts

  直接按照题面模拟，复杂度 $O(m{n}^2)$。

40 pts

  维护一个线段树支持单点修改，区间查询，我们发现一个性质，对于一个左端点 $i$ 来说，她向右扩展之后的 $or$ 值是非严格单调递增的，所以我们可以考虑二分得到一个点 $pos$，这个点是第一个大于等于 $x$ 的右端点，那么这个点 $i$ 的贡献就是 $v-pos+1$。

  二分每次 $check(mid)$ 都要线段树区间查，所以复杂度是 $O(mn\log n)$ 的。

50 pts

  因为 $x=0$，所以答案就是：

$$ans=\frac{1}{2}(r-l+1)(r-l+2)$$

70pts