元音和辅音显然是独立的，我们考虑分开计算。记只用元音和辅音组成的单词数分别为 $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)$。