A 第三心脏

令 ，问题等价于需要找到一个最小的 的倍数 ，使得 。
若质数 并非是 的因子，那么 就是一个合法的解，那么只需要枚举出最小的 即可。而前 个质数相乘已经超过 ，所以只需要枚举前 个质数。

B 尖端放电

考虑到当一个点被攻击第二次时我们就找到一个答案了，否则会至少覆盖一个新的点，所以直接暴力枚举所有点对直到找到答案即可。
时间复杂度 。

C 格点染色

设 为把前 个格子染成黑色的顺序方案数。考虑这 个方案中的一种：

• 如果 在 中是最后一个被染色的，那么方案数为 。
• 如果 在 中不是最后一个被染色的，在 中，对于 ，令 为 前一个染色的点，那么有 ，因此可以把 放在 与 之间染色， 是第一个染色的点时同理。因为 共有 个取值，所以方案数为 。

综上，总方案数为 。
时间复杂度 。

D 三千道路

一张竞赛图中两个点有三连通关系：

1. 能到达 ， 不能到达 。
2. 不能到达 ， 能到达 。
3. 能到达 ， 能到达 。

首先我们把强连通分量缩起来，如果有大小为 的需要输出 NO。之后一张 DAG 合法当且仅当它的拓扑序唯一。
充分性：当它的拓扑序唯一时我们之间前面的强联通分量都向后面的连即可。
必要性：若它的拓扑序不唯一，那么我们一定能找到两个强连通分量使得它们之间无法互相到达。
所以跑拓扑排序的时候判断是否任意时刻队列大小不超过一即可。
时间复杂度 。

E 字典树简单题

有一个显而易见的结论：对于任意一个节点 ，以及两个叶子节点 ，若满足 ，那么 到 的权值一定大于 到 的权值。
证明的话，考虑 与它父亲 的边的权值 。如果 ，那么 深度越小， 到 的权值在二进制表示下的位数就越多。如果 ，那么 到另一个儿子的权值一定为 ，同样满足 深度越小， 到 的权值在二进制表示下的位数就越多。
所以说其实只需要找到 的深度最大的祖先，满足该祖先子树内的叶子节点数量不小于 。然后答案一定就在这个祖先的不包含 的子树内。
可以用 LCT 维护每个点子树内叶子数量。对于加点操作，只需要把点 access 后，将整棵 Splay 打上加的标记。
对于询问操作，将点 access 后，相当于需要在这棵 Splay 上找到中序遍历最大的点满足子树内叶子不小于 ，直接在 Splay 上二分即可。那么只需要再支持查询点 子树内，权值第 大那个叶子。
如果没有加点操作，那么可以将叶子按照 dfs 序排序，然后对于 01 Trie 上的每一个点记录它子树内 dfs 序最小的叶子节点。那么 子树内编号最小的叶子的编号 就是答案点的编号。
有了修改操作后，注意到加点并不会影响其他叶子排名的相对顺序，所以相当于需要支持在序列中插入一个数，并动态维护 01 Trie 上每一个结点子树内排名最小的叶子的编号。为了方便，下文称一个点 子树内排名最小的叶子的编号为 的最小叶子。
在序列中插入一个数这个很简单，再用一棵平衡树维护序列即可。
对于 LCT 上的每一个点再维护一个值表示 01 Trie 上这个点的最小叶子。考虑一次加点操作的影响。首先新加的点的子树内只有新加的叶子，而对于原本就在 01 Trie 上的点 ，它的最小叶子会改变成新叶子当且仅当：

• 是 的祖先。
• 与新建点之间的边的权值为 ，且 到 之间的边权值均为 。

而 “ 到 之间的边权值均为 ” 等价于 ” 到 路径上所有点的最小叶子均相同“。所以其实一次加点操作的影响，就是 到“满足最小叶子等于 的最小叶子”的祖先 这一段路径。
可以在 Splay 上二分找到这个 点，然后就是路径覆盖了，直接打标记就好。
维护好每一个点的最小叶子后，询问时只需要在平衡树上查询最小叶子的排名 ，然后再查询排名为 的点即可。
时间复杂度 。

F 再见***与胖头鱼

当上次和这次攻击的胖头鱼不同时才会加一次攻击，显然所有胖头鱼都是一样的，所以我们可以只考虑一只胖头鱼造成的期望伤害。
构造多项式 其中 表示一只胖头鱼被连续攻击恰好 次时的概率。
考虑到转移到下一条鱼时的概率是由上一条被攻击的连续次数决定，所以这个概率在每个 处乘上。
首先指定一只胖头鱼计算它的期望伤害，定义多项式 其中 表示不是我们指定的胖头鱼被恰好攻击 次后就转回我们指定的胖头鱼的概率，那么有

那么多项式 就可以用来表示被指定胖头鱼两次被攻击间的概率。
然后我们枚举破坏圣盾的次数，那么造成的伤害（ 且不考虑初始的 点攻击力）就是
设 表示攻击了 次且破坏了 次圣盾时的概率，那么答案就是

考虑用多项式计算 ，首先我们开始时可能有一段不是攻击指定胖头鱼的，这一段就是 ，然后中间 段攻击胖头鱼的，且出了最后一个都需要一段间隔将两次隔开。
由于最后一段就结束了，此时不需要算上转移到另一条鱼上的概率，所以还需要一个 表示连续攻击一条胖头鱼 次的概率。
那么 的多项式就是

然后转到求答案就是

用等比数列的通项公式可以化为

多项式计算即可。时间复杂度 。