HDU 多校 2024 记录

赛时指赛时我过了这题或者嘴巴掉了，赛后指赛后补了或者嘴巴了。

第一场

B 星星（赛时）

就直接暴力 DP。

F 序列立方（赛时）

考虑立方的组合意义，即任意选三个子序列，使得它们相等的方案数。

$dp_{i, j, k}$ 表示三个子序列末尾分别在 $i, j, k$ 的方案数，这样不好转移，改成三个指针，每次选一个指针向后移一格或选择这三个指针上的数插到子序列末尾，为了避免数重钦定先移好第一个再移好第二个再移第三个即可。

D 传送（赛时）

线段树分治然后用并查集维护，每次相当于是要给一个集合加上某个权值。

给每个点打个 tag，令一个点的权值为其到根的所有祖先的 tag 之和。

设是把 $x$ 合并到 $y$，若要给 $x$ 子树加上 $v$，则 $tag_x \gets tag_x + v$。若要给 $y$ 子树加上 $v$，则 $tag_y \gets tag_y + v, tag_x \gets tag_x - v$。

分裂时直接 $tag_x \gets tag_x + tag_y$ 即可。

E 博弈（赛时）

先把问题转化成把这些字符等概率排成一个序列，Alice 取奇数位置组成字符串，Bob 取偶数位置，求 $A > B$ 的概率。

我们发现字符总数为偶数时 $P(A > B) = P(A < B)$，因为找到第一个不同的位置，交换一下，出现的概率是相等的，因此只要数 $P(A = B)$。那么需要满足 $\forall i, h_i \equiv 0 \pmod{2}$。求概率比较困难，直接数方案数，就是 $\frac{(\sum h_i / 2)!}{\sum (h_i / 2)!}$。

当字符总数为奇数时，不可能相等，但是需要考虑 $B$ 是 $A$ 的前缀的情况，此时需要满足有且仅有一个 $h_i$ 为奇数，钦定 $i$ 为最后一个字符，然后前面就和上面一样了。

I 数位的关系（赛时）

直接按题意数位 DP，设 $dp_{n, m, d, 0 / 1}$ 表示剩下 $n$ 位，子序列选了 $m$ 个数，子序列中最后一个数是 $d$，有没有卡到上限时的答案，直接转移即可。

---

A 循环位移（赛后）

对 $A$ 的所有循环位移求哈希值，然后直接 check 每个子串即可。

C 树（赛后）

注意到如果是序列可以方便地用线段树维护，然后线段树合并一下就好了。

G 三元环（赛后）

竞赛图三元环计数经典结论：数所有三元组个数，然后对于不构成三元环的，一定有一个点出度为 $2$，一个点入度为 $2$，随便选一个统计数量然后减掉即可。

然后这题就变成三维偏序了。

H 位运算（赛后）

每位分开算贡献，然后对于每一位直接暴力即可。

J 众数（赛后）

随机情况下答案大概率是前几大的，因此取出前 $O(1)$ 大的数 check 一下即可。

L 并（赛后）

先离散化，然后每个区域分开算。对于一个区域，选上的方案数只和覆盖他的矩形个数有关，容斥一下就好了。

---

Summary

小丑队打得最好的一集，总榜 rk10 中学 rk4，不过好像也没有特别超常的发挥，只是这次没有打到一半开摆而已。

第二场

G URL划分（赛时）

按题意模拟即可。

赛时 Tx_Lcy 没读懂题+和我写了同一道题罚了一发，战犯。

F 传奇勇士小凯（赛时）

算出每个点的期望天数，然后求从 $1$ 开始权值最大的链即可。

H 成长，生命，幸福（赛时）

考虑两个点 $u, v$ 中间的链，对于一个度数为 $d$ 的点，第一次会分裂出 $2$ 个二度点和 $d - 2$ 个三度点，之后每次 $1$ 个二度点分裂成 $2$ 个二度点，$1$ 个三度点分裂成 $1$ 个三度点和 $2$ 个二度点，因此分裂 $m$ 次后总点数为：

$$\begin{aligned} & 2 \times 2^{m - 1} + 2(d - 2)\sum\limits_{i = 2}^m 2^{m - i} + (d - 2) \\ =& 2^m + 2(d - 2)\sum\limits_{i = 0}^{m - 2} 2^i + (d - 2) \\ =& 2^m + 2(d - 2)(2^{m - 1} - 1) + (d - 2) \\ =& 2^m + (d - 2)2^m - 2d + 4 + (d - 2) \\ =& (2 - d) + (d - 1)2^m \end{aligned}$$

因此可以给每个点赋权值 $(2 - d) + (d - 1)2^m$，两个点 $u, v$ 的贡献就是中间所有点的点权和。

显然贡献是 $a + b2^m$ 的形式，比较大小是方便的，直接用求树的直径的 DP 方式做即可。

B 梦中的地牢战斗（赛时）

设 $dp_{x, y, S}$ 表示走到 $x, y$，消灭集合 $S$ 的怪物的最大收益，直接最短路即可。可以桶优化 dijkstra，按 $S$ 一层层转移。或者由于图很特殊直接 SPFA 也能过。

---

A 鸡爪（赛后）

鸡爪个数显然 $\lfloor n / 3\rfloor$，为了字典序最小就贪心编号小的点度数尽量多，乱分讨一下。

C 绝对不模拟的简单魔方（赛后）

赛时队友做法是模拟魔方暴力搜，赛后被 zjc 告知有高妙做法。

注意到无论怎么旋转角块相对魔方中心的方向是不会变的，因此对于每个角 check 一下有没有换贴纸即可。

J 女神的睿智（赛后）

按题意模拟即可。

K 在 A 里面找有 C 的 B（赛后）

对 $A$ 建 SAM，check 第一个条件直接把 $B$ 在 $A$ 上跑即可。对 $B'$ 和 $C$ 哈希，然后就可以 check 第二个条件了。

L 图计算（赛后）

算是经典题了，但是赛时胡了个原神做法给队友写没写出来。

在每张图中给每个连通块一个标号，则两个点在每张图中都联通当且仅当在每张图中都有同一个标号。对每个点在每张图中的标号哈希，然后启发式合并修改哈希值即可。

---

Summary

打得一般，没啥好说的。

第三场

A 深度自同构（赛时）

直接 DP，设 $dp_i$ 为 $i$ 个点的答案，枚举根的个数 $j$，$dp_i \gets dp_i + dp_{i / j - 1}$，枚举因数转移即可，复杂度为调和级数。

H 比特跳跃（赛时）

唐完了，写了一车锅。

考虑直接从 $1$ 跳跃到 $u$ 的时间是 $k \times (1 | u)$，而如果从某个点 $v$ 跳过去需要的时间就是 $dis_v + k \times (v | u)$，注意到如果 $v | u \ge 1 | u$ 就一定不如直接从 $1$ 跳，因此除了从 $1$ 出发的跳跃都一定满足 $v | u = u$。我们对每个点建虚点 $i'$，连边 $(i, i', 0), (i', i, k \times i), (i', (i | 2^k)', 0)$ 即可实现每个点到超集的跳跃，然后 dijkstra 即可。

B 旅行（赛时）

更为唐诗，提供巨大多罚时。

设 $f_{i, 0 / 1}$ 为 $i$ 子树内，$i$ 有没有在某个匹配中的答案。显然：

$$f_{i, 0} = \sum\limits_{u \in \mathrm{son}(i)} \max\{f_{u, 0}, f_{u, 1}\}$$

对 $f_{i, 1}$ 的转移就是枚举两个子树内的点 $u, v$ 使得 $c_u = c_v$，然后转移的权值是这样的：

$$f_{i, 0} + \sum\limits_{w \in \mathrm{anc}(u)} f_{w, 0} - \max\{f_{w, 0}, f_{w, 1}\} + \sum\limits_{w \in \mathrm{anc}(v)} f_{w, 0} - \max\{f_{w, 0}, f_{w, 1}\}$$

这里 $\mathrm{anc}(u)$ 是 $u$ 在 $i$ 以下的所有祖先（包括 $u$，不包括 $i$）。

用 dsu on tree 优化转移，从重儿子继承就是全局加一个数，打个标记即可。

C 游走（赛时）

全场唐诗的巅峰。

用二元组 $(t, p)$ 表示 $t$ 时刻酒鬼出现在位置 $p$，按时间排序。对于相邻两次事件 $(t_1, p_1), (t_2, p_2)$，显然不会矛盾的充要条件是 $t_2 - t_1 \equiv p_2 - p_1 \pmod{2}, t_2 - t_1 \ge |p_2 - p_1|$。这个可以方便地用 set 维护。

然后考虑询问，显然只和第一次事件 $(t_s, p_s)$ 有关，若询问最大值则答案为 $t_s - p_s + 1$，询问最小值则只要奇偶性与 $t_s - p_s + 1$ 相同即可。

但是这样是有问题的，原因是当 $p = 1$ 时酒鬼可能并没有开始移动而是停留在 $1$，即 $t \le t_0$。

于是我们分讨 $p = 1$ 时 $t$ 的情况。如果存在一个事件 $(t', p'), p' \ne 1$ 满足 $t' - p' + 1 \le t$，那么这个时候显然是在移动了，所以直接和上面一样考虑。

否则暂时先认为他是没有动的。

然后考虑询问，询问最大值时答案显然仍然是 $t_s - p_s + 1$，而当询问最小值时，找到所有和 $t_s - p_s + 1$ 奇偶性不同的事件，显然这些事件发生时必须停留，因此答案就是这些事件时间最大值 $+1$。当不存在这样的事件时则认为偶数则时间为 $0$，奇数则时间为 $-1$。注意当不存在 $p \ne 1$ 的事件时则两个取较小值。

因此用两个 set 维护这些事件，每次插入一次事件后把 set 内时间大于等于 $t_s - p_s + 1$ 的事件加进去即可。

---

E 数论（赛后）

注意到 $\gcd$ 只有 $n \log n$ 种，每种分开来考虑。

设 $f_i$ 为前 $i$ 个数的方案数，枚举区间 $j$ 使得 $(j, i]$ 的 $\gcd$ 满足要求，$j$ 是一段区间，可以线段树优化。

对后缀也做一遍，则 $i$ 的答案就是总方案数减去前缀后缀乘起来。

可能实现要精细一点。

G 单峰数列（赛后）

你就拿个数据结构嗯维护一下。

K 抓拍（赛后）

考虑随着时间增加长和宽的增量都是 $-2 \to -1 \to 0 \to 1 \to 2$，也就是长和宽都是凸的，因此周长也是凸的，然后三分就好了。

L 死亡之组（赛后）

若 $a_1 \ge L$，那第三小 $< L$ 或所有数的极差 $> D$。

若 $a_1 < L$，次小 $< L$ 或所有数极差 $> D$。

---

Summary

这次真唐完了，先是 A 被卡常，然后 H 写挂了一万个地方吃了 4 发罚时。然后开 C，刚开始没有意识到可以站在原地吃了一发，后来改好后又出了一万个锅导致最后才过，调到一半心态崩了直接弃疗，最后发现只是有个地方 !flag 写成了 flag，说明还得加训写代码能力。心态爆炸后 B 就写得有点急，有几发罚时是忘记清空，还有几发是 tag 打错了。

鉴定为写代码能力太弱，该加训了。

第四场

I 昵称检索（赛时）

对字母从前往后建子序列自动机，得到每个名字最后一个字符最前的位置。

对日期从后往前建子序列自动机，得到每个日期第一个字符最后的位置。

一个昵称合法当且仅当名字的位置在日期的位置之前，后缀和一下就好了。

L 寻找宝藏（赛时）

芝士询问的矩形：

答案一定是以下两种之一：

即在蓝色矩形中找一个点，由其左边到左下角的矩形内的点和其上面到右上角的矩形内的点构成。

实际上有用的点是有限的，只有所有 $(i + 1, p_i)$ 和这两个点：

然后我们发现两个红色矩形满足前一个的最大值小于后一个的最小值，因此可以分别求解然后直接加起来。

对于左下角的矩形，按高度从小到大加点，每个点的答案就是前面加入的点的最大值加上自己的权值，线段树维护一下即可。对于右上角的矩形就是从大到小加点，答案是后缀最大值。

然后每个询问 $O(1)$ 计算即可。

D 分组（赛时）

枚举集合 $S$，令 $A \cup B = S, C \cup D = U \setminus S$，然后枚举 $A$，计算出 $val_{S, i}$ 表示 $\max\{w_{f(A)}, w_{f(B)}\} \le i$ 时 $\min\{w_{f(A)}, w_{f(B)}\}$ 的最大值，对 $C$ 也一样做一遍，然后枚举 max 算答案即可，时间复杂度为 $O(3^n + 2^{n + m})$。

---

A 超维攻坚（赛后）

每次删掉的是一个平面的某一侧（或许可以称为半空间？），因此存活的就是一个半空间交，显然大概是个凸包。因此枚举点集，合法当且仅当这个点集的凸包满足所有点集外的点都在凸包外（不能在凸包上）。题解做法是枚举任意三个点求出平面，如果点集内所有点都在它的一侧则该面是凸包上的面。

C 最优 K 子段（赛后）

先二分答案，然后设 $f_i$ 表示前 $i$ 个最多划分出多少段，从 $sum_i - sum_j \ge mid \implies sum_j \le sum_i - mid$ 中按 $f_j$ 从大到小枚举，遇到 $i - j$ 为质数就结束，随机数据下期望枚举 $\ln n$ 次即可得到答案。从大到小枚举的过程可以用数据结构维护一下。

E 多层血条（赛后）

感觉唯一难点在于读懂题。按题意模拟即可。

F 延时操控（赛后）

首先注意到可以让自己先走 $k$ 步使时差为 $0$。

设 $dp_{i, x, y, h}$ 表示走 $i$ 步到 $(x, y)$ 敌人还剩 $h$ 血的方案数，在敌人不撞墙时他的偏移量应该是和我的偏移量相同的，但是要撞墙，因此再记两维 $dx, dy$ 表示敌人偏移量和我的偏移量的偏移量，显然 $dx + dy \le hp$，然后直接 DP 即可。

G 序列更新（赛后）

感觉很神的题。

考虑设置一个阈值 $B$，设 $V$ 为 $b$ 中第 $B$ 大的元素，当 $a_i \le V$ 时用 $b_{(i + k) \bmod n}$ 更新它，然后用 $b$ 中前 $B$ 大的数去更新 $A$。

后半部分复杂度为 $O(nB)$（认为 $n, q$ 同阶），对于前半部分，考虑一个位置执行的期望次数，即为：

$$\sum\limits_{i \ge 1} (1 - \frac{B}{n})^{i} = \frac{n - B}{B} = O(\frac{n}{B})$$

因此总时间复杂度即为 $O(\frac{n^2}{B} + nB)$，取 $B = \sqrt{n}$ 即可做到 $O(n \sqrt{n})$。

Summary

放假了还是有点摆。

第五场

F 猫罐头游戏（赛时）

手玩一下 $1, 1, a$ 的情况，大胆猜想和奇偶性有关。

那就按偶数个数分讨，发现最终必败状态 $1, 1, 1$ 是全奇数，全奇数无论怎么操作都会变成两奇一偶，两奇一偶可以变成全奇，两偶一奇也可以变成全奇，因此全奇必败，两奇一偶或两偶一奇必胜。

然后剩下全偶的情况，此时可以变成全偶或两奇一偶，但是在能全偶的情况下（即不全是 $2$）一定不会变成两奇一偶，因此对于状态 $2a, 2b, 2c$，操作后一定会变成 $2d, 2e, 2c$ 的形式，也就是无论怎么操作三个数都会保留一个 $2$ 的因子，因此全偶时一直同除 $2$ 再判断就好了。

E 树论（二）（赛时）

对于每个 $d \in [1, \lfloor n / 2\rfloor]$，找到所有 $d$ 的倍数，对于这些点构成的虚树中的边，其答案可以是 $d$ 的倍数。因此对于所有 $d$ 抠出虚树，然后对虚树上的边的答案对 $d$ 取 $\max$ 即可得到答案。

考虑这个怎么做，那就先转化为所有 $d$ 的倍数的点到虚树的根的直链取 $\max$，一共 $O(n\ln n)$ 次操作，最后查询每条边的值。

把操作按值从大到小排序，然后树上并查集维护即可。

求虚树的根就是 dfs 序最小和最大的点的 LCA。

总复杂度 $O(n\log n)$。

B Array-Gift（赛时）

答案下界显然是 $n - 1$。

上界是 $n + 1$，找两个数 $a \le b$，一次操作 $a \gets a + (b + 1 - a)$，一次操作 $a \gets a \bmod a$，然后得到一个 $1$，再 $n - 1$ 次操作把别的数变成 $0$ 就好了。

那就考虑什么时候答案是 $n - 1$，什么时候是 $n$。

$n - 1$ 显然是有数等于全局 $\gcd$。

答案为 $n$ 那就是有一次额外的操作。考虑每个数被什么数变成 $0$，要么是原本的数，要么是一次操作变出来的数。因此策略显然是在进行一次额外的操作之前将被操作的数的倍数都消掉，然后操作完这个数变成全局 $\gcd$。

暴力枚举额外的操作是什么然后 check 一下即可，复杂度 $O(n^3)$。

数据很水，赛时代码有点问题（直接把倍数都删掉再做额外操作）也过了。

Hacks：

不在额外操作前将被操作数的倍数消掉：

4
15 30 8 24

赛时代码的问题：

4
13 26 5 17

J 世末农庄（赛时）

对于单个询问，肯定是贪心从上往下取。注意到询问不独立，因此只要能找到从上往下第一个农作物重量不为 $0$ 的点，找的次数是 $O(q)$ 的。

找显然树上倍增，然后每次跳的时候要 check 一个点到根的链和是否为 $0$，要支持单点修改，树状数组维护一下好了，两部分都是一个 $\log$，因此总复杂度是 $O(q\log^2 q)$ 的。虽然两只 $\log$ 但常数很小，可以通过。

---

D 树论（一）（赛后）

注意到 $\mathrm{lcm}(i, j) \le 10^5$ 的对只有 $2\times 10^6$ 个左右，可以全部找出来，然后按 $\mathrm{lcm}$ 从小到大加入，每次加入一个对 $(i, j)$ 就给它们的 LCA 的权值加上 $1$ 或 $2$（取决于是否 $i = j$），然后询问就是求子树和。

G 猫咪军团（赛后）

对于猫的每个连通块，若存在树上的边不在猫咪通道上则需要两只猫，否则只需要一只猫。

必要性：如果不存在树上的边不在猫咪通道上则相当于猫也能走树边，只要一只猫一直追着狗即可。否则必须有另一只猫去堵着狗，不然狗可以在一条不在猫咪通道上的树边来回走。

充分性：任意选一只猫将狗拦截在其子树内，然后再找一只猫（可以是原来那只）走到其狗所在的儿子上，最后狗能走的空间只会一点点变小直到无路可走。

H 猫咪们狂欢（赛后）

先把所有点放在第一棵树上，加上贡献。

然后建 $k$ 个点代表每个狂欢猫，权值为其在第一棵树上的边的边权和的相反数，表示将其移开会损失这么多的贡献。

对于第一棵树上的有效边，建一个点连接其连着的两个点，权值为这条边的边权，表示如果这两个点都放到第二棵树上则会多减这么多贡献，要加回来。

对于第二棵树上的有效边，建一个点连接其连着的两个点，权值为这条边的边权，表示如果两个点都移到第二棵树上则会增加这么多贡献。

然后就变成了最大权闭合子图，直接最小割即可。

I 用心感受（三）（赛后）

只需考虑 $\mu(k) \ne 0$ 的 $k$，则 $k$ 的每个质因子只出现一次。然后：

因此转化成求：

$$\begin{aligned} & \sum\limits_{k = 1}^n \mu(k) \cdot (a \bmod k) \\ =& \sum\limits_{k = 1}^n \mu(k) \cdot \left(a - \left\lfloor\frac{a}{k}\right\rfloor \cdot k\right) \\ =& a \sum\limits_{k = 1}^n \mu(k) - \sum\limits_{k = 1}^n \mu(k) \cdot k \cdot \left\lfloor\frac{a}{k}\right\rfloor \end{aligned}$$

直接杜教筛即可。

M 飞行棋（赛后）

第一次结束的概率是 $\frac{1}{n}$，之后每次都是 $\frac{1}{n - 1}$，因此期望为：

$$\begin{aligned} & 1 + \frac{n - 1}{n} + \frac{n - 1}{n}\sum\limits_{i = 1}^\infty \left(\frac{n - 2}{n - 1}\right)^i \\ =& 1 + \frac{n - 1}{n} + \frac{n - 1}{n} (n - 2) \\ =& 1 + \frac{(n - 1)^2}{n} \end{aligned}$$

第六场

C 飞车狂飙（赛时）

按题意模拟即可。

B 造花（困难版）（赛时）

每个极大连通子图都是菊花图等价于去掉单点和仅两个点的极大连通子图后度数为 $1$ 的点的数量等于其他点的度数和。

维护这两个值，删掉一个点后受到影响的点要么直接与其相连，要么只有一条边且这条边连着的点直接与其相连且度数为 $2$，暴力更新一下即可。

H 树形 DNA（赛时）

朴素暴力是 $f_{u, v}$ 表示 $S$ 上 $u$ 子树能否匹配 $v$ 子树。

可以把 $T$ 的二度点缩起来，这样就只有至多 $40$ 个点，就可以暴力 DP 了。

考虑 check，相当于左子树对应的链在 $S$ 上一样的走走到一个点然后 check，右子树类似。

儿子有两个，没有好的方法快速往下跳，但是父亲只有一个，我们可以在 $f_{u, v} = 1$ 时从 $u$ 往上跳 $v$ 到父亲那条链长度次走到一个点，然后 check 中间这段是否相同，哈希一下即可，如果满足要求则更新这个祖先的值。

G 树上 MEX 问题（赛时）

嘴巴完让 wc 写了。

以 $0$ 为根，$\mathrm{mex} = m$ 时就是把 $0 \sim m - 1$ 的虚树缩成一个点，然后数有多少个含根连通块不包含 $m$，也就是 DP 时不从 $m$ 的子树转移，那从小到大加点，暴力跳父亲直到跳到虚树上，然后更新一下 DP 值即可。

---

A 造花（简单版）（赛后）

对每个点随便 check 一下就好了。

D 不醒人室（赛后）

也随便乱 check 一下。

E 交通管控（赛后）

我的做法：维护线性基，然后对每个状态去 check 能不能凑出来。

实际上不用这么麻烦，发现数据范围很小，暴力状压 DP 即可。

J Rikka 与子集 IV（赛后）

把树重剖一下，然后对于一条重链，设从下往上每个点的轻儿子的多项式的乘积为 $F_i$，每个点的多项式为 $G_i$，则有：

$$G_i = G_{i - 1} F_i x + 1$$

设 $H_i = F_i x$，展开一下就可以发现 $G_n$ 就是 $H$ 的后缀积的和，$G$ 的和就是 $H$ 的区间积的和，分治，维护乘积、前缀积的和、后缀积的和、区间积的和即可。

K 天天爱跑步（赛后）

对于树直接换根，基环树就再考虑一下经过环的情况，那对于每个子树在环上接的段是相同的，接上这段再跑一遍即可。

第七场

K 蛋糕上的草莓是蛋糕的灵魂（赛时）

要求 $2my | 2nx$，显然蛋糕一刀都不切。然后当 $\mathrm{lcm}(x, y) / x$ 是 $2$ 的倍数时 $2nx = \mathrm{lcm}(x, y)$，否则 $2nx = 2\mathrm{lcm}(x, y)$ 即可。

J 故障机器人想活下去（赛时）

显然贪心对 $a_i$ 最大的 $k$ 个用烟雾弹，拿堆维护一下即可。

I 关于 agKc 实在不喜欢自动化于是啥都自己合成这件事（赛时）

合成关系形成一棵树，求出每个叶子需要的时间，然后无限获取一个物品就相当于将其子树内的叶子的时间都变成 $0$，直接 check 一下就好了。

G 创作乐曲（赛时）

等价于求最长的子序列使得相邻两个差不超过 $k$，那对于一个 $a_i$，他后面只会接第一个 $[a_i, a_i + k]$ 中的数或者第一个 $[a_i - k, a_i]$ 中的数，然后这样转移就是 $O(n)$ 的了。

H 循环图（赛时）

先差分一下，然后考虑一层层转移，那就是先层内求出每一对 $(u, v)$ 的 $u$ 到 $v$ 的路径条数，然后把每个点此时的方案数加上，然后再转移到下一层，这样就是三个举证 $g_1, g_2, g_3$，要求 $1\sim T$ 的答案时，先跑 $\lfloor\frac{(T - 1)}{n}\rfloor$ 轮，然后再乘上一个 $g_1$ 再手动把贡献加上即可。

B 生产机器（赛时）

考虑如何 check 一个串是否合法，那显然就是贪心用当前小时匹配极长的一段，然后看能否全部匹配完。

因此设 $f_{i, 0 / 1 / 2}$ 表示前 $i$ 小时，后面还有未匹配的部分，此时 $i$ 已经全部用完 / $i$ 的黄色已经用完下一个还是黄色 / $i$ 的蓝色已经用完下一个还是蓝色时的方案数。

设当前两种颜色分别至多生产 $a, b$ 个，则：

$$f_{i, 0} \gets f_{i, 0} + f_{i - 1, 0} \binom{a + b}{a} \\ f_{i, 0} \gets f_{i, 0} + f_{i - 1, 1} \binom{a - 1 + b}{b}\quad(a > 0) \\ f_{i, 0} \gets f_{i, 0} + f_{i - 1, 2} \binom{a + b - 1}{a}\quad(b > 0)$$

后面两种转移都需要一个东西，就是注意到一种要用完，设是 $n$ 个，另一种不能用完，设至多用 $m$ 个，那这样的方案数就是：

$$\sum\limits_{i = 0}^m \binom{n + i}{n} = \binom{n + m + 1}{n + 1}$$

记这个是 $\mathrm{calc}(n, m)$。

感谢我的好队友 tx_lcy 不会求这个东西。

$$f_{i, 1} \gets f_{i, 1} + f_{i - 1, 0} \mathrm{calc}(a, b - 1) \\ \begin{cases} f_{i, 1} \gets f_{i, 1} + f_{i - 1, 1} \mathrm{calc}(a - 1, b - 1) & a > 0 \\ f_{i, 1} \gets f_{i, 1} + f_{i - 1, 1} & a = 0 \end{cases} \\ f_{i, 1} \gets f_{i, 1} + f_{i - 1, 2} \mathrm{calc}(a, b - 2)\quad(b > 1)$$

以上转移都基于 $b > 0$。

$f_{i, 2}$ 的转移是类似的。

注意特判 $a = b = 0$ 的情况。

考虑统计答案，若匹配在 $i$ 结束，则需要用 $f_{i - 1}$。

从 $f_{i, 0}$ 统计时两种球都可以选任意个，因此方案数为：

$$\begin{aligned} & \sum\limits_{i = 0}^a \sum\limits_{j = 0}^b \binom{i + j}{i} \\ = & \sum\limits_{i = 0}^a \binom{i + b + 1}{i + 1} \\ = & \sum\limits_{i = 0}^a \binom{b + i + 1}{b} \\ = & \sum\limits_{i = 0}^{a + 1} \binom{b + i}{b} - 1 \\ = & \binom{a + b + 2}{b + 1} - 1 \end{aligned}$$

注意此时是 $f_{i, 0}$，为了保证至少选一个还需要再 $-1$，后面两个是类似的但是不需要额外 $-1$ 了。

然后我写错模数又罚一发，队友悬着的心终于似了。

感觉还是得放下码（

// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1e9 + 7;

int T, n, fac[2000005], inv[2000005], dp[100005][3];

int C(int n, int m) {return (long long)fac[n] * inv[m] % mod * inv[n - m] % mod;}
int calc(int n, int m) {return C(n + m + 1, n + 1);}

int main() {
	fac[0] = fac[1] = 1;
	inv[0] = inv[1] = 1;
	for (int i = 2; i <= 2000002; i++) {
		fac[i] = (long long)fac[i - 1] * i % mod;
		inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
	}
	for (int i = 2; i <= 2000002; i++) inv[i] = (long long)inv[i - 1] * inv[i] % mod;
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		int ans = 1;
		dp[0][0] = 1;
		for (int i = 1; i <= n; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			dp[i][0] = dp[i][1] = dp[i][2] = 0;
			if (!a && !b) {
				dp[i][0] = dp[i - 1][0], dp[i][1] = dp[i - 1][1], dp[i][2] = dp[i - 1][2];
				continue;
			}
			dp[i][0] = (dp[i][0] + (long long)dp[i - 1][0] * C(a + b, a)) % mod;
			if (a) dp[i][0] = (dp[i][0] + (long long)dp[i - 1][1] * C(a - 1 + b, b)) % mod;
			if (b) dp[i][0] = (dp[i][0] + (long long)dp[i - 1][2] * C(a + b - 1, a)) % mod;
			if (b) {
				dp[i][1] = (dp[i][1] + (long long)dp[i - 1][0] * calc(a, b - 1)) % mod;
				if (a) dp[i][1] = (dp[i][1] + (long long)dp[i - 1][1] * calc(a - 1, b - 1)) % mod;
				else dp[i][1] = (dp[i][1] + dp[i - 1][1]) % mod;
				if (b > 1) dp[i][1] = (dp[i][1] + (long long)dp[i - 1][2] * calc(a, b - 2)) % mod;
			}
			if (a) {
				dp[i][2] = (dp[i][2] + (long long)dp[i - 1][0] * calc(b, a - 1)) % mod;
				if (a > 1) dp[i][2] = (dp[i][2] + (long long)dp[i - 1][1] * calc(b, a - 2)) % mod;
				if (b) dp[i][2] = (dp[i][2] + (long long)dp[i - 1][2] * calc(b - 1, a - 1)) % mod;
				else dp[i][2] = (dp[i][2] + dp[i - 1][2]) % mod;
			}
			ans = (ans + (long long)dp[i - 1][0] * (C(a + b + 2, a + 1) - 2 + mod)) % mod;
			if (a) ans = (ans + (long long)dp[i - 1][1] * (C(a + b + 1, a) - 1 + mod)) % mod;
			if (b) ans = (ans + (long long)dp[i - 1][2] * (C(a + b + 1, b) - 1 + mod)) % mod;
		}
		printf("%d\n", ans);
	}
	return 0;
}

---

D 战争游戏（赛后）

首先当 $2r_1$ 大于等于直径时第一步就可以把整棵树覆盖。

否则如果 $2r_1 < r_2$ 那显然无论在哪里都能走到一个未被覆盖的地方。

剩下 $2r_1 \ge r_2$，可以证明这样进攻方必胜，方法如下：先选择一个到 $s$ 距离为 $r_1$ 的点，以此为根，然后每次将选择的点向当前防守方所在的点移动一步，由于防守方永远无法穿过爆炸点，因此防守方无法走到爆炸点的子树外，直到防守方走到叶子就无路可走了。

E Hold’em Shark（赛后）

答辩模拟。

第八场

L cats 的电脑中毒（赛时）

一个串的时间就是和三个串异或后 $1$ 的个数的最小值。

考虑每一位，如果三个串都相同那就会产生 $1$ 的贡献，否则就是要么给其中一个产生 $1$ 的贡献，要么给另外两个产生 $1$ 的贡献。要最小值最大，因此初始时全都搞成两个的贡献，然后不断给最小值 $+1$，另外两个 $-1$ 即可。

F cats 的最小生成树（赛时）

JOISC2015Day4T1.

H cats 的数据结构（赛时）

先不考虑树，只考虑权值，将权值视为二维平面上的坐标，连边满偏序关系，稍微观察一下就可以发现一个子树内的点在一个以根为右上角的正方形内。要求字典序最小，那就将儿子按子树 $\min$ 从小到大排序，然后从左上到右下分配正方形即可。

I cats 的凸包计算（赛时）

考虑凸包的面积就是相邻两个点的叉积的和，把贡献拆开，枚举凸包上两个点 $i, j$ 和他们的值 $v1, v2$，当 $i, j$ 在下凸壳时其他点都要在 $(i, v_1), (j, v_2)$ 构成的直线上方，是上凸壳时都要在直线下方，因为每个点可以选的值是包含关系因此可以直接计算数量，然后乘上贡献就好了。

C cats 的飞机坠毁（赛时）

将问题转化一下，往正方向飞视为左括号，往负方向飞视为右括号，则两架飞机相撞当且仅当它们是一对匹配的括号。

考虑枚举答案为 $(a, b)$，则概率分成三段，一段是 $[a + 1, b - 1]$ 要形成合法括号匹配的概率，一段是 $[1, a - 1]$ 没有匹配的括号长度大于等于 $b - a + 1$，一段是 $[b + 1, n]$ 没有匹配的括号长度大于 $b - a + 1$，并且左边没有未匹配的左括号或右边没有未匹配的右括号。

设当前限制括号长度最长为 $lim$，设 $f_{i, 0 / 1}$ 表示 $[1, i]$ 中没有 / 有未匹配的左括号时合法的概率。

枚举 $i$ 是否匹配，若不匹配，有如下转移（其中 $p_i$ 为第 $i$ 个是左扩号的概率，$b_{i, j}$ 表示区间 $[i, j]$ 形成合法匹配的概率）：

$$f_{i, 0} = f_{i - 1, 0} (1 - p_i) \\ f_{i, 1} = (f_{i - 1, 0} + f_{i - 1, 1}) p_i$$

如果匹配，枚举和哪个匹配，有如下转移：

$$f_{i, 0} \gets f_{i, 0} + f_{j - 1, 0} p_j (1 - p_i) b_{j + 1, i - 1} \\ f_{i, 1} \gets f_{i, 1} + f_{j - 1, 1} p_j (1 - p_i) b_{j + 1, i - 1}$$

其中 $i - j + 1 \le lim$。

对于后缀也是一样的做一下然后整道题就做完了。

---

D cats 的重力拼图（赛后）

四个边界是一定能走到的，如果在中间还能额外走 $\max(n, m) - 2$，如果在边上且不在角上，如果是上下边界则可以额外走 $n - 2$，左右边界可以额外走 $m - 2$。

E cats 的二分答案（赛后）

显然我们只关心区间长度，然后 $k$ 至多 $65$ 左右即可。

设 $f_{n, k}$ 表示长度为 $n$，次数为 $k$ 时的答案，按 $mid$ 划分为三部分，若在 $[1, mid)$，则贡献为 $f_{mid - 1, k - 1}$，若恰好为 $mid$，则贡献为 $1$，若在 $(mid + 1, n]$，则贡献为 $f_{n - mid, k}$。

显然有用的状态只有 $O(\log n)$，记忆化一下即可。

G cats 的 k-xor（赛后）

考虑 $a + b < c$ 显然无解，$a + b = c$ 有无穷解。

否则考虑 $a + b - c$，那这个东西就相当于进位要产生的额外贡献，因此进制一定是这个的因子，暴力枚举一下即可。

J cats 的集合 1（赛后）

维护 Trie，或和与就是合并两个子树，异或就是交换两个子树，打下标记然后维护一下即可。

感觉会很 shit……

第九场

C 黑洞合并（赛时）

诈骗。

考虑贡献的组合意义，就是两堆里面各选一个，再在两堆的并里面选一个，设为 $x, y, z$，产生 $x \times y \times z$ 的贡献。

考虑若 $z = x$ 或 $z = y$，则会在 $x$ 和 $y$ 合并时产生这个贡献。否则无论哪两个先合并都会产生这样一个贡献，因此无论如何合并总贡献是相同的。

随便选一种暴力模拟即可。

F 融合矿石（赛时）

先 DP 出每个质量的“金辉石”质量的最大值，然后背包。

J 收集签名（赛时）

考虑走过的是含 $1$ 的连通块。

然后对于每次使用技能，显然一定要走到叶子。

因此考虑设 $f_{i, j}$，表示 $i$ 子树，已经到了 $i$，$j < 0$ 表示还有 $-j$ 个叶子没有被遍历，$j > 0$ 表示还有 $j$ 个技能用了但是没有确定终点的最小代价，一个子树内有没用的技能和没走的叶子时显然在子树内直接匹配掉就好。所以转移就是直接背包就好了。

---