NOI.AC NOIP2018 全国热身赛 第四场

心路历程

预计得分：(0 + 100 +100)

实际得分：(10 + 100 + 0)

神TM T3模数为啥是(1e9 + 9)啊啊啊啊，而且我也确实是眼瞎。。。真是血的教训啊。。

T2 T3为啥这么简单啊。。。T1为啥是原题啊。。。打死我也不信这是IOIrank2出的题 肯定是没给够钱

T1 一点思路都没有，因为上来大方向就错了。

T2 很有意思，也不算很难。但是写起来有点繁琐，而且数据特别水，完全随机。。

T3 和zzx讨论了很久(因为当时已经快弃疗了)，最后xjb猜了个结论直接把(A, B)带到二项式定理里，没想到居然猜对了！(3min)写完就拍上了 感觉稳的一批。然而！！我TM居然把模数看错了！！！直接从(100->0)

Sol

A.tree

https://cloud.tencent.com/developer/article/1367910

B.sort

首先(nlogn)求出排名为(L)和(R)的数是什么(二分+利用单调性扫描)，然后再用同样的方法算出(L)到(R)之内的数。

边界问题可能比较难处理，我是先求出一定会在出现的数，然后再判边界情况

虽然看上去比较玄学但是复杂度是(O(nlogn))的

C.triangle

上面说了，直接把((A, B))带到二项式定理中，后来想了想也挺显然的。