exLucas

# 【模板】扩展卢卡斯定理/exLucas ## 题目背景 这是一道模板题。 ## 题目描述 求 $${\mathrm{C}}_n^m \bmod{p}$$ 其中 $\mathrm{C}$ 为组合数。 ## 输入格式 一行三个整数 $n,m,p$ ，含义由题所述。 ## 输出格式 一行一个整数，表示 ......

0x00 前言 Lucas 定理适用于求在模 p 意义下的组合数（p 是质数）。此时， p 一般不大，但 n,m 很大，这样无法通过常规的方法预处理（一是空间可能开不下，二是如果 m>p ，则 n-m 和 m 不一定有逆元）。 当然你可以用杨辉三角递推，但这是 $\text{O}(n^2)$ 的。 ......