高效计算pow(a，nCr) %m

Question

我认为有一些过程来计算功率(a，nCr)%b？但是我想知道如何在编程中有效地解决这个问题？

Answer 1

我能想到一种方法，它只有~O(n^2*log(m))，并且不需要使用大整数。我有一个更快的方法(类似于O(k*log(m)*log(n)))的概念，如果你可以分解m，你可以分解一些k的totient(m/gcd(a^k,m))，但它会变得非常麻烦。

在任何情况下，对于O(n^2*log(m))方法，我们都将利用nCr == (n-1)C(r-1) + (n-1)Cr这一事实

下面是nCr的计算，它利用了这一点：

def nCr(n0,r0):
  memoized = {}

  def go(n,r):
    if r == 0 or r == n:
      return 1
    if (n,r) not in memoized:
      memoized[(n,r)] = go(n-1,r-1) + go(n-1,r)
    return memoized[(n,r)]

  return go(n0,r0)

您的powChooseMod函数的代码将几乎相同：

def powChooseMod(a,n0,r0,m):
  memoized = {}

  def go(n,r):
    if r == 0 or r == n:
      return a
    if (n,r) not in memoized:
      memoized[(n,r)] = go(n-1,r-1) * go(n-1,r) % m
    return memoized[(n,r)]

  return go(n0,r0)