回 帖 发 新 帖 刷新版面

主题:组合数

Description 

从 n 本不同的书中,任取 m 本书的不同组合总数是多少? 

Input 

只有一行共有二个正整数:n m 
( 1 <= m < n <= 1000 ) 

Output 

只有一行且只有一个正整数:符合条件的组合总数

Sample Input 


5 3

Sample Output 


10

Source 

基础题
pascal做(我知道C(m,n),但是这个数据太大,得用高精度的)

回复列表 (共5个回复)

沙发

这个似乎没什么好办法,阶乘就用乘法乘法再乘法去解决好了,我没主意。

板凳

有一些可以约的

3 楼

就是用M!/(m-n)!/n!来做,高精度阶乘+高精度除法

4 楼

简化版:不用写高精度除法:(因为答案总是整数)
先把分子(即阶乘)每一项都因式分解,把每个因式都累加起来。譬如:
M=6,M!=1*2*3*4*5*6
4=2*2,6=2*3
所以:数组f:f[2]=4(表示总积中有四个2相乘,下同),f[3]=2,f[5]=1.
除法和乘法差不多,只是把分母(即阶乘)每一项都因式分解,把每个因式都从他相应的数组位置里减1而已。
最后来一次高精度乘法就OK了
PS:3楼的式子还能化简哦

5 楼

ls的也太麻烦了......
想要效率,四位四位去乘就可以了

我来回复

您尚未登录,请登录后再回复。点此登录或注册