神秘链接

首先发现 $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)$。

考虑将答案转化为期望，最后乘上 $2^{n-1}$。

如果 $a_i$ 前是加号，有 $\frac{1}{2}$ 的概率，因此贡献为 $\frac{a_i}{2}$。

如果 $a_i$ 前是乘号，有 $\frac{1}{2}$ 的概率，贡献是 $\frac{a_i-1}{2}$ 乘以前 $i-1$ 个数的期望后缀乘积，这个可以递推算出来。

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

简要题解：

先手推一波式子：

$$f(i,m)=a^{m-1}\times f(i,1)+\frac{a^{m-1}-1}{a-1}\times b$$

再次展开，得：

$$\begin{bmatrix}f(i,m) & 1\end{bmatrix}\times \begin{bmatrix}a^{m-1}\times c & 0\\a^{m-1}\times d+\frac{a^{m-1}-1}{a-1}\times b & 1\\\end{bmatrix}=\begin{bmatrix}f(i+1,m) & 1\end{bmatrix}$$

高精度十进制快速幂即可。

注意特殊处理 $a=1$ 的情况。

显然的贪心思路：让被经过期望次数多的边的编号尽量小。但是这题 $m$ 可能为 $10^5$ 级别，不能对边进行求解。

考虑求出每个点的期望经过次数，设其为 $f_i$，令点 $i$ 的度数为 $deg_i$。

则有:

$$f_1=(\sum\limits_{(1,v)\in E\land v\neq n} \frac{f_v}{deg_v})+1,f_i=\sum\limits_{(i,v)\in E\land v\neq n}\frac{f_v}{deg_v}(1\lt i\lt n)$$

$v\neq n$ 的原因是，一旦 $v=n$，就走到 $n$ 了，肯定不可能再走回 $i$。

因为有后效性，所以将其列成矩阵进行高斯消元求解。

则：

$$\forall (u,v)\in E,g(u,v)=\frac{f_u}{deg_u}+\frac{f_v}{deg_v}$$

其中 $g(u,v)$ 表示边 $(u,v)$ 被经过的期望次数。

注意特判 $u\neq n,v\neq n$，原因同上。

时间复杂度 $\mathcal O(n^3)$。