固定 $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$ 分。