在Python中高效地查找r在0到n范围内的nCr值的程序

假设我们需要多次计算nCr的值。我们可以通过非常高效的方式解决这个问题。如果我们存储nCr的较小值，我们可以轻松地找到较高的值。所以，如果我们有n，则我们必须找到nC0到nCn的列表。如果答案太大，则返回模数10^9。

因此，如果输入类似于n = 6，则输出将是[1，6，15，20，15，6，1]。

要解决此问题，我们将遵循以下步骤 −

• 项目：=具有单个元素1的列表
• 对于r在1到n的范围内，执行以下操作
  • 将项目中的最后一个元素×(n-r+1)/r的下限插入到项目的末尾
  • 其中n是项目的大小，items[n-2]: = items[n-2] mod 10^9
• 返回项目

示例

让我们看一下以下实现，以便更好地理解-

def solve(n):
   items = [1]
   for r in range(1,n+1):
      items.append(items[-1]*(n-r+1)//r)
      items[-2] %= 10**9
   return items

n = 6
print(solve(n))

输入

6

输出

[1, 6, 15, 20, 15, 6, 1]