[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

代码

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注