萌新第一次发博，不知道和出题人的Bonus做法是否相同。提交时是速度第一名，后来被一个内存比我小很多的做法吊锤了。

题意简述

有 $n$ 个数，初始都是 $0$, 每次随机一个小于 $a$ 的数将其加上 $1$, 当且仅当所有数都不小于 $b$ 时结束。求 $a$ 的个数的期望。

限制：$n \le 250, 1 \le b < a \le 250$.

我的想法

最后一步操作一定是把 $b-1$ 变成 $b$. 我把这一步叫做终止操作。与终止操作对象相同的其余 $b-1$ 次操作叫做终止操作的相关操作。

考虑影响操作序列的取得概率的步骤，是把 $a-1$ 变成 $a$. 我把这一步叫做加满操作。与一个加满操作的对象相同的其余 $a-1$ 次操作叫做它的相关操作。

如果一个操作不属于终止操作、加满操作或是它们的相关操作，这个操作就叫做普通操作。

考虑按照时间加入加满操作，顺便维护其相关操作和在其之前的普通操作。有些操作可能是后续加满操作或终止操作的相关操作，但是在后续操作加进来之前，我们仍然把它视为普通操作。

记 $g(i, j)$ 表示放入前 $i$ 个加满操作，在第 $i$ 个加满操作之前有 $j$ 个普通操作，所有满足此情况的状态取得的概率和。

初值：$g(0, 0)=1$.

转移：设第 $i-1$ 个加满操作和第 $i$ 个加满操作之间有 $k$ 个操作，连带加满操作一共需要在概率中乘上 $(n-i+1)^{-k-1}$; 这个加满操作的对象有 $n-i+1$ 种可能性；在 $j+a-1$ 个普通操作中需要确定 $a-1$ 个第 $i$ 个加满操作的相关操作。于是转移为

$$g(i, j)=\sum_{k=0}^{j+a-1}\binom{j+a-1}{a-1}g(i-1, j+a-1-k)(n-i+1)^{-k}$$

最后还需要放入一个终止操作，和上述转移基本类似，只是把 $a$ 改成了 $b$. 假设结束时，放了 $i$ 个加满操作，还剩余 $j$ 个普通操作，所有如此的操作序列的概率和记为 $h(i, j)$.

接下来还剩下 $n-i-1$ 个最终落于区间 $[b, a)$ 内的整数。设 $f(i, j)$ 表示 $j$ 个普通操作分配给 $i$ 个对象，使得每个对象都操作了不少于 $b$ 次但少于 $a$ 次的方案数。

初值：$f(0, 0)=1$.

转移：$f(i, j)=\sum_{k=b}^{a-1}\binom jkf(i-1, j-k)$

所以所有含恰好 $i$ 个 $a$ 的终止态的概率之和是 $P_i=\sum_{j=0}^{na}f(n-i-1, j)h(i, j)$.

那么在操作已终止的前提下其概率就是 ${P_i \over \sum_{k=0}^{n-1}P_k}$. 答案即 $\sum_{i=0}^{n-1}iP_i$.

场上想到的优化

把 $f$ 写成生成函数的形式，有 $\sum_{j=0}^{na}{f(i, j) \over j!}x^j=\left(\sum_{k=b}^{a-1}{x^k \over k!}\right)^i$

把 $g$ 的转移也写成生成函数的形式，有 $g(i, j)=[x^{j+a-1}]\binom{j+a-1}{a-1}\left(\sum_{j=0}^{na}g(i-1, j)x^j\right)\left(\sum_{k=0}^{na}(n-i+1)^{-k}x^k\right)$

于是两个都用NTT算一算，复杂度 $O(n^2a\log(na))$, 常数巨大，只能拿 $70$ 分。

场后想到的优化

鬼知道我场上脑子里堆了多少铁锈。首先我们发现

$$\begin{align}g(i, j)&=[x^{j+a-1}]\binom{j+a-1}{a-1}\left(\sum_{j=0}^{na}g(i-1, j)x^j\right)\left(\sum_{k=0}^{na}(n-i+1)^{-k}x^k\right)\\&=[x^{j+a-1}]\binom{j+a-1}{a-1}\frac{\sum_{j=0}^{na}g(i-1, j)x^j}{1-{x \over n-i+1}}\end{align}$$

用暴力除，即可减少 $3n$ 次NTT（我场上的做法甚至比这多做了 $6n$ 次），估计就 A 了吧。

接下来的内容感谢 EntropyIncreaser 教育。

设 $F=\sum_{k=b}^{a-1}{x^k \over k!}$, 那么 $F'=F-G$, 其中 $G={x^{a-1} \over (a-1)!}-{x^{b-1} \over (b-1)!}$.

那么 $(F^i)'=iF^{i-1}F'=iF^i-iGF^{i-1}$, 移项可得 $F^i-{(F^i)' \over i}=GF^{i-1}$, 从高到低确定位即可。

于是整个做法的时间是 $O(n^2a)$, 空间由于需要完整保存 $f, g$ 其中任意一个，也为 $O(n^2a)$.