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考虑对串的反串建后缀树，答案就是叶子节点个数。注意到这时的叶子节点一定是一段前缀，如果一个前缀 $s[1\ldots i]$ 是叶子节点当且仅当它不属于任何一个点的 border 集合，所以问题变成了求每个前缀的 border 集合的并的大小，用 kmp 解决即可。这里发现一个结论：每个前缀的 border 集合的并的大小等于 $\max{fail_i}$。证明要考虑这个命题等价于叶子节点...
A. 序列分割容易发现分割顺序并不影响答案。因为你确定下来最终状态后，设每段的和分别为 $x_1,x_2,\ldots x_m$，发现你这个分割实际上是统计了 $\prod_{i < j} x_ix_j$。（每次都是统计跨过某个点的所有对，然后递归）所以我们可以设计一个 dp：$f_{i,j}$ 表示分了 $i$ 段，第 $i$ 次分的位置是 $j$ 的答案。记前缀和为 $s_i$，转...
因为某些原因晚了半小时打，然后就疯狂挂题，从前二（或许？）挂到了倒一A可以考虑哈希。这里可以给每个值随机一个哈希值，合并操作定义为异或。考试的时候写的N模好像 T 飞了。。事实上这个数据一模数就能过#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define fi first #define s...
A前面的 # 都贪心只填一个 )，用最后一个 # 调整即可。还是最后扫一遍判断比较靠谱。。尝试 $O(1)$ 特判挂了。。B设 $f_i$ 表示最后一个区间右端点选在 $i$ 的概率，我们对于每个点 $i$，处理出 $l_i$ 表示最大的数满足 $[l_i,i]$ 包含串 $T$（可以用哈希/kmp轻松处理）。然后转移的话先枚举这一段在哪里结束，再枚举下一段在哪里开始，转移是但是值域太大了怎...