LOJ NOI Round 简要总结

### Day 1 Day 1 简直有点乱来，早上起床时距离比赛开始只剩$5$分钟了，然后出题的题面还没做好…… 遂延迟半小时开始做……然后就非常自闭。 #### [T1 单枪匹马](https://loj.ac/problem/573) 拿到题一看——连分数？昨天刚说这个呢…… 觉得这个东西可能有性质，列几个柿子——找不到性质。开始自闭。 想了一会儿，没办法，只能写暴力了。写暴力的时候又没怎么把式子写在纸上，直接在代码里写了，于是没有发现式子的特点——**$f$可以看做以$a$为系数的非常系数齐次线性递推**！如果能注意到这点，应该能拿到更多分？ 当然，只有这些还远远不够。原式是从右端点往左推的，如果要在右端添加元素，要维护的可就多了，就相当于在头部添加元素，所有的前缀和都会变一样。 怎么办呢？写棵线段树，也能基本解决问题。 当然，正解是$\mathrm{O}(n)$的。 正解利用了连分数的一个性质：翻转后分子是不变的！这两篇文章都对这个性质有简要的介绍：[连分数的一个性质以及它的一个组合解释](http://www.matrix67.com/blog/archives/5556)、[连分数简介（3）：有限连分数性质的进一步讨论](http://blog.sina.com.cn/s/blog_a661ecd50101d3y1.html)。 可是我们该如何在考场上发现这个性质呢？ 看下面两个式子。$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$的递推。