求若干个首项为 $0$ 公差为 $1$ 的等差数列总和为 $s$ 的情况下长度之和最少为多少。

注意到和不超过 $s$ 的这样的等差数列只有 $\sqrt s$ 种，暴力 DP 即可。

fail 数上的子树更改或查询是易于维护的，而对一个字符串在 AC 自动机上经过的路径进行更改或查询只能暴力做。

所以如果直接把 CF547E 的做法用到这里来，区间询问拆成前缀，对每个前缀按顺序处理，fail 树上子树加，每个询问在 AC 自动机上暴力求和，时间复杂度为 $O(A\sum|s_i|+B\sum|s_{t_i}|)$。其中 $t_i$ 为第 $i$ 次询问的文本串，$A$ 为区间加的时间复杂度，$B$ 为单点查询的时间复杂度。注意式子中第一个 $\sum$ 是有约束的（不超过 $10^5$），而第二个没有。这样我们就获得了一个与文本串串长相关的暴力做法。

注意到第一个做法的问题在于遍历文本串的次数过多。如果选择每个文本串只进行一次遍历，对经过的所有点做 $O(1)$ 子树加（树上前缀和），然后依此处理该文本串相关的所有询问，这个做法的时间复杂度为 $O(\sum|s_{t_i}|+|t|\sum|s_i|)$，$t$ 为询问的文本串序列。

于是我们根号分治：对于长度不超过 $\sqrt{\sum|s_i|}$ 的串使用第一种算法，使用 $A=O(\sqrt n),B=O(1)$ 分块进行区间加单点查；否则使用第二种算法，此时 $|t|=O(\sqrt{\sum|s_i|})$。总时间复杂度为 $O((\sum|s_i|)^{1.5})$

询问有多少种选取的方案，使得取出的集合的并包含给定集合。

一眼 NP，于是考虑暴力容斥。

将选出集合的并包含给定集合 $\{a_1,a_2,\cdots,a_n\}$ 看作选出的集合并包含 $a_1$ 且包含 $a_2$ 且包含 $a_3$……。经过一步容斥后转化为选出的集合并不包含 $b_1$ 且不包含 $b_2$ 且不包含 $b_3$……（其中 $\{b_1,b_2,\cdots,b_n\}\subseteq\{a_1,a_2,\cdots,a_n\}$），也就是对于询问集合的每个子集，求可选集合中与它不交的有多少个。

暴力显然不可取，考虑到质因数分解带自然根号：每个质因数至多有一个不小于 $\sqrt n$ 的质因子。所以我们只用状压前 13 个质数，单独讨论最大的质数即可。