C变态组合数C(n,m)求解
作者:baoer1024 / 发布于2012/6/25/ 585
问题:求解组合数C(n,m),即从n个相同物品中取出m个的方案数,由于结果可能非常大,对结果模10007即可。 方案1: 暴力求解,C(n,m)=n*(n-1)*...*(n-m+1)/m!,n<=15 方案2: 打表,C(n,m)=C(n-1,m-1)+C(n-1,m),n<=10,000 方案3: 质因数分解,C(n,m)=n!/(m!*(n-m)!),C(n,m)=p1a1-b1-c1p2a2-b2-c2…pkak-bk-ck,n<=10,000,000 方案4: Lucas定理,将m,n化为p进制,有:C(n,m)=C(n0,m0)*C(n1,m1)...(mod p),算一个不是很大的C(n,m)%p,p为素数,化为线性同余方程,用扩展的欧几里德定理求解,n在int范围内,修改一下可以满足long long范围内。
Copyright © 2004 - 2024 dezai.cn. All Rights Reserved 站长博客 粤ICP备13059550号-3