玄机

题意 ： 给你 $m$ 个子串和一个长度 $n$， 求出有多少个长度为 $n$ 的主串满足这些子串都在主串中出现过。

数据范围 ： $m \leq 4$， $\sum|\operatorname{str}| \leq 50$， $n \leq 10^9$。

题解 ：由于是多串的匹配， 考虑建出 AC 自动机， 在每个子串的终止节点打上标记，那么一个满足条件的字符串必然是从起点出发走 $n$ 步，且经过所有的标记点至少一次。

考虑 dp，设 $f[i][j][S]$ 表示目前位于 $i$ 点， 已经走过了 $j$ 个点，且经过的标记点的集合为 $S$ 的方案。

转移就枚举每一条边就行了，恰好经过 $n$ 个点可以使用矩阵快速幂优化。

发现这个 $S$ 集合很麻烦， 于是我们想找到一种方法把 $S$ 去掉， 因为 $m \leq 4$， 可以考虑枚举子集容斥。

具体地， 枚举强制不经过的点集 S （为什么不是经过的点 ？因为你不计下 $S$ 后不能保证经过所有的点）

那么算出不经过某些点的答案 $ans$ 后， 考虑它对总答案的贡献，也就是它的容斥系数。 经过一系列繁（lian）琐（meng）复（dai）杂 （cai）的计算后， 可知是 $(-1)^{|S|}$。

可以这么来考虑 ：不出现任意一个串的方案数 = 一个串没有出现的方案 - 两个串没有出现的方案 + 三个串没有出现的方案 ...

最终的答案就是总情况数 - 不出现任意一个串的方案， 推一下即可。

画心

题意 ： 把一个长度为 $n$ 的序列划分成若干段，要求每段长度在 $L, R$ 之间， 每段的权值为 $ax^2 + bx+c$，其中 $x$ 是每段权值和， 求最大划分权值。

很显然的斜率优化， 两只 $\log$ 做法是直接上线段树套李超树。

一只 $\log$ 的做法还没听懂， 咕了。

注意本题会爆 long long，请使用 __int128。

求索

题意 ：一棵树， 边有边权， 若一条路径的最大值与最小值之差不超过 $m$，则定义它的权值为 $mn \times len$，其中 $len$ 是边的总长， 求权值最大的路径。

常 数 大 赛

首先点分治 + 树套树或者三维偏序可以做到 3 只 log，树套树的常数巨大。

边分治 + 二维偏序可以做到 2 只 log，但要做两遍常数较大。