[BZOJ2751] [HAOI2012] 容易题

题目

题目链接
题目大意为有一个数列 \{a_n\}, 每一项可以取值为 [1, n], 并且有一些限制某一项不能取某一个数。求所有可能的数列的积的和。

 

思路

首先我们可以得知结果为 \prod_{i=1}^{m} \sum_{feasible\ j} j
\prod_{i=1}^{m}(\frac{n(n+1)}{2}\ -\ \sum_{unfeasible\ j} j)
然而 m 非常大,所以我们可以从 k 入手。因为 k 非常小,意味着有限制的项数非常小,我们可以将限制排序,然后处理出限制项的贡献,其他没有限制的用快速幂算出,最后相乘得到结果。

 

代码

 

完结

参考黄学长博客

发表评论

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