Sweetlemon 的博客

Sweetlemon 的博客

LOJ NOI Round 简要总结

posted on 2019-07-07 22:23:15 | under 总结 |

Day 1

Day 1 简直有点乱来,早上起床时距离比赛开始只剩 $5$ 分钟了,然后出题的题面还没做好……

遂延迟半小时开始做……然后就非常自闭。

T1 单枪匹马

拿到题一看——连分数?昨天刚说这个呢……

觉得这个东西可能有性质,列几个柿子——找不到性质。开始自闭。

想了一会儿,没办法,只能写暴力了。写暴力的时候又没怎么把式子写在纸上,直接在代码里写了,于是没有发现式子的特点—— $f$ 可以看做以 $a$ 为系数的非常系数齐次线性递推!如果能注意到这点,应该能拿到更多分?

当然,只有这些还远远不够。原式是从右端点往左推的,如果要在右端添加元素,要维护的可就多了,就相当于在头部添加元素,所有的前缀和都会变一样。

怎么办呢?写棵线段树,也能基本解决问题。

当然,正解是 $\mathrm{O}(n)$ 的。

正解利用了连分数的一个性质:翻转后分子是不变的!这两篇文章都对这个性质有简要的介绍:连分数的一个性质以及它的一个组合解释连分数简介(3):有限连分数性质的进一步讨论

可是我们该如何在考场上发现这个性质呢?

看下面两个式子。 $p_{l\cdots r}$ 和 $q_{l\cdots r}$ 分别代表 $[l,r]$ 区间的连分数的分子和分母。

$$p_{l\cdots r}=a_lp_{l+1\cdots r}+q_{l+1 \cdots r}$$

$$q_{l\cdots r}=p_{l+1\cdots r}$$

双递推不好处理,暂时消去 $q$ 。

$$p_{l\cdots r}=a_lp_{l+1\cdots r}+p_{l+2 \cdots r}$$

再将 $q$ 回代。

$$q_{l-1\cdots r}=a_lq_{l\cdots r}+q_{l+1 \cdots r}$$

$$q_{l\cdots r}=a_{l+1}q_{l+1\cdots r}+q_{l+2 \cdots r}$$

$p$ 和 $q$ 的性质还算不错,都是齐次线性“常”系数(一元二阶)递推;不过都是固定 $r$ 的递推。