感觉是比较基础的多项式题，但我还是因为弱智错误调了一晚上,wtcl。

令 $q$ 的下标为 $0$，以下均在 $(mod\ x^n)$ 意义下运算。

首先构造生成函数，有

\[ \sum_{i \ge 0} { E_i x^i } = \sum_{i \ge 0} { \; \Big[ \; \sum_{j<i}{ \frac{q_j}{(i-j)^2}} - \sum_{j>i}{ \frac{q_j}{(j-i)^2}} \; \Big] \; x^i } \]

\[ \qquad\qquad\qquad\qquad\;\;\, =  \sum_{i \ge 0} { \; \Big[ \; \sum_{j<i}{ \frac{q_j}{(i-j)^2}} \; \Big] \; x^i } - \sum_{i \ge 0} { \; \Big[ \; \sum_{j>i}{ \frac{q_j}{(j-i)^2}} \; \Big] \; x^i }\]

先看前半部分，有

\[ \sum_{i \ge 0} { \; \Big[ \; \sum_{j<i}{ \frac{q_j}{(i-j)^2}} \; \Big] \; x^i } = \sum_{i \ge 0} { \; \Big[ \; \sum_{j+k=i,k \gt 0}{ \frac{q_j}{k^2}} \; \Big] \; x^i } \]

\[ \qquad\qquad\qquad\qquad\qquad\quad\;\; = \Big[ \; \sum_{i \ge 0} { q_i x^i } \; \Big] \; \Big[ \; \sum_{i \gt 0} { \frac{1}{i^2} x^i } \; \Big] \]

对于后半部分，将 $q$ 翻转即可。

使用 $FFT$ 进行卷积，时间复杂度 $O(n \log n)$。

波特题。strong。

首先发现 A,B 之间互不影响，考虑枚举分割线 $i$，定义 $f(i)$ 表示以 $i$ 为结尾的 AA 串个数，$g(i)$ 表示以 $i$ 为开头的 AA 串个数。则答案为 $\sum\limits_{i=1}^{n-1} f(i)g(i+1)$。

然后发现直接 hash $\mathcal O(n^2)$ 求 $f(i),g(i)$ 就能拿 95pts，考场上就不用考虑正解了，直接冲 hash。但是练习还是要学一下的。

观察 AA 串中，两个 A 串的开头距离为 $|A|$。

考虑枚举 $w=|A|$，用一个波特才能想到的技巧：每隔 $w$ 撒一个点。这样每个 AA 串恰经过相邻两点。

设相邻两点分别为 $x,y$，定义 $\mathrm{lcp}(x,y)$ 表示以 $x,y$ 为开头的后缀的最长公共前缀，$\mathrm{lcs}(x,y)$ 表示以 $x,y$ 为结尾的前缀的最长公共后缀。

画个图就会发现，若有 AA 串经过 $x,y$，则必有 $\mathrm{lcp}(x,y)+\mathrm{lcs}(x,y)\ge w$，且这是 AA 串存在的充要条件。

然后又发现，$\mathrm{lcp}(x,y)+\mathrm{lcs}(x,y)$ 可能比 $w$ 大，此时有连续的一段点是 AA 串的开头/结尾，用两个差分数组维护即可。

时间复杂度：$\mathcal O(n(\log n+\ln n))$。

拒绝「命运」的安排。

小清新题。

这题给我最大的启示就是：不要被经验限制，开放思维，尝试不同的角度，一些平平无奇的性质可能就是解题的关键。

首先注意到，题目中的限制很可以容斥的样子。但事实上，如果一直将思维卡在容斥，这题就真的做不出来了。

我的思路比较清奇，我一开始想到的是 dp，将限制条件存入 $u$ 节点的 std::vector，然后一遍 dfs 算出来。

然而这样想同样存在一个问题，就是 $v$ 的分布不好处理。你会发现在这种思路中，我们几乎没办法确定方案。

归根结底是这样的 dp 过程能利用的有效信息太少，状态不好设计和转移。考虑正难则反。

不难发现，对于两组限制 $(u_1,v)$ 和 $(u_2,v)$，不妨设 $\mathrm{dep}(u_1)\le \mathrm{dep}(u_2)$，此时只用考虑 $u_2$ 的限制。

通过这个小思考，我们发现可以将此时还未处理到的最深的上节点的深度存入状态，进行转移。

令 $f(u,i)$ 表示处理了 $u$ 的子树，此时最深的未满足的限制的上节点深度为 $i$ 的方案数。

考虑加入一个子树，枚举 $u\to v$ 这条树边的权值：

权值为 1：则 $v$ 以上的限制全部被满足，最大深度仍由 $u$ 的子树提供，即 $f(u,i)\gets f(u,i)\times \sum\limits_{k=0}^{\mathrm{dep}(u)} f(v,k)$。

权值为 0：此时 $i$ 有可能是由 $u$ 的子树取到，也可能是由 $v$ 的子树取到，故 $f(u,i)\gets f(u,i)\times \sum\limits_{k=0}^{i}f(v,k)+f(v,i)\times \sum\limits_{k=0}^{i-1} f(u,k)$。

其中第二个和式上边界 -1 的原因是 $f(u,i)\times f(v,i)$ 已经在第一个和式中计算过，避免重复。

综上，$f(u,i)\gets f(u,i)\times \sum\limits_{k=0}^{\mathrm{dep}(u)} f(v,k)+f(u,i)\times \sum\limits_{k=0}^{i}f(v,k)+f(v,i)\times \sum\limits_{k=0}^{i-1} f(u,k)$。

直接 dp 可以获得 64pts，发现有效节点不多，把虚树建出来就可以获得 72pts，但我并不会建虚树。

（当然这题数据水，一部分出题人想不到的 $\mathcal O(n^2)$ 解法没被卡，甚至铃酱的 $\mathcal O(n^2\log n)$ 做法被放过去了，这很 CCF）

注意到这个 dp 的状态和深度有关，而且涉及求和，这正是线段树合并擅长的。

综上，使用线段树合并进一步优化 dp，时间复杂度 $\mathcal O(n\log \mathrm{dep})$，其中 $\rm dep$ 为深度最大的节点深度。

神秘链接

首先发现 $f_i=\sum_{j=1}^m f_{i-j}$。

$m\le 5$，所以可以 $\mathcal{O(m^3\log n)}$ 计算 $f(n)$。

以 $m=3$ 为例：

$$\begin{bmatrix}f_n & f_{n-1} & f_{n-2}\end{bmatrix}\times \begin{bmatrix}1 & 1 & 0\\1 & 0 & 1\\1 & 0 & 0\end{bmatrix}=\begin{bmatrix}f_{n+1} & f_n & f_{n-1}\end{bmatrix}$$

撕烤如何计算 $g$。根据矩阵的结合律，先考虑转移矩阵的计算，最后再整体乘上初始矩阵。

考虑这样一个事实：$f(x+y)=G^{x+y}=G^x\times G^y=f(x)\times f(y)$，其中 $G$ 为转移矩阵。

基于此，可以 dp 求解原数字串的划分。

比如：$g(123)=g(12)\times f(3)+g(1)\times f(23)+f(123)$。

这样求解的前提是我们知道原串每个子段的 $f$ 值，这个可以递推求解。

设 $D_{i,j}=f(s_{i\sim j})$，则：

$$D_{i,j}=\begin{cases}f(s_i), & \mathrm{if}\ i=j\\f(s_i\times 10^{j-i})\times D_{i+1,j}, & \mathrm{Otherwise}\end{cases}$$

则有：

$$g_i=\sum_{j=0}^{i-1} g_j\times D_{j+1,i}$$

预处理 $D_{i,j}$ 之前先算出来 $f(c\times 10^k)$，时间复杂度可以做到 $\mathcal{O(n^2m^3)}$，我这里写少了，只处理了 $f(10^k)$，不过开 O2 也可以过。

元音和辅音显然是独立的，我们考虑分开计算。记只用元音和辅音组成的单词数分别为 $ans_p$ 和 $ans_q$，则总答案为 $ans_p \times ans_q + ans_p + ans_q$。

考虑计算 $ans_p$，$ans_q$是类似的。枚举单词长度 $i$，显然有，

\[ ans_p = \sum_{i=1}^{n}{(i+1)p^i} = \frac{ p \frac{1-p^n}{1-p} + p -(n+1)p^{n+1}}{1-p} \]

这个式子可以 $O(\log n)$，但问题是 $1-p$ 不一定有逆元，所以是行不通的。

由于没有逆元，我们希望递推计算答案。

记 $f(n) = \sum_{i=1}^{n}{(i+1)p^i}$，整个式子是不好递推的，我们把它拆开，用 $p^i$ 和 $ip^i$ 去凑它。我们有，

\[ \left\{\begin{array}{l} f(i) = f(i-1) + (i+1)p^i = f(i-1) + ip^i + p^i\\ ip^i = p \times (i-1)p^{i-1} + p \times p^{i-1}\\p^i = p \times p^{i-1}\end{array}\right.\]

这样就可以构造矩阵了。

\[ \begin{bmatrix} f(i-1)\\ (i-1)p^{i-1}\\ p^{i-1} \end{bmatrix}  \begin{bmatrix} 1 & p & 2p\\ 0 & p & p\\ 0 & 0 & p \end{bmatrix} = \begin{bmatrix} f(i)\\ ip^i\\ p^i \end{bmatrix} \]

时间复杂度$O(\log n)$。