2022.3.4模拟赛

困难。

A.「2017 山东二轮集训 Day1」第二题

贪心，贪心，贪心！

我们对于序列建出笛卡尔树，考虑在笛卡尔树上贪心。

对于一个点，他的两个儿子是凸出来的两块，我们考虑先把他们搭完，把剩下的留在底下继续搭。

复杂度是优美的 $O(n)$

B.「2017 山东二轮集训 Day1」第一题

才知道主席树也能区间加

考虑处理出每个点 ${\rm i}$ 能扩展到的最远点 ${\rm nxt(i)}$ , 知道这个之后我们在主席树上进行若干次区间加法，最后询问左端点在 $[{\rm l, r}]$ 之间的区间和即可。

需要用到标记永久化的处理技巧。

对于 ${\rm nxt(i)}$ 的处理还是要用到二分。

考虑如何判断区间 $[{\rm l, r}]$ 是否合法。
我们维护一个前缀和， $s(0/1,i,j)$ 表示 前 ${\rm i}$ 个数，第 ${\rm j}$ 位为最高位 $0 \rightarrow 1$
的次数， 同理维护一个 $1 \rightarrow 0$ 的次数，二分判断这一段区间这个是否为 ${\rm 0}$ 即可。

预处理复杂度是两只 $\log$ , 查询是一只 $\log$

C. GCD

第三次学.jpg

求 $\gcd(af_n+bf_{n+1},cf_n+df_{n+1})$ ，其中 $f_n=9f_{n-1}+12f_{n-2}$

通过打表可以发现 $gcd(f_n,f_{n-1})=3^{\frac{n}{2}}$

首先我们通过辗转相减，可以把 $df_{n+1}$ 这一项消去，只需要考虑 $\gcd(af_n+bf_{n+1},cf_n)$ 其中 $\text{a, b, c}$ 每次都有所变化。

考虑没有 $c$ 这个东西会怎么样呢？

$\gcd(af_n+bf_{n+1},f_n)$ = $\gcd(bf_{n+1},f_n)$

通过我们打的表可以看出他就是

$3^{\frac{n}{2}}\gcd(b,f_n)$ 啦

只需要在 $\text{mod b}$ 意义下做矩阵快速幂就好了。

在有 $c$ 的情况下，我们考虑有 $g=\gcd(af_n+bf_{n+1},f_n)$

我们就可以把原式做一些等价变化。

$\gcd(af_n+bf_{n+1},cf_n) \\ =g * \gcd(\frac{af_n+bf_{n+1}}{g},c\frac{f_n}{g})\\=g*\gcd(\frac{af_n+bf_{n+1}}{g},c)\\=g*\gcd(\frac{af_n+bf_{n+1}(\text{mod gc})}{g},c)$

看起来就可以了。

最后要求的是 $\frac{f_n}{3^{\frac{n}{2}}}$

我们可以让转移矩阵 $\text A$ 平方后 除 $\text{3}$
做 $^\frac{n}{2}$ 次运算即可。

即 $\frac{x}{3^{\frac{n}{2}}}=(\frac{x^2}{3})^{\frac{n}{2}}$