【游记】2026 UESTC 暑假集训（div.1）
本文最后更新于 2026年8月20日 晚上
属于 UESTC-无尽相拥 的最后一个赛季。
也许输赢没有那么重要了，无论结果如何，大家都有各自的归宿。
但拿到金牌依然是一件很酷的事情，不是吗？
7.22
跟 leader 请了六周的假，就飞回来了。
为什么是六周？因为实习答辩在八月底，这个点回成都也不至于错过大部分多校。
这个点队友应该已经训了一周了，不过再早的话我手头也有事情没结。
下午两点多落地，空客 A350，但乘坐体验一般，而且落地后还在双流机场排了 40min 的队才对接到廊桥，半步闷死了。然后又坐了一小时地铁，出地铁站的时候真的感觉要融化了，38℃ 是人类能存活的温度吗。
才离开学校六个月，进校门的时候就有一种莫名的亲切感。
可能是因为在公司远比在学校要累的多吧。
宿舍楼下的蜜雪冰城换成了书亦烧仙草，虽然贵了点但喝着还行，主要和北京比起来还是便宜了。
太疲惫了，晚饭没吃，直接倒头就睡了。
7.23 (杭电多校 2)
写在前面：我收回我上一段说的话，双校区往返 2h+ 通勤，比上班累多了。
怎会如此？？？
沙河输的最彻底的一次。
这场很可惜，最后一个小时没把 B 开出来，是一个很 trivial 的东西，但我设的 \(G(x)\) 比较奇怪导致递推卡住了。
A 和 G 的做法也比题解要复杂。A 我注意力涣散，直接大力拆了 \(n+5m\) 个点出来，加了个剪枝卡过去了；G 也是个 trivial 的题，先 gcd 容斥再莫比乌斯反演是自然的，但我推了一长串出来，好在过程全错结果全对。
E 的话补题的时候觉得挺难，但现在回想了一下好像也没那么困难。当时觉得这个容斥不是很自然，可能当时已经昏头了。
C 没咋看明白，lzh 赛后写了个递归给秒了。
I 这个题我看题解没觉得很难啊，不过也可能是题解写的太好了。用的和 E 差不多的容斥，多项式那一块也比较自然，不过很考验代码的写法。
四舍五入这场三个多项式，贵校是多项式王国吗.jpg
晚上七点多点了个外卖，结果发现外卖不能进校了，说什么放在校医院外卖柜。看来以后还是得吃食堂啊，不知道学知三旁边那个餐厅开了没（忘记叫啥了，反正我记得牛肉饭还不赖）。
7.24 (牛客多校 3)
写在前面：贵校是 AI 王国吗？整份题解看不出半点人类痕迹。
几乎被 B 硬控大半场。最后十分钟用拼式子 + 打表的方式凑出来了。
能过 600 个队简直是一个奇迹。
这题的核心是一个引理：
然后是 J，对于当前 \(x\)，先选中一个编号最大的后继 \(y\)，把所有 \(x\) 的其它后继接到 \(y\) 后面，题解里用了个可并堆，但实际上直接启发式合并也是可以的，当把所有 \(y\) 的后继接到 \(x\) 时，因为总是挑编号最大的，相对顺序依然有保证。
F 和 G 都是比较简单的题，G 有个小细节不过很快拍出来了。
D 这个网络流的建模还挺有意思的，感觉可以放到明年暑假前集训。
然后是 M，树上随机游走的变形，推出来还是有点麻烦的，只能说 lzh 还是太神了。
I 是个很耗时间的分讨，前半场 wbc 一直在做，三个小时的时候出狱了，非常给力。
7.25 (AMPPZ 2021)
波兰场。数据范围都很大，时间限制也很大。
C 本来不会的，但 lzh 看一眼就会了。大概就是奇数列的 \((x, y)\) 和偶数列的 \((y,x)\) 等价，就变成了给定数列 \(a,b\)，问几次交换能让 \(a=b\)，求逆序对即可。
D 是个纯纯模拟题。
A 题队友写了个 \(O(nk\log w)\) 然后加了些神秘剪枝卡过去了。
题解做法比较巧妙：先找出 \(k\) 个分属不同集合的点，具体的，先钦定 \(p_1=1\)，然后找到离 \(p_1\) 最远的点 \(p_2\)，这两个点肯定属于不同的集合，再找到离 \(p_1\) 和 \(p_2\) 最远的 \(p_3\)，以此类推找全 \(k\) 个点。剩下的 \(n-k\) 个点只用看离哪个点更近就属于哪个集合。暴力是 \(O(nk^2)\)，可以优化到 \(O(nk)\)。
I 题容易想到从高位到低位建字典树，但建树之后的讨论让人头大。一开始 wbc 写，但写到一半发现不会写了。后面我来写，对着样例改了好久才写对。一开始想的是如果 \(k\) 当前位是 \(0\)，就所有子树朝同一个方向走，到后面才意识到只用关心两个子树的状态。
题解里还提到了一种转化成最大独立集的做法，有时间看看。
K 题解里写的比较省略，思路是分段函数复合，然后放线段树上。
E 过的人很少，实际上做下来也就一般金牌题难度。
晚上困成狗了，吃完饭回来直接躺 234 床上睡了两个多小时。这床真是一如既往的舒服。
不知道是不是因为头顶的灯坏了的原因，打不起精神。后天得想办法报修才行。
7.26
白天在 steam 首页偶然发现了某款益智解谜游戏，下载下来玩了一下午，很好玩！
晚上打 CF，D 题差一点打表打出来了，差 \(n=2^k\) 且 \(x\) 是奇数的情况，比较遗憾。
回头补一下 D 和 F。
7.27 (神秘比赛)
从比赛名称看不出是什么比赛，查了一下貌似是 CCPC 省赛？
CGH 是纯签。E 是按位去询问，印象中第二次见，因为普通二分如果问到 \(0\) 就没办法判断 \(1\) 在哪一边。
A 和 L 我看了都不太会啊，不过好在也不是我开，队友秒了。
B 是个比较 implement 的题。对于一组询问 \((x,y)\)，可以枚举 \(x,y\) 路径上的点 \(p\)，其中 \(u\) 选取 \(p\) 向子树内延伸出的最大距离。因为这个延伸不能选取 \(x\) 方向和 \(y\) 方向的，所以要对每个点求它延伸出去的第一长，第二长和第三长的路径。然后再用倍增/树剖优化这个过程。
I 题 wbc 很快就想到了，但漏了一种情况，后面改了一下枚举顺序就过了。
K 最开始是 lzh 写，但 wa23（赛后发现是精度挂了），一直看不出就写 J 去了，然后 wbc 写，又一直 wa2，两个人都很红温。赛后发现 extra test 还是错的。（赛中并非因为 extra test）
我是感觉它要求精度 1e-9 有一点抽象，印象中没见过这么严格的。
F 我一开始没什么想法，我去想线段树分治去了，漏看了 kruskal 重构树，是后来 wbc 提醒我的。那做法就呼之欲出了，线段树离线维护后缀 min, max dfn，然后重构树上 LCA 的点权就是答案。
J 后来也被 lzh 开出来了，太神了。
D 先将答案用多项式表示，转化成求 \(\large \text{Ans}=[x^k]\left(\sum\limits_{i=1}^{c}f_i x^i \cdot \prod\limits _{t=c}^{n-1}(x+t)\right)\)，问了下 gemini，需要部分分式分解 + 多点求值。https://share.gemini.google/9qOCrXgko17x
有点困难啊，有这时间貌似可以先去补一下昨天的 CF。
7.28 (杭电多校 3)
两个小时之后开始坐牢场。
后面的题我都不太能对的上脑电波。
J 我纸上画了下，发现是 \(w^l+l-1\)，一看样例过了，交上去 AC 了，就没想那么多。后面看题解发现我当时那么推应该是假的。总之过程全错结果全对。
D, E 都是板子。F 我本来也想网络流，但不知道怎么处理字典序最小。于是打了个表，发现答案形如
cnt[25] = 13
4 6 9 10 11 13 14 15 17 19 21 23 25
7 -> 14
5 -> 10
3 -> 6于是倒着枚举，取奇数，如果和已有的冲突就改成它的倍数（比如枚举到 7，发现已经有 21 了，就改成 14），这样就能 AC 了。复杂度不会分析，但跑的飞快。
I 我看了没有很对的思路，贡献了两发罚时就扔给队友了。看了题解发现是将二元组连边，就能转化成边定向问题。
B 是个神秘题，队友双双红温。大概是按 \(x_i\) 排序，选一个后缀的球队赌它输。赛后发现这道题占了七页题解，吓晕了，队友会了就是我会了。
K 思路错了，没想到补集的角度。不过想到了可能也没那么轻松。
G 貌似一堆人 KD-Tree 或者暴力卡过去了。但是已经太晚了明天再看吧 UwU
7.29 (牛客多校 4)
完全不会签到了，I 写了快半个小时才签上。
B 我一直想的 \(x_2=1\)，先是发现是二次剩余，于是去找 \(k\) 使得 \(kp+1\) 是奇素数，枚举 \(k\) 再用 miller-rabin 判，最后发现 T 飞了。赛后看了题解才恍然大悟。
K 我那年的暑假集训见过类似的。两个点在原树上相邻，在点分树上肯定是祖先关系。因此令 \(dp[x][i]\) 表示考虑 \(x\) 的子树形成的点分树，\(x\) 位于深度 \(i\) 的方案数，然后 \(x\) 的每个儿子 \(y\) 的 \(dp[y][j]\) 可以选出 \(k\ (k\le j)\) 个元素插进 \(x\) 的祖先，因为是和原先 \(x\) 的 \(i\) 个祖先互插，所以贡献是 \(\binom{i+k-1}{k}\)。把转移写成卷积的形式然后做树上背包就行了。
E 是一个很幽默的题，因为很显然 \(i,j\) 相邻最优，那你每次询问用新的边权更新一下 \(m\) 条边的 \(\text{dis}\) 就做完了。歪榜惨案。
J 没想到是区间 dp。题解的做法感觉有点复杂了，这里推荐一下 starsilk 的做法，https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84269427。
- \(\text{dp1}[l][r][u]\) 表示当前栈节点为 \(u\)，按顺序访问 \(x_l,\cdots,x_r\) 时所需的最小操作次数。
- \(\text{dp2}[l][r][u]\) 表示在满足最小操作次数的前提下，过程中栈大小的最小增量。
状态转移的时候先保证 \(\text{dp1}\) 最小，\(\text{dp1}\) 相同再保证 \(\text{dp2}\) 最小。
虽然也是分题解里的两种情况转移，但会好写不少。
7.30 (杭电多校 4)
写在前面：这场的题解几乎不说人话，有点先用 gpt 生成，然后随机删去一些段落的美感。
这场基本全是队友在发力，我纯负优化。
开局签了个到，然后开始琢磨 F，琢磨了快两个小时，贡献了一发罚时之后还是扔给队友了。
B 大概在 3.5h 的时候就知道怎么做了，但一直 wa/re，遗憾离场。赛后发现做法一点问题没有，就是给边定向的时候逻辑比较混乱，如果先找出一个 dfs 树，给非树边任意定向，再给树边定向，就非常清晰。
C 队友声称对拍都拍不出来，我看了下对拍程序，发现两个队友题意都挂了。
H 比较好的理解方式是先按线段依赖关系建出树，然后 \(dp_c[u][t]\) 表示节点 \(u\) 这条线段在 \(t\) 时刻最多能有多少个位置是颜色 \(c\)。每个节点用一个动态开点线段树维护第二维，需要的是 “\(dp_c[u]\) 和 \(dp_c[v]\) 对应位置相加”，“单点查询”，“区间赋值” 三种操作。不难发现线段树合并可以满足所有需求。
当务之急是先搞一份线段树合并的板子。
一个细节是，线段树要维护每个节点的最大值和最小值。线段树合并的时候，如果当前节点最大最小值相等，表示这个区间已经被推平了，我们直接停止合并过程，并打一个区间加的 tag。可以证明这样剪枝之后时间复杂度是均摊 log 的。
7.31 (牛客多校 5)
L 开局吃饱罚时，跟 lzh 简单说了思路就给他重写了。赛后发现 wa 是因为 \(a_{i,j}\) 可以是负数，我求 \(\max a_{i,j}\) 的时候把记录最大值的变量初始化成 \(0\) 了。这扯不扯.jpg
E 我在草稿纸上列举了一下，发现如果唯一分解后指数的无序集合相同，答案就是相同的。但没想到的是，只要指数的和 \(\Omega(n)\) 相同，答案就相同。因为 \(\Omega(n)\le \left\lfloor \log_{2} n\right\rfloor\)，所以能暴力处理出每个 \(\Omega(n)\) 的答案。而给定一个 \(n\)，它的 \(\Omega(n)\) 也能线性筛预处理出来。
注意力还是太缺乏了。
后面差不多两个多小时我都在 all in C，其实我很想看其它题，但 C 过的队和其它题过的队明显不是一个数量级。
C 的关键是注意到只用为每一个 \(P_i\in [0,n)\) 选定一个到 \(Q_i\in [0,n)\) 的双射，而不用关注每一组 \((P_i,Q_i)\) 的顺序。将 \((P_i,Q_i)\) 按是否需要被进位，是否有进位，能分成四个等价类。按如下顺序排布即可（第一行是被进位，第二行是进位，左边是高位，右边是低位）
101..1010111..11000..00
010..0101011..11100..00问题转换成是否能寻找到这个双射，并安排 \(\frac{B}{2}\) 个被进位，且满足题目的所有要求。
这个好像做法挺多的，总之我找到的做法就是将 \(P_i\) 循环右移 \(\frac{B}{2}+1\) 得到 \(Q_i\)，再去找具体是哪些位需要被进位。
8.1 (Ucup4-25 Zagreb)
写在前面：最坐牢的一把。
起晚了，12 点 40 才到的 234，而且不知道为什么头开始一痛一痛的。
怀疑是昨晚没睡好。
之后头越来越痛，经常思考的时候被一阵晕眩打断。
但来都来了，还是得看看题。（后面发现还不如去睡觉）
跟榜看了下 C，其实很简单，但有一股神秘力量让我一直过不来样例。
呃啊，什么都不记得了。头好晕。
大概就是到中期一题都不会。
呃啊，头好晕。
后面几乎都在磕 E，但不会。
呃啊，头好痛。
呃啊，终于结束了。
呃啊，E 怎么是一个比较典的维护上凸壳。
呃啊，昏厥了，瘫倒在了 234 的床上。
好舒服。睡着了。
呃啊，几点了。
呃啊，怎么一从床上起来就头痛欲裂。
呃啊，好难受，打了个出租车回沙河了。
呃啊，差点因为神志不清倒在台阶上。
呃啊，幸亏明天是周日，可以直接睡到下午。
8.3 (杭电多校 5 验题)
写在前面：被 i 题硬控了。和 lzh 讨论了下，得到一个超级难写的做法，写着写着不会写了，就去给 div2 拉题了。选了几道我觉得很 edu / 很有趣的图论题。
感觉我们学校出的多校比前面的场都要 hard。
看了下 D 和 I，都不会做。要不退役吧.jpg
8.4 (2026 沈阳邀请赛)
晚上忙着给 div2 拉题。之后再补。
（upd on 8.8）周末了，突然发现这场还有几道题没补。
赛时发生了啥都忘记了，只记得 lzh 把 M 干出来了，非常厉害！
C 是一个萌萌题，过的人太少了，盘了一下发现也就银牌题难度。
G 需要，很强的注意力。
这个不变量 \(X\) 推导起来不复杂，但你得知道这个不变量长这样才行。不知道有没有更深刻的视角。
不过最难理解的应该还是充分性，即为什么删 ear 的时候只关注顶点颜色两两不同和删完仍剩三种颜色。几天过去了我依旧没什么头绪。
8.5 (牛客多校 6)
写在前面：被 I 题创飞了。这个题真的能过 200 多个队吗？
依旧天崩开局。D 题一眼拆点，但我 exgcd 忘了怎么写了，导致 100min 的时候才过。
另一边队友一直在卡 F，说是 \(O(26\cdot 2^{26})\) 但是大常数 T 飞了。
G 我感觉是个比较简单的题，但赛后才发现竟然没用上每个点度数不超过 \(3\) 的条件。想着想着忘条件了但结果全对.jpg
到了中期基本上是 A 和 I 双线都不会啊，就去看 J 了。
后面队友把 A 过了，但 I 还是没什么思路。赛后发现是个神秘且抽象的数位 dp。
8.6 (杭电多校 6)
写在前面：疑似 math 场，被一些奇奇怪怪的题干飞了。
一个很 fun 的事情是出题人 spj 没配好，导致 spj 的题输出空就能直接 AC。不过 hdu 也是一个很变态的 oj 就是了，只能说两边都有责任。
印象比较深是 G 题，赛时推导整整写满了两页 A4 纸，但如果一开始考虑 \(g(n)=f(n)-f(n-1)\)，转换成求 \(\sum g(n)\)。复杂程度明显减少一个量级。
值得注意的是 \(a(n)\) 除了一般的枚举倍数算贡献的做法，还可以线性筛出来。
首先 \(a(n)=\sum\limits_{i=1}^{n}\gcd(i,n)=\sum\limits_{d\mid n}d\sum\limits_{i=1}^{n}[\gcd(i,n)=d]=\sum\limits_{d\mid n}d\cdot \varphi(n/d)\)，然后
I 的话我没仔细看，赛后发现直接递归就是对的。
A 队友写了个 dp 搞过去了，赛后发现正解是 2-sat。
8.7 (牛客多校 7)
突然就起飞了。开局很顺利，中期三线做题竟然都做出来了，还都是 0 dirt，两个半小时的时候直接排到第 5 名。最终幻想了。
但是两个半小时之后就没题过了。D 疑似线性代数，打了个表但用处不大。不过 E 和 J 队友都有想法，最后 J 代码写出来了，过不了样例结果发现题意假了。
赛后拼尽全力 + 拷打 gpt 一小时，没能看懂 D 的题解。
I 题其实没题解说的这么麻烦。对于一个点 \(x\)，到其中一个子树 \(y_1\) 里访问到第一个叶子 \(l\)，之后再遍历其它子树 \(y_2,y_3,\ldots\) 的时候 LCA 就是 \(x\)。然后又因为深度相同取最早访问的，所以 \(x\) 子树里其它叶子写下的整数就是 \(l\)。dfs 向下，回溯的时候记录当前子树访问的第一个叶子的编号，存到一个 vector 里，check 一下就行。
8.8 (Ptz Summer 2019 Day3)
一整个下午都在面试 div2，四点半左右才面完，队友两个人打的。
8.10 (Ucup 4-22. Kyoto)
看到是日本人出的场就知道要牢底坐穿了。
开局跟榜看的 O，半小时没签上到，就给队友做了。关键点是注意到 \(x,y,x\oplus y\) 自然满足非退化三角形的情况，然后做一个容斥。
然后趁队友苦战 G 的时候，我把 D 给签了。因为队友 dp 水平肯定远超我，所以我直接看 F 去了。抓耳挠腮一个小时后终于发现可以写成 \(\frac{i}{g}\cdot \frac{j}{g}=A+\frac{B}{g}\) 的形式，只要枚举 \(B\) 的因数 \(g\)，再暴力枚举 \(A+\frac{B}{g}\) 的因数，复杂度就是对的。用一个 map 作为并查集，并一下就行。比较坑的地方是并的时候有可能超过 \(10^{16}\)，这部分是不算数的。
后面队友看别的题去了，我才发现 G 只要算出 \(k=0\sim n-1\) 时候的答案就能插值了，因为转移是一个前缀和，答案肯定是 \(n-1\) 次的多项式。
后面 lzh 把 J 过了，我就和 wbc 看 I。沟槽的日本人能不能出点阳间的构造，N 题也是。不过赛后上帝视角来看也都不难就是了。
E 题赛后发现是个很简单的转化。注意力匮乏了。
这里解释一下 “连通图乘上任意图” 的含义。设连通图的 EGF 是 \(A(x)\)，任意图的 EGF 是 \(B(x)\)，根据 EGF 的组合意义，\(A(x)B(x)\) 其实就是从 \(n\) 个顶点里选出 \(k\) 个顶点构造成一个连通块，然后其余 \(n-k\) 构造成任意图。考虑某个特定的已经构造好的大小为 \(n\) 的图 \(G\)，假设 \(G\) 由 \(m\) 个连通块构成。那在上述 \(A(x)B(x)\) 的枚举过程中，每个连通块都会被归到 \(A(x)\) 一次，即恰好有 \(m\) 种方式来选择这一个 “特殊的连通块”，因此 \([x^n]A(x)B(x)\) 的意义就是所有 \(n\) 个点的图的连通块数量之和。
H 题是一个没有听说过的引理，乍一看还挺震撼的，距离矩阵的行列式居然和树的形态无关。
8.11 (杭电多校 7)
天崩开局之对着签到题 H 狂 wa 三发，拉队友来看发现少判了一个 corner case。
之后去看 K，其实早就知道怎么做了，但上一次推路径压缩的转移方程已经是两年前了，摆弄了好久才推出来。
其实很简单，考虑当前 \(u\) 连通块的老根 \(p\) 和新根 \(r\)，那么有 \[ \begin{align} x_u&=k_{u}^{\text{old}}\cdot x_{p}+b_{u}^{\text{old}}\\ x_p&=k_p\cdot x_r+b_p \end{align} \] 于是 \(x_u=(k_u^{\text{old}}k_p)x_r+(k_u^{\text{old}}b_p+b_u^{\text{old}})\)，所以写成下面这样
auto find = [&] (auto self, int u) -> int {
if (u == f[u]) {
return u;
}
int p = f[u];
int r = self(self, p);
b[u] += k[u] * b[p];
k[u] *= k[p];
return f[u] = r;
};后面帮队友看 A，但队友转化错题意了，给了我个假的，我还用 ntt 推出来了。
最后四十分钟，我看了 C 还以为是大模拟，就 pass 继续去想 A 了。赛后才发现是一个搜索，码量还不大。
J 是一个结论题/猜猜题，马后炮来说不难猜到，但也只是马后炮了。
8.12 (牛客多校 8)
有猪写了三个小时 F，写到后面已经汗流浃背了，幸亏写出来了。
前两个小时题甚至都读错了，我读成把简单路径上的所有边连带端点一起删掉了，写完才发现样例过不了。只能说还好改起来难度不是很大，后面大部分时间都在对拍。
翻提交记录翻到一个队写的特别短，简单看一眼是 Link Cut Tree，仔细看就看不懂了，有时间再研究。https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84456193
出狱了之后还听 lzh 的思路 rush 出了 K，是一个只要想到用费用流就不难想的题。
要是出狱晚了说不定就完蛋了.jpg
其实本来没想这么复杂，但写着写着越想越不对劲，然后打了一堆补丁，到最后纯手写的部分都有 400+ 行。
晚上看了一下 J，感觉是纯纯科技题。
这个 de Bruijn 序列貌似已经是近一年第三次遇到了 UwU。晚点学习一下。
8.13 (杭电多校 8)
写在前面：从别的地方搬 12 道题 + 指挥 AI 写题解/写 std，我来我也能日赚 1w .jpg
被 G 题卡常浪费了 > 1h，cin 换快读 4000ms TLE -> 800ms AC，牛敌。
好久没用 fread 了，忘记本地输入到 stdin 要手动 ctrl + Z 了，赛时疑惑了好久。
反正出题人不是人类了，说再多也没有意义。
以后谁再给杭电多校付费我笑话谁。
晚上补了下 F，赛时搞了个假做法还过样例了，最后还是拍了下才发现有一个逻辑漏洞，假完了。
8.14 (牛客多校 9)
先鸽着。昨晚发生了一些意外导致一整晚都没睡好觉，晚上根本提不起精神。
8.15 (2023 Asia Seoul Regional)
比较简单的场。
整场好像就写了下 B 和 F。B 这个题里的伪代码写的非常抽象，没有被 dislike 是一个奇迹。这个伪代码貌似也没有什么特别的含义，草稿纸上画一下发现就是个模拟。F 是个典题，扫描线优化 dp。
C wbc 开局就秒了。赛后看了下题，发现确实不难。从上往下扫，遇到没被覆盖的点就向两侧尽量大地扩张作为一个新矩形。
E 是 lzh 写的。考虑用一个权值线段树，叶节点存逆排列，窗口向右移动的时候，相当于操作两个叶子，然后实际逆排列全局 \(-1\)，线段树节点存一个哈希值，这样每次更新后看根节点哈希值是否匹配上某个排列就行。
H 是一个很有趣的题。先将 \((a_i,b_i)\) 按 \(a_i\) 升序排，注意到对于每一列，\(\max(a_i,b_i)\) 是肯定能取到的，于是题目等价于求 \(\min(a_i,b_i)\) 的一个最大权上升子序列。
最后一个小时都在和 L 周旋，脑子一直绕不过来。赛后发现 A 只要知道结论的话就是纯板子题。
8.17 (神秘比赛)
队友两个人都卡 E 了。幸亏我没看，要不然就是三个人都卡 E 了。
8.18 (杭电多校 9)
我有点事没来，队友两个人打的。
8.19 (牛客多校 10)
打的比较舒服的一场。
8.20 (杭电多校 10)
终于脱离杭电的苦海了。相比牛客来说杭电真路边吧。
开局开的 L，贡献了两发罚时意识到并不是签到，遂换题。实际上是论文题来的。
卡常卡爆了，典型的中学生思维。时限连 std 的两倍都开不到，能不能禁止中学生出题。
C 是二分答案然后跑最大流，问就是跑不满。如果保留增广 \(2^k\) 后的图些许能做到理论更优的复杂度。
E 是全局最小割的板子，凑数来的。
D 题这里，\(J_2(w)=\sum\limits_{d\mid w}d^2\mu(\frac{w}{d})\)。
但我觉得题解其实做麻烦了。因为如果设 \(f(d)\) 满足 \(x^2=\sum\limits_{d\mid x}f(d)\)，可以莫比乌斯反演一步到位。 \[ F(n)=\sum_{d\mid n}f(d)\quad\longrightarrow \quad f(n)=\sum_{d\mid n}\mu(d)F\left(\frac{n}{d}\right) \] B 题赛时队友直接给了一个式子，我照着推的。和题解做法不太一样，我整理了一下。
另一种做法是题解里利用概率生成函数的做法。
学习了一下 PGF 的用法，还是第一次见。
概率生成函数 PGF
设离散型随机变量 \(X\in\{0,1,2,\dots\}\)，则 \(G_X(z)=\sum_{n\ge0}P(X=n)z^n\)。
基本结论
\(P(X=n)=[z^n]G_X(z)\)
\(E[X]=G_X'(1)\)
\(E[X^{\underline k}]=G_X^{(k)}(1)\)
\(E[X^k]=\sum_{i=0}^k\begin{Bmatrix}k\\i\end{Bmatrix}G_X^{(i)}(1)\)
\(\operatorname{Var}(X)=G_X''(1)+G_X'(1)-G_X'(1)^2\)
独立变量
若 \(S=X_1+\cdots+X_n\) 且相互独立，则 \(G_S(z)=\prod_{i=1}^nG_{X_i}(z)\)。
若 \(X_i\) 独立同分布，则 \(G_S(z)=G_X(z)^n\)。
随机次数求和
若 \(S=X_1+\cdots+X_N\)，且 \(N\) 与 \(X_i\) 独立、\(X_i\) 独立同分布，则 \(G_S(z)=G_N(G_X(z))\)。
常见离散分布的 PGF
以下约定：\(q=1-p\)；\(k\ge0\)。其中几何分布取 “成功前失败次数” 作为随机变量，负二项分布取 “第 \(r\) 次成功前失败次数” 作为随机变量。
- 伯努利分布
- \(P(X=k)=p^k(1-p)^{1-k},\quad k\in\{0,1\}\)
- \(G(z)=1-p+pz\)
- \(G'(z)=p\)
- \(G^{(k)}(z)=0,\quad k\ge 2\)
- 二项分布
- \(P(X=k)=\dbinom{n}{k}p^k(1-p)^{n-k},\quad k=0,1,\dots,n\)
- \(G(z)=(1-p+pz)^n=\displaystyle\sum_{k=0}^{n}\binom{n}{k}p^k(1-p)^{n-k}z^k\)
- \(G'(z)=np(1-p+pz)^{n-1}\)
- \(G^{(k)}(z)=n^{\underline{k}}p^k(1-p+pz)^{n-k}\)
- 几何分布
- \(P(X=k)=(1-p)^kp,\quad k=0,1,2,\dots\)
- \(G(z)=\dfrac{p}{1-(1-p)z}=\displaystyle\sum_{k=0}^{\infty}(1-p)^kp z^k\)
- \(G'(z)=\dfrac{p(1-p)}{[1-(1-p)z]^2}\)
- \(G^{(k)}(z)=\dfrac{k!\,p(1-p)^k}{[1-(1-p)z]^{k+1}}\)
- 负二项分布
- \(P(X=k)=\binom{k+r-1}{k}p^r(1-p)^k,\quad k=0,1,2,\dots\)
- \(G(z)=\left(\dfrac{p}{1-(1-p)z}\right)^r=\displaystyle\sum_{k=0}^{\infty}\binom{k+r-1}{k}p^r(1-p)^k z^k\)
- \(G'(z)=\dfrac{rp^r(1-p)}{[1-(1-p)z]^{r+1}}\)
- \(G^{(k)}(z)=r^{\overline{k}}p^r(1-p)^k[1-(1-p)z]^{-r-k}\)
- 泊松分布
- \(P(X=k)=e^{-\lambda}\dfrac{\lambda^k}{k!},\quad k=0,1,2,\dots\)
- \(G(z)=e^{\lambda(z-1)}=\displaystyle\sum_{k=0}^{\infty}e^{-\lambda}\dfrac{\lambda^k}{k!}z^k\)
- \(G'(z)=\lambda e^{\lambda(z-1)}\)
- \(G^{(k)}(z)=\lambda^k e^{\lambda(z-1)},\quad k\ge 0\)
- 离散均匀分布
- \(P(X=k)=\dfrac1{m+1},\quad k=0,1,\dots,m\)
- \(G(z)=\dfrac{1-z^{m+1}}{(m+1)(1-z)}=\dfrac1{m+1}\displaystyle\sum_{j=0}^{m} z^j\)
- \(G'(z)=\dfrac1{m+1}\displaystyle\sum_{j=1}^{m} jz^{j-1}\)
- \(G^{(k)}(z)=\dfrac1{m+1}\displaystyle\sum_{j=k}^{m} j^{\underline{k}}z^{j-k}\)
- 超几何分布
- 设 \(k_{\min}=\max(0,n-(N-K)),\qquad k_{\max}=\min(K,n)\)
- \(P(X=k)=\dfrac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}},\quad k=k_{\min},k_{\min}+1,\dots,k_{\max}\)
- \(G(z)=\dfrac1{\binom{N}{n}}\displaystyle\sum_{k=k_{\min}}^{k_{\max}}\binom{K}{k}\binom{N-K}{n-k}z^k\)
- \(G'(z)=\dfrac1{\binom{N}{n}}\displaystyle\sum_{k=k_{\min}}^{k_{\max}} k\binom{K}{k}\binom{N-K}{n-k}z^{k-1}\)
- \(G^{(k)}(z)=\dfrac1{\binom{N}{n}}\displaystyle\sum_{j=k_{\min}}^{k_{\max}} j^{\underline{k}}\binom{K}{j}\binom{N-K}{n-j}z^{j-k}\)
此外貌似还有利用半在线卷积的 \(\log^2\) 做法。