c – 查找大n和k模m的二项式系数

发布时间：2020-12-16 10:01:29 所属栏目：百科来源：网络整理

导读：我想用以下约束计算nCk mod m： N’LT = 10 ^ 18 KLT = 10 ^ 5 m = 10 ^ 9 7 我读过这篇文章： Calculating Binomial Coefficient (nCk) for large n k 但是这里m的值是1009.因此使用卢卡斯定理,我们只需要计算1009 * 1009个不同的aCb值,其中a,b = 1009 如何

我想用以下约束计算nCk mod m：

N’LT = 10 ^ 18

K&LT = 10 ^ 5

m = 10 ^ 9 7

我读过这篇文章：

Calculating Binomial Coefficient (nCk) for large n & k

但是这里m的值是1009.因此使用卢卡斯定理,我们只需要计算1009 * 1009个不同的aCb值,其中a,b <= 1009 如何用上述约束来做到这一点.
我不能用给定的约束来制作O(m * k)空间复杂度的数组.

救命！

解决方法

只是使用这个事实

(n,k) = n! / k! / (n - k)! = n*(n-1)*...*(n-k+1)/[k*(k-1)*...*1]

所以你实际上只有2 * k = 2 * 10 ^ 5个因子.对于数字的倒数,您可以使用kfx的建议,因为您的m是素数.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!