首页 > 其他 > 详细

【BZOJ】2142 礼物

时间:2017-07-08 19:12:28      阅读:288      评论:0      收藏:0      [点我收藏+]

【算法】中国剩余定理+组合数取模(lucas)

【题意】给定n件物品分给m个人,每人分到wi件,求方案数%p。p不一定是素数。

【题解】

首先考虑n全排列然后按wi划分成m份,然后对于每份内都是全排列,除以wi!消除标号影响,注意剩余的(n-W)也视为一份。

所以ans=n!/(w1!w2!...wm!(n-W)!)%p

也可以从排列组合公式方面考虑,即

ans=C(n,w1)*C(n-w1,w2)*C(n-w1-w2,w3)*...*C(n-w1-w2-...-w_(m-1),wm) mod P

      =n!/w1!/w2!/.../wm! mod P (by POPOQQQ)

 

为了出p倍数

【BZOJ】2142 礼物

原文:http://www.cnblogs.com/onioncyc/p/7137642.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!