ICPC 南京站
Day -1
周五早上的飞机，落地后在酒店楼下吃了铁锅炖，豪赤！休息了一会儿我去南大找我的初中同学玩，有点远，地铁做了一个多小时，运气不好还下雨了。在校园里随便逛了逛以后就去吃饭了，吃烤鱼，聊天的过程中顺便了解一下他们的课程（由于专业相近，所以还白嫖了个计算机系统基础的课程链接），羡慕南大有这么好的课程体系安排！
Day 0
早上闹钟没听到，还是被队友叫醒的。吃了早饭直接去签到，参赛服好评，然后参与游戏获得一只迷你版袋鼠。骑电瓶车逛校园，十分惬意，刚好 30 min 还车，没有多付款。然后想着有点早，去食堂可以买点奶茶，但是发现餐券有效范围过小，于是就坐下歇着，开始摆弄袋鼠。
下午热身赛，竟然要存包（好像被说了，后来负责人和保安沟通了就不用了）。获得一只大袋鼠，开赛前又是各种袋鼠摆 pos 的传统，群里图片乱飞。热身赛果然都是袋鼠题，其中三道做过，于是很快地再次复现了出来。还有两道题我们分工，然后差不多都有思路，于是上机写。但所剩时间不多（由于一开始发现题目基本做过，于是去调 bash 了，所以没剩多少时间写题），最后这两题没过，打算晚上补一下。回去路上简单瞅了题解，发现思路都是对的，所以说是口胡 AK（。
Day 1
开局良心签到，飞速通过。之后是一个象棋的简化版，想了一下发现只需要判断一步即可得到结果。然后我第一反应是直接列出所有情况，疯狂敲 if 然后 WA，冷静了一下直接循环枚举所有情况，然后又 WA，瞪了好久才发现有一个 $dy$ 敲成了 $dx$。成罪人了 WA 了三发 1h 才过。
之后 Zlw 佬发现 F 是一个贪心加 bfs 的题，敲完一发通过。跟了一下榜发现 G,I 有一车人通过，但是想了想这两题发现我们三人都不会。佬提出我们应该多看一点题，于是开了 H，发现可做。
以下证明 SUNCHAOYI 是入机：
Zlw: 这道题我们可以先预处理出 $f_{l,r}$ 表示这段区间内有多少个满足中间条件限制的数量。但是怎么快速处理出来呢？
Scy: 先不管前缀，枚举两个重复子串的同一侧端点，然后就可以把 border 转化成哈希判断是否相等的问题，用二分加个 log 就行。
Zlw: 哦有道理，那么相当于前缀就是等差数列的贡献，随便维护一下就好了。
Scy: 对，可以用差分代替线段树。
Zlw: 那两侧的答案怎么统计呢？好像和刚刚的过程有点像。
Scy: 前缀和就行了。
Zlw: 哎，那好像这题做完了。
Zlw: 啊呀，差分咋写来着？
Scy: 两次前缀和，阿巴阿巴阿巴！
证明完毕。prompt 正确，直接胡出来了。
然后就过样例了，差点忘记取模，然后提交！测了一万年，一发通过！
然后剩下的两个小时疯狂的在 G,I 之间徘徊，但是最后都不会，4 题遗憾离场。
讲题，发现 G 题可以将两个参数分离，于是就可以简单贪心了，懊悔怎么没想到，但是转念一想过了也 Au 不了，又感觉还好（bushi。
滚榜，竟然意外的守住银了，在正是队伍中排 80 多名，就这样吧，SUA 题真的好难！
不知道还有没有机会打 EC，感觉离退役不远了，滚回学校学 CS 去了。
【赛后补题】
G 主要就是理解合并，即让较小容量和较大流速失效。将桶分别按照容量由小到大排序，记为 $A$，再按照流速由大到小排序，记为 $B$。那么也就是最后需要保留 $A$ 与 $B$ 的一段同样长度的后缀。当想要再失效一组容量和流速，发现水会漏完时，情况已经不优，因此对于一组询问直接二分答案即可。
I 是一个读题细节很多的 DP，读完题后需要意识到需要从后往前 dp。因此，设 $dp_{i,j,opa,opb}$ 四维表示前 $i$ 天剩 $j$ 元，$A,B$ 两人是否已经支付一次的最大价值。注意 $j < 0$ 的状态直接设为非法，又由于需要从后往前，dfs 记忆化即可，代码竟然异常好写。
M 组合加 NTT 优化题，还是相当的不熟练啊，借着 AI 的理解又推了一万年。考虑 $(P_i,P_{(i + d) \bmod n})$ 为凸 $k$ 多边形的一条边，则两线段右侧的 $d - 1$ 个点失效，剩余的 $n - 2 - (d - 1) = n - d - 1$ 个点需要选择 $k - 2$ 个组成 $k$ 凸多边形。
令 $F_d$ 表示选距离为 $d$ 的点作为一条边时的贡献，则有凸 $G_k$ 边形的面积和的两倍 $G_k$ 为
令 $A_d = (n - d - 1)! \times f(d)$，$B_d = \frac{1}{i!}$，则有
当然，还需要快速求出 $F_d$ 的值，用叉积表示面积的两倍，则有
以 $\sum \limits_{i = 0}^{n - 1} x_i y_{(i + d) \bmod n}$ 为例，先倍长数组，令 $X = [x_0,x_1,\cdots,x_{n - 1},0,0,\cdots,0]$，$Y = [y_0,y_1,\cdots,y_{n - 1},y_0,y_1,\cdots,y_{n - 1}]$。再令 $Y^{rev}$ 表示 $Y$ 的反转数组 $Y^{rev} = [y_{n - 1},\cdots,y_1,y_0,y_{n - 1},\cdots,y_1,y_0]$。则有
其中上限可以改变是因为倍长的时候 $x_{n} \sim x_{2n - 1}$ 均为 $0$，而最后 $H_k$ 也就是卷积后 $C_{2n - d - 1}$ 的值。
计算另一半 $H2_d$ 同理，最后 $F_d = H1_d - H2_d$。
做三次完整的 NTT 即可得到答案，时间复杂度为 $O(n \log n)$。
