一种对操作赋势能来平衡权值的 trick

Hint 0：答案是

\log

量级的。

Hint 1：思考一个邪恶的交互库会做什么。

Hint 2：交互库无法得知选手策略——也就是说，它必须抓住某种变量，并尽可能最大/最小化它。同时选手的目标也就变成了最小/最大化这个变量。

你应该再完整阅读题解后再继续阅读。

Hint 0：请先完成 CF1924F。

Hint 1：字符串匹配问题的利器是 AC 自动机

Hint 2：解方程可以直接迭代

Sol：参考官方题解。

Hint -1：只有

3^n

种不同的对。

Hint 0：你要预处理一些信息，同时，查询时借助信息容斥。

Hint 1：直接列出所有可能的预处理信息所带来的查询容斥结果。（例如，例如，一种可行的映射是将 A+B+C 映射到 0，A+B映射到 1，B+C 映射到 2，B 映射到 3，询问时，对其进行容斥，例如，假如第一位是 A+C，第二位是 B，我们则使用 {0}-{3}，{3}计算答案）

Sol：显然，我们只需在本地把容斥系数比凑出来即可，所以你可以直接在本地跑一个

O(\omega^7)

的东西预处理一下。最终结果和 zxx 的差别极小。说明 zxx 的做法十分精妙！

你应该在完全掌握本题后再继续阅读

你也许已经注意到了，问题的关键在于预处理和查询复杂度之间的平衡。试说明一些 P12020 在 $n,q$ 分布不同时产生的复杂度情况（例如，当 $q=\Theta({100}^n)$ 时呢？我们显然必须预处理每一对答案。那么，当 $q=\Theta(n^{100})$ 时呢？ $q=\Theta(n^2)$ 时呢？ $n=\Theta(q^2)$ 呢？）

文章操作