冒泡ioa
冒泡ioa

[JXOI2018]游戏 (组合数学)

题目链接

题解

我们称当一个数 k 除了它本身的因数不在这个序列里的时候, k 为特异数。

我们发现,当且仅当我们选完最后一个特异数的时候,整个数列被选完。

于是枚举每个位置为最后一个特异数的位置计算期望,答案为:

ans=\sum_{i=1}^{n} i\times sum\times C_{n-sum}^{n-i}\times (n-i)! \times (i-1)!

其中 i 为选花费, sum 为特异数的个数

求逆元的时候要线性推,要不然会T

代码

发表评论

textsms
account_circle
email

冒泡ioa

[JXOI2018]游戏 (组合数学)
题目链接 题解 我们称当一个数 $k$ 除了它本身的因数不在这个序列里的时候, $k$ 为特异数。 我们发现,当且仅当我们选完最后一个特异数的时候,整个数列被选完。 于是枚举每个位置…
扫描二维码继续阅读
2019-04-29