固定 $m,k$, 令 $[x^t]P(x)$ 表示 $n=t$ 时的答案，令 $[x^t]Q(x)$ 表示满足以下条件的字符串 $S$ 个数： 能通 过 $t$ 次操作消完且不能划分成 $S_1S_2$ 满足 $S_1,S_2$, 分别能用 $a,t-a$, 次消完（其中 $0 < a < t$）。易证这等价于 $S$ 不存在能通过若干次操作消完且长度在 (0,|S|)$ 的前（后）缀。显然我们有：

$$\begin{cases} P(z) &= \frac{1}{1-Q(z)}\\ Q(z) &= mzP^{k-1}(z) - \frac{1}{m}P(z)Q^2(z) \end{cases}$$

即

$$1-\frac{1}{P(z)} = mzP^{k-1}(z) - \frac{1}{m} P(z) \left(1-\frac 1{P(z)}\right)^2$$

直接进行牛顿迭代，可以得到 $40$ 分。

记 $\mathcal P=P-\mathcal E$，使用 Lagrange 反演可知：

$$[z^n] \mathcal P(z) = [z^{n-1}] \frac{m}{(1-mz)^2(1-(m-1)z)^{n(k-1)}}$$

我们的答案 $I$ 即为：

$$\begin{split} I &= \frac{1}{n} \sum_{i=0}^{n-1} (n-i) \binom{n(k-1)+i-1}{i}m^{n-i}(m-1)^i\\ &= \sum_{i=0}^{n-1} \binom{n(k-1)+i-1}{i}m^{n-i}(m-1)^i-\sum_{i=0}^{n-1} (k-1)\binom{n(k-1)+i-1}{i-1}m^{n-i}(m-1)^i \end{split}$$

两侧都是容易计算的形式，直接暴力 $\Theta(nk)$ 计算可以得到额外的 $40$ 分。使用 Lucas 定理结合数位 dp 即可在 $\Theta(p \log n+p \log k)$ 的时间复杂度内完成，得到 $100$ 分。