题解 P2183 【[国家集训队]礼物】

2018-12-30 11:10:04


这题最多是紫题吧,式子我都能想出来qwq

前置姿势:扩展Lucas

不会的左转模板区

首先可以推出答案为 $\large C_{n}^{w_1}\times C_{n-w_1}^{w_2}\times... \mod P$

组合意义很明确,就是在剩下的礼物中选出 $w_i$ 个的方案数,再根据乘法原理乘起来。

显然我们要每步都对算出的组合数取模,但是这里的 $P$ 不一定是质数,所以直接上 $\color{red}{\text{扩展Lucas}}$ 即可。

细节见代码