algorithm - 找到可以具有巨大 n 和 k 值的 nCk

Question

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

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

在哪里：

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

p=小于 2^32 的素数

我知道如何使用快速从右到左的二进制方法找出 (a^b)%p ，但我的问题是如何找到像 10000C9 这样的数字的组合 [nCk] 会导致如此巨大的数字，然后再使用在模幂方法中？

Answer 1

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