DTOJ 4793. 通用测评号

本文主要是介绍DTOJ 4793. 通用测评号，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

完成清扫银河计划带来的信心并不能让跳蚤们的航天科技突飞猛进，你看不到任何用现有的工质发动机技术完成环银河系航行的可能性。但这时，章北蚤向你展示了最新的通用测评号恒星级宇宙飞船 —— 它拥有最新一代的工质发动机，全功率推进时，理论上可以加速到光速的千分之五。

为了实验通用测评号的实际效果，你被安排给通用测评号装填燃料。通用测评号上有 $n$ 个燃料舱，初始时均为空。一个燃料舱被填满时可以储藏 $a$ 单位的燃料。但为了完成本次实验，只需要每个燃料舱装填至少 $b$ 单位的燃料即可。

装填燃料是个非常无聊的事情，因此你每次会等概率随机选一个没有满的燃料舱，并且在其中放入 $1$ 单位的燃料，直至所有燃料舱均包含至少 $b$ 单位的燃料。

但是由于设计上的失误，一个燃料舱被填满 $a$ 单位的燃料后，该燃料舱与发动机连接的管道由于压力过大会坏掉。章北蚤发现了这个问题，他想估计坏掉的管道数量，所以想请你算一算期望有多少个燃料舱被填满了。

为了避免实数计算带来的浮点误差，你只需要输出答案对 $998244353$ 取模后的结果。

测试点编号	$n,a\le$	特殊性质
$1$	$5$	无
$2$	$10$	无
$3$	$30$	无
$4$	$50$	$b=1$
$5$	$50$	无
$6$	$100$	$b=1$
$7$	$100$	无
$8$	$150$	无
$9$	$200$	无
$10$	$250$	无

对于所有测试数据，满足 $1\le n\le 250,1\le b<a\le 250$。

题解

说一下我的劣质做法（被卡常了自闭了，为什么好不容易有个想法都不让人过啊）。

考虑用每一种情况的填满的燃料舱个数乘上它的概率计算出期望，而每一种情况相当于一个序列，为了方便把一种燃料舱看作一种颜色，这个序列即为$n$种颜色各自出现了$[a,b]$次，其中最后一个的颜色出现恰好$b$次的序列，它的贡献为出现了$a$次的颜色数。

注意到概率比较麻烦，每个位置的概率为$1/在它以及之前还未出现a次的颜色数$。首先枚举出现$a$次的颜色数，考虑先对剩下的出现$[a,b-1]$次的颜色计算排列的方案数，为了避免重复，我们按照每个颜色最后一次出现的位置从前往后排序，最后再乘上阶乘表示颜色可以交换，这个用一个简单的DP即可：$f[i][j]$为前$i$种颜色组成长度为$j$的序列的方案数，转移时枚举当前颜色的次数，乘上组合数即可。直接做的效率是$O(n^4)$的，显然可以用$ntt$优化到$O(n^{3}logn)$。

考虑对这个序列插入出现次数为$a$的颜色，并乘上概率就是答案。对于次数为$a$的那些颜色，还是按照最后一次出现的位置，为了方便计算，我们从后往前考虑，每次考虑插到哪个位置，后面的那些数的概率就知道了。这个再用一个DP计算即可：$g[i][j]$为长度为$i$的序列插入后后面的每个数概率为$1/j$的概率，枚举插入的位置即可（注意这里插入后面的数就直接删掉因为没用了，且为了保证顺序不能插到整个序列的末尾）。这里直接做的效率是$O(n^5)$的，显然可以用$ntt$优化到$O(n^{3}logn)$，由于这个$log$是$17$，又是$ntt$的，显然过不去并且不会优化自闭了。

这篇关于DTOJ 4793. 通用测评号的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---