n最大为200000时，求高效计算组合数模m的方法

Anish抛掷无偏硬币n次，需计算j从0到n时，恰好出现j次正面的所有可能结果数（即组合数C(n,j)），结果对m取模后返回每个j对应的整数。n最大可达200000，时间限制1.5秒。使用math.comb循环计算会超时，需要更快的实现方式。

示例 #

• 输入：2 998244353
• 输出：1 2 1

原尝试代码 #

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)

优化方案 #

问题分析 #

循环调用math.comb(n,i)的时间复杂度为O(n²)，因为每次计算math.comb(n,i)需要O(min(i, n-i))的时间，当n=2e5时，总运算量会达到4e10级别，完全超出时间限制。必须使用O(n)时间复杂度的方法。

方案1：质数模下的阶乘+逆阶乘法（最常用） #

当m是质数时（如示例中的998244353），可以利用费马小定理计算逆元，通过预处理阶乘和逆阶乘数组快速计算所有组合数：

1. 预处理阶乘数组fact，fact[i] = i! mod m
2. 预处理逆阶乘数组inv_fact，利用费马小定理inv_fact[n] = pow(fact[n], m-2, m)，再逆推得到所有逆阶乘
3. 每个组合数C(n,k) = fact[n] * inv_fact[k] * inv_fact[n-k] mod m

代码实现：

n, m = map(int, input().split())
if m == 1:
    print(' '.join(['0'] * (n + 1)))
    exit()

# 预处理阶乘数组
fact = [1] * (n + 1)
for i in range(1, n + 1):
    fact[i] = fact[i-1] * i % m

# 预处理逆阶乘数组
inv_fact = [1] * (n + 1)
inv_fact[n] = pow(fact[n], m - 2, m)
for i in range(n-1, -1, -1):
    inv_fact[i] = inv_fact[i+1] * (i+1) % m

# 计算所有组合数
result = []
for k in range(n + 1):
    val = fact[n] * inv_fact[k] % m
    val = val * inv_fact[n - k] % m
    result.append(str(val))

print(' '.join(result))

方案2：通用递推法（支持任意m） #

利用组合数的递推公式C(n,k) = C(n,k-1) * (n - k + 1) // k，由于组合数必为整数，我们可以先计算精确值再取模（Python支持大整数运算）：

n, m = map(int, input().split())
result = [0] * (n + 1)
result[0] = 1

for k in range(1, n + 1):
    # 递推计算精确组合数，利用整数除法保证结果为整数
    result[k] = result[k-1] * (n - k + 1) // k

# 统一取模
result = [str(x % m) for x in result]
print(' '.join(result))

注意：当n=2e5时，中间的组合数会非常大（位数超6万），Python的大整数运算虽然能处理，但速度可能略慢于质数模的专用方法。

方案3：质因数分解+中国剩余定理（复杂m场景） #

如果m是合数且无法通过上述方法高效计算，可以分解m的质因数，分别计算每个质因数幂次下的组合数模值，再用中国剩余定理合并结果。该方法实现复杂，但适用于所有m的情况，此处不再展开具体代码。

内容的提问来源于stack exchange，提问作者Adithya