contest2 题解
A. 寿司晚宴暴力 dp 是设 $f_{S_1,S_2}$ 表示两个人选的质因子的集合，转移直接预处理每个数的集合转移。这种题肯定是按照 $\sqrt n$ 分类讨论：对于 $\leq \sqrt n$ 的质数只有 $8$ 个，先状压，然后将其他的数字，如果最大的质因子 $> \sqrt n$ 就按照这个分类。显然每一类如果要选肯定都只会选给同一个人，所以对每一类先预处理 $g_{S}...
A. 寿司晚宴暴力 dp 是设 $f_{S_1,S_2}$ 表示两个人选的质因子的集合，转移直接预处理每个数的集合转移。这种题肯定是按照 $\sqrt n$ 分类讨论：对于 $\leq \sqrt n$ 的质数只有 $8$ 个，先状压，然后将其他的数字，如果最大的质因子 $> \sqrt n$ 就按照这个分类。显然每一类如果要选肯定都只会选给同一个人，所以对每一类先预处理 $g_{S}...
A. 序列分割容易发现分割顺序并不影响答案。因为你确定下来最终状态后，设每段的和分别为 $x_1,x_2,\ldots x_m$，发现你这个分割实际上是统计了 $\prod_{i < j} x_ix_j$。（每次都是统计跨过某个点的所有对，然后递归）所以我们可以设计一个 dp：$f_{i,j}$ 表示分了 $i$ 段，第 $i$ 次分的位置是 $j$ 的答案。记前缀和为 $s_i$，转...
A前面的 # 都贪心只填一个 )，用最后一个 # 调整即可。还是最后扫一遍判断比较靠谱。。尝试 $O(1)$ 特判挂了。。B设 $f_i$ 表示最后一个区间右端点选在 $i$ 的概率，我们对于每个点 $i$，处理出 $l_i$ 表示最大的数满足 $[l_i,i]$ 包含串 $T$（可以用哈希/kmp轻松处理）。然后转移的话先枚举这一段在哪里结束，再枚举下一段在哪里开始，转移是但是值域太大了怎...
A发现限制形如选了一条边之后，不能选和它端点相同的边。我们建一张新图，新图中的点代表原图中的边，如果两个边不能同时选就连边。首先可以证明问题一定有解：因为这个问题等价于对于每个弱连通分量找出一个环，而只要出度入度都为 $1$ 就一定有环，所以这种情况下更有环。我们发现原图的一种答案对应了新图的一种二分图染色方式，所以我们可以得到新图的每个连通块都是一个二分图，每个连通块有 $2$ 种染色方式...
A类似后缀数组算本质不同串的思路，考虑 $S$ 的第 $i$ 个前缀和第 $i+1$ 个前缀有多少个都会被计算，发现被算重的后缀等价于 $T$ 中 $S[i+1]$ 的出现次数。举个例子：abc abc 第 1 个前缀和第二个前缀都会算到 abc,原因是第一个前缀是 "a"+"bc"，第二个是 "ab"+"c"...