今年咋是联考啊。
没有停课的日子
除了最后一周，都只占用下午下课后与晚上的时间。我寻思倒不如多整点停课，划走晚上算什么嘛。
稳定每天一套模拟赛，每天被吊打。
学会了多项式的卡常技巧。
终于停课了
才发现 0202 年了你校还有一个机房是 32 位 win。
咋只剩一周了。
根据惯例（¿）最后一周不会天天有模拟赛。
信心场也打得和屎一样。没救了啊。
想复习点分、串串、网络流、数论、计算几何。算了先写个 LCT 吧。
各种模板题写挂，为啥码力退步巨大多，我人傻了。
随便学了学 k-D Tree，SAM。
考前补知识点简直是女娲补天。
奶一口都不会考算了。
最后一天
你校留生工作傻逼，初三自招壬填报志愿把我们赶来赶去。
最后到了「数学研究室」，其实就是颓废室啦。大量无系统的机，几台设了密码的机。有个老哥密码提示「好啊！来啊！」，输入114514进去了。
于是试图在某无系统电脑装个 UBuntu 18.04，然而失败。
就这样白费了一早上。
下午机房的人都开始颓。我也想颓，然而还在复习（预习）知识点，算了。
晚上受不了了开始看神仙扫雷。
走之前打印了准考证，和几个板子。试图在宿舍看看，然而还是睡觉好。
商店里冰火人在问问题
开场 1min 输奇怪的密码，10min 把题看了一遍。怎么这么 CSP2019 day 1。
icefire 看起来就是区间加减和维护一个非严格单峰函数的右峰。
$Q\le 2\times 10^6$，-lm。怎么省选还考卡常的，差评。
二分？好像我会 $O(Q\log^2 Q)$。然而只有 60 分。
三个.cpp开好了，测一些输入输出，发现文操错了：
1 | freopen(".in", "r", stdin); |
怎么俩stdin，赶紧改。
于是开始看 problem。草怎么模数不是质数，昨天谁奶的来着。
$$\sum\limits_{i = 0}^{n} x^i \binom{n}{i} = (x + 1)^n$$
开始推。
$$\begin{aligned}S_m
&=\sum\limits_{i = 0}^{n} i^{\underline{m}} k^i \binom{n}{i}\\
&=\sum\limits_{i = m}^{n}\dfrac{n!}{(i - m)!(n - i)!}\cdot k^i\\
&=n^{\underline{m}} k^m\sum\limits_{i = 0}^{n - m} \binom{n - m}{i} k^i\\
&=n^{\underline{m}} k^m (k + 1)^{n - m}
\end{aligned}$$
想了想 $n^{\underline{m}}$ 按 $m$ 从小到大计算可以 $O(m^2)$ 求出所有要用的。好啊，只要把 $f$ 转下降幂多项式就可以 $O(m^2)$ 了。
如何转下降幂？
设 $f(x) = \sum\limits_{i = 0}^{m} b_i x^{\underline{i}}$。
假如我知道了 $b_i$($i < x$)，那可以求出 $x!b_x$，不妨设 $c_x = x!b_x$。发现 $x^{\underline{i}}b_i = \dfrac{x^{\underline{i}}}{i!}c_i$。
假如我可以 $O(m^2)$ 处理 $\dfrac{x^{\underline{i}}}{i!}$($x, i\le m$)和 $\dfrac{n^{\underline{i}}}{i!}$($i\le m$)岂不做完了？
后面那个我会！直接搞 $m$ 个数，每次要除一个数的时候就遍历这 $m$ 个数除可以除的，直到把这个数除到 $1$，$O(m^2)$。
前面那个，乘的数和除的数都 $O(m)$ 有啥用？只能 $O(m^3)$？没这部分分啊！
自闭了，我也不知道浪费了多久。
随手写下一个式子：$\dfrac{(x + 1)^{\underline{i}}}{i!} - \dfrac{x^{\underline{i}}}{i!} = \dfrac{x^{\underline{i - 1}}}{(i - 1)!}$
哦 $\dfrac{x^{\underline{i}}}{i!} = \dbinom{x}{i}$ 啊，那没事了。
于是又写了 10min 走人，写完都十一点半了。
自闭的途中试图写 shop 的最低档暴力，未果。想了想 icefire，还是只会俩 $\log$，人没了。
没办法只能写。
瞎搞过了第一个样例，第二个死活过不去。十二点三十了，我觉得我在冒汗，头脑也已经将近停止转动了。
全机房好像只剩我的键盘在响。
看了看自己的写法，发现二分的时候没有取到温度最大的。
又补了一个二分。补的时候监考员已经表示只剩十分钟了。
距离考试结束只剩几分钟，过了第二个样例。
认真看了看感觉没错，最后三分钟啥都没干，考试结束了。
大概 60 + 100 + 0 罢。
出考场一想，icefire 那个东西好像完全可以直接树状数组上二分，省掉一个 $\log$。
也会了 shop 的 10 分暴力。
还是考场降智啊。
顺便用自己傻瓜的 problem 的心路历程逗笑了整个机房。
明明我昨晚刚看过斯特林数，结果 problem 推导完全没用上。
某神仙拿草稿纸在场上写游记结果草稿纸回收了，草。
吃中午饭大家疯狂奶明天考啥。毕竟今天没串串没计数没树。
下午在「数学研究室」划水划了一下午，发现テトリス(Tetris)底力下降巨大多。
晚上在 32 位机房又划水划了一晚上。
作业是在树上传递信号
反正 CSP 成绩和昨天 icefire 笑话已经决定我进不了 E 的事实，今天决定随便考。
transfer 看起来是个 $O(m2^m)$ 之类的，然而我想了 20min 只会阶乘做法。
count 看起来暴力分好足。
第一个包 10min，第二个包 3min。
矩阵树定理是啥来着……行列式怎么算来着……
于是成功在第三个包浪费巨久。
等等第四个包怎么搞啊，怎么求必须选某条边的树的个数啊！！！
于是只拿了前三个包跑路了。
tree 一看就是个工业题，大概要维护一个数据结构支持：
- 插入一个数
- 一个结构内全加 1
- 求一个结构内的异或和
- 合并两个结构
这不是 ynoi trick 吗，反正就 Trie 合并完事。
于是敲了 80min 左右搞出来了。
数组卡紧开，反正值域到就完事了。(flag)
还有大量时间搞 transfer。
先把第一个包拿了。
剩下 40min，找个暴力拍拍拍。
$5\times 10^4$ 两份代码都跑得飞快，$5\times 10^5$ 两份代码都跑不出来。
怎么回事啊！
$1\times 10^5$ 也能跑。$2\times 10^5$ 也能跑。
自闭了，直到考试结束都不知道发生了啥。
一出来发现 transfer 可以把边的贡献拆在点上，然后随便 $O(m^2 2^m)$。
发现 tree 只开了 $2^{19}$，凉了。
发现 count 第四个包只要算全图生成树个数和去掉某条边之后生成树个数，一减就是包含某条边的生成树个数。
又降智了。预估 30 + 80 + 50。
两天串串没考，计数没考，奇怪的数据结构没考，计算几何没考。我怀疑我来的是 CSP 2019 Round 2。
一上你谷看到 lxl 发的听说省选考了Ynoi题一样的trick，想到考场上自己好像第一反应也是这个。
滚回文化课
考完两天出分了。
| 类型 | icefire | problem | shop | transfer | tree | count |
|---|---|---|---|---|---|---|
| 实际得分 | 60 | 100 | 0 | 30 | 35 | 50 |
| 考场上会，但是写挂了 | 0 | 0 | 0 | 0 | 65 | 0 |
| 出了考场不久会了 | 40 | 0 | 10 | 30~40 | 0 | 20 |
| 再肝多久也搞不出来 | 0 | 0 | 90 | 10 | 0 | 0~30 |
考场上降智（即表中第三行）是主要丢分点。
至于写挂的 65 分……
tree 暴毙是因为它看起来开了 $2^{19}$ 实际上只开了 $2^{18}$。（实际上是被某人奶死的（确信））
算是买了个「值域要仔细看」的教训吧。
并且考场造数据的时候，值域可以尽量开到上限（比如在 $[\dfrac{1}{2}W_{max}, W_{max}]$ 之间随机而不要在 $[1, W_{max}]$ 随，或者直接测几个全开 $W_{max}$ 的数据）。如果这么干了，考场上是不是也能救回来那 65 呢。
发现考场我不愿意去洗手间，其实 4.5h 的比赛去一去转换一下思路也许确实能一定程度上避免降智吧。
感觉睡好确实挺重要的，精神状态比 CSP 好太多了。
距离中考只剩一个月。
暂别。