萌新第一次组织活动，在这里，我首先要感谢 UOJ 的各管理员的付出，感谢各位出题人和选手的参与。

那是在 2020 年 12 月中旬，我的集训队论文才刚刚动笔。写下标题——《#TBA》命题报告。仿着学长 wzt 的命题报告的格式，摘要的第一句话是：“《#TBA》是我为 2021 年集训队互测命制的一道试题。”——等等，互测呢？！

不过考虑到命题报告的明显优势，我选择保持原计划不变。这时我想到，队友 Lagoon 的论文也是命题报告，他的题也没处放。于是我找他商量：要不要办一个比赛放论文题？

两题肯定是不够。不过我想，再团结至少一个人来办起一场比赛，还是不难的。我先获得了集训队教练的批准，然后与 UOJ 取得了联系，开始拉群、发广告、造题。

我们的出题人队伍只有 5 人，Round #1 很顺利地办成之后，我才意识到 Round #2 可能只有两题了。在群里连着两天发广告无人响应，在第三天，我开始对着候选队员名单挨家挨户地征集，却颗粒无收。这期间，zhouzhendong 和 p_b_p_b 先后响应，可惜来稿均被识别出原题，只能作罢。正当此时，幸亏 rushcheyo 站出来，贡献了一道签到题：一番抢救，Round #2 至少成为了一场完整的比赛。

再次地，感谢出题人 EntropyIncreaser, Itst, Lagoon, shiliangzhi, rushcheyo 支持并响应本次活动，贡献了宝贵的一题。

感谢 UOJ 承办本次活动，感谢站长 vfleaking、管理员 mayaohua, rushcheyo, skip2004 的辛勤工作，是他们保障了本次活动顺利举行。值得一提的是，外联大师 rushcheyo 还邀请了国外选手来参赛。

感谢各位选手与我们出题人交流。既然是“互测”，那我们出题人出题目、各位选手解题目，就不是为了选拔选手，而是与选手以攻防战的形式交流。以我命的题《太阳神的宴会》为例，本来我欠思考，武断地认为后缀数组根本做不了，在论文中写：“这种计数问题只能用自动机来表示，痛击了后缀数组的弱点”。所幸，我聆听 djq_cpp, jiangly 等选手的赛后讨论，开始意识到错误。后来 zx2003 提了一个基于后缀数组的做法，时间复杂度是对的，可惜给卡了常数，止步于 81 分（这份代码的提交者是 3002xz）。我的论文中这处严重错误的纠正，离不开各位选手的帮助。

至此，本萌新组织的第一次活动，落下了帷幕。相关题目的资料可能还有不完善的，会尽快补全，维持我们 UOJ 题库的高质量。祝 UOJ 越办越好。

萌新第一次发博，不知道和出题人的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)$.