algorithm - 寻找可能具有巨大 n 和 k 值的 nCk

Question

首先这不是我的作业..我在练习过程中卡在了一个问题上。

我想计算这个表达式的值:ans=(2^huge)%p..

哪里:

huge=n1Ck1+ n2Ck2 +n3Ck3 ..... [n1,n2.. 可以大到 10^4 而 k1,k2.. 小于 10]

p=小于 2^32 的质数

我知道如何使用快速 right to left binary method 找出 (a^b)%p , 但我的问题是如何找到像 10000C9 这样的数字的组合 [nCk] 可以产生如此巨大的数字，然后在模幂方法中使用它 ??

Answer 1

因为 2^(p-1)==1 mod p，您可以对指数取模 p-1 进行所有计算。