关于lucas定律解决大组合数取模问题,求救!我不想要复杂的证明过程,我想知道怎么使用.lucas定律：求C（n,m)%p(p是素数）,即将m转化为p进制,每一位数是m0,m1..,n也转化为p进制,n0,n1...然后求C（n0

Question

关于lucas定律解决大组合数取模问题,求救!
我不想要复杂的证明过程,我想知道怎么使用.
lucas定律：求C（ n,m )%p (p是素数）,即将m转化为p进制,每一位数是m0,m1..,n也转化为p进制,n0,n1...
然后求C（n0,m0)*C(n1,m1)*.%p.
然后到了这里我还是看不懂,如果出现m0>n0怎么办,如果转化成p进制后数量不相等怎么办?比如求C(100,50)%17,可写成C(15,16)*C(5,2)%17,可是这里16大于15,怎么办?比如求C（10000,50）%17,10000变成17进制数有4个数字4,10,0,2,但是50才两个怎么办?还有lucas定律说p大概不可超过100000,但是就算p为20000,我们还是可能面临不小的组合数,比如如何求C（900,300）%10007（假设素数）.

Answer 1

C(15,16)=0 对于n