有效地以 m 为模的组合数量
Adi*_*hya 10 python algorithm math performance combinations
首先，我现在正在解决编程问题而不是数学问题。
问题是
安尼什（Anish）得到一枚无偏向的硬币，他将其扔了n次，然后他要求古拉布（Gourabh）计算所有j从0到n的正面朝上的所有可能结果的数量。由于可能的结果数量可能很大，因此他会以 m 为模给出值。需要明确的是，我们需要为 j 的每个值返回一个整数。
问题很简单，但是问题出现在时间限制上，为1.5秒，但输入n却大到200000。
我曾经math.comb计算过这些值，但运行时间超过了1.5秒。
那么，有没有什么方法可以更快地计算组合呢？
编辑#1：
输入示例：
2 998244353
示例输出：
1 2 1
编辑#2：
这是我尝试过的代码：
import math
n,m=input().split()
n = int(n)
m = int(m)
l = []
for i in range(n+1):
l.append(math.comb(n,i)%m)
print(*l)
PS：请告诉我这是否与本网站的主题无关，并建议一个合适的 SE 网站来发布此问题。提前致谢！这个问题来自两个月前结束的一场校际比赛。
这是原始问题：https://codeforces.com/gym/430360/problem/B（您需要一个帐户，第一次按照此处的“竞赛链接”进入）。
如果您无法查看问题，请查看下图。
由于您需要输出 all 的值j，因此您应该使用此生成函数：
如果j >= 1，那么C(n,j) = C(n,j-1) * (n+1-j) / j
通常，当提出此类问题时，模数m是大于 的素数n。这使得完成所有这些计算 mod 变得相对容易m，因为每个计算j都会有一个乘法逆元。
事实上，用非质数模数来问这个问题是非常不寻常的，我敢打赌 codeforces 问题描述只是没有提到它。我会尝试使用素模假设。
如果您使用的是 python 3.8 或更高版本，那么该语言中内置了一个模块化逆，您可以这样做：
def getBinomialCoefficientsMod(n,m):
result = [1]
for j in range(1,n+1):
result.append(( result[j-1] * (n+1-j) * pow(j,-1,m) )%m)
return result
编辑：嗯，事实证明这m并不总是一个足够大的素数，我不想让这个答案不完整，所以这里有一个适用于composite或small的版本m：
def getBinomialCoefficientsMod(n,m):
# get the prime factors of the modulus
facs=[]
fac=2
mleft = m
while fac*fac<=mleft:
if m%fac==0:
facs.append(fac)
while mleft%fac==0:
mleft//=fac
fac+=1
if mleft>1:
facs.append(mleft)
result = [1]
# factor of the last result that is relatively prime to m
rpresult = 1
# powers of the prime factors of m in the last result
exponents = [0]*len(facs)
for j in range(1,n+1):
p=1
num = n+1-j
den = j
# remove factors of the modulus from num and den,
# track their exponents, and get their product
for i in range(len(facs)):
fac = facs[i]
while num%fac==0:
exponents[i]+=1
num//=fac
while den%fac==0:
exponents[i]-=1
den//=fac
p = p*pow(fac,exponents[i],m)
rpresult = (rpresult * num * pow(den,-1,m)) % m
result.append(( rpresult * p )%m)
return result
使用通常的乘法公式根据前一个数字计算下一个数字，但保持数字较小。为了清楚起见，让我们首先看一个简单的版本。
\n幼稚的
\ndef naive(n, m):\n c = 1\n yield c\n for k in range(n):\n c = c * (n-k) // (k+1)\n yield c % m\n\nn, m = map(int, input().split())\nprint(*naive(n, m))\nn=200000 时大约需要 30 秒。因为c变得非常大，达到60204位（199991位）。而且如此大的数字的计算速度很慢。
\n快速地
\n我们不要天真地计算那些大的 c 并仅使用模 m 进行输出，而是让c 始终保持较小，以模 m 为模。在网站上被接受，花费了大约 0.68 秒。
\nfrom math import gcd\n\ndef fast(n, m):\n c = 1\n G = 1\n yield c\n for k in range(n):\n\n mul = n - k\n while (g := gcd(mul, m)) > 1:\n mul //= g\n G *= g\n\n div = k + 1\n while (g := gcd(div, m)) > 1:\n div //= g\n G //= g\n\n c = c * mul * pow(div, -1, m) % m\n yield c * G % m\n\nn, m = map(int, input().split())\nprint(*fast(n, m))\n乘法在模数下很好。如果只是这样的话c = c * (n-k)，我们就可以这么做c = c * (n-k) % m。
部门不允许这样做。因此，我们不是除以k+1，而是乘以它的倒数(k+1) -1模 m。某个数字 x 的倒数是数字 x -1，因此您得到 x\xc2\xb7x -1 = 1。例如，7 -1模 10 为 3。因为 7 和 3 相乘得到 21，即 1（模10）。
\n下一期：并非所有数字都有模 m 的倒数。例如，6 没有模 10 的逆元。您不能将 6 与任何整数相乘并得到 1（模 10）。因为 6 和 10 的公约数是 2。我们要做的就是尽可能多地反转 6。提取公约数 2，剩下 3。它确实有一个模 10 的倒数（即 7）。
\n因此，将与 m 共同的乘数/除数中的质因数提取到一个单独的数字 G 中。并用剩余的内容更新 c，模 m。然后将c和G组合起来输出。
\n我得到的粗糙时间为 n=200000，m=998244353 （问题中的大素数）：
\nnaive: 30.0 seconds\nfast: 1.0 seconds\nMatt\'s: 1.0 seconds\n对于n=200000，m=2*3*5*7*11*13*17*19*23：
\nnaive: 30.0 seconds\nfast: 1.2 seconds\nMatt\'s: 4.8 seconds\n我认为最坏的情况是具有许多素数的模数，例如 m=2*3*5*7*11*13*17*19*23，它最大化我的 G。当 n=200000 时，G 增长到 127 位。完全不用担心。
\n我在 Leetcode 上对类似问题的解决方案/解释。它的模数为 10，我对因子 2 和 5 进行了硬编码并对它们进行了计数，而不是像我在这里那样将它们乘以数字 G。也许我会用这个通用解决方案重新审视它......
\n