同步自UOJ博客
不知道和出题人的Bonus做法是否相同。
有 $n$ 个数，初始都是 $0$, 每次随机一个小于 $a$ 的数将其加上 $1$, 当且仅当所有数都不小于 $b$ 时结束。求 $a$ 的个数的期望。输出期望模 $998\,244\,353$ 意义下的符号分数的值。
限制：$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)$.
提交时是速度第一名，后来被两个内存比我小很多的做法吊锤了，其中一个貌似复杂度是 $O(n^2b)$.
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。