HBC234839[SCOI2009]最长距离,最短路,图论Gachapon题解

云中君算法基础篇 2023-11-15 01:26:02 37 0

想要成为编程高手？那就来试试全网最全C++题库，让您在练习中快速成长。

)，每次生成整数互不影响，请计算Snuke使用生成器的次数的期望值，把它取模 998244353 输出。

Snuke 发现一个随机数生成器，这个生成器可以生产 0 到 n-1 n−1 的整数。一个整数序列 a_0,a_1,...,a_{n-1} a ,a 1 ,...,a n−1 ，代表这些数被生成的概率。整数 i i ( 0le i le n-1 0≤i≤n−1) 被生成的概率是 frac{a_i}{s} s a i ( s=sum^{n-1}_{i=0}a_i s=∑ i=0 n−1 a i )。每次生成整数互不影响。现在Snuke重复使用生成器生成整数，直到满足：对于每个 i i ( 0le i le n-1 0≤i≤n−1)， i i 生成了 b_i b i 次。请计算Snuke使用生成器的次数的期望值，把它取模 998244353 输出。