contest3 题解
A. 小星星考虑一个大家都会的暴力 dp：设 $f_{v,i,S}$ 表示确定好了 $v$ 的子树内的点映射到集合 $S$ 上，并且 $v$ 对应 $i$ 的方案数。合并子树的时候要保证 $S1$ 和 $S2$ 不交，然后根据图是否有边来判断。复杂度瓶颈显然在每次转移时的枚举子集。我们考虑我们这个第三维的作用是什么：是为了防止多个点映射到同一个点上。我们如果限定这个数的映射只能用 $S$ 然...
A. 小星星考虑一个大家都会的暴力 dp：设 $f_{v,i,S}$ 表示确定好了 $v$ 的子树内的点映射到集合 $S$ 上，并且 $v$ 对应 $i$ 的方案数。合并子树的时候要保证 $S1$ 和 $S2$ 不交，然后根据图是否有边来判断。复杂度瓶颈显然在每次转移时的枚举子集。我们考虑我们这个第三维的作用是什么：是为了防止多个点映射到同一个点上。我们如果限定这个数的映射只能用 $S$ 然...
A考虑对串的反串建后缀树，答案就是叶子节点个数。注意到这时的叶子节点一定是一段前缀，如果一个前缀 $s[1\ldots i]$ 是叶子节点当且仅当它不属于任何一个点的 border 集合，所以问题变成了求每个前缀的 border 集合的并的大小，用 kmp 解决即可。这里发现一个结论：每个前缀的 border 集合的并的大小等于 $\max{fail_i}$。证明要考虑这个命题等价于叶子节点...
A前面的 # 都贪心只填一个 )，用最后一个 # 调整即可。还是最后扫一遍判断比较靠谱。。尝试 $O(1)$ 特判挂了。。B设 $f_i$ 表示最后一个区间右端点选在 $i$ 的概率，我们对于每个点 $i$，处理出 $l_i$ 表示最大的数满足 $[l_i,i]$ 包含串 $T$（可以用哈希/kmp轻松处理）。然后转移的话先枚举这一段在哪里结束，再枚举下一段在哪里开始，转移是但是值域太大了怎...
A发现限制形如选了一条边之后，不能选和它端点相同的边。我们建一张新图，新图中的点代表原图中的边，如果两个边不能同时选就连边。首先可以证明问题一定有解：因为这个问题等价于对于每个弱连通分量找出一个环，而只要出度入度都为 $1$ 就一定有环，所以这种情况下更有环。我们发现原图的一种答案对应了新图的一种二分图染色方式，所以我们可以得到新图的每个连通块都是一个二分图，每个连通块有 $2$ 种染色方式...
这场ABC都是Div2 ABC种偏难的。。但是后面难度就上不去了（可能是我只会做一点点套路题的原因？）A这里的反转是 reverse，不是取反。。自闭了。。设这两个数是 $a,b$，其中 $a > b$，由于字典序最小，所以我们从低位向高位看，要求尽量是 $0$。我们找到 $b$ 的 $\text{lowbit}$ $p$，发现比 $p$ 低的位都是无法改变的（由 $a$ 决定），我...