记录一下，下文的除法非特殊注明都是向下取整。
求 \(F(n, k) = \sum_{i=0}^{k}\binom{n}{i}\pmod p\)。
首先使用卢卡斯定理。
\[\begin{aligned} &\sum_{i = 0}^{k}\binom{n}{i}\\ =&\sum_{i = 0}^{k}\binom{\frac{n}{p}}{\frac{i}{p}}\binom{n \bmod p}{i \bmod p}\\ =&\sum_{j=0}^{p-1}\binom{n \bmod p}{j}\sum_{i = 0}^{k}[i\bmod p=j]\binom{\frac{n}{p}}{\frac{i}{p}}\\ =&\sum_{j=0}^{p-1}\binom{n \bmod p}{j}\sum_{i = 0}^{\frac{k-j}{p}}\binom{\frac{n}{p}}{i}\\ =&\sum_{j=0}^{p-1}\binom{n \bmod p}{j}F(\frac{n}{p},\frac{k - j}{p})\\ \end{aligned}\]然后考虑 \(\dfrac{k - j}{p}\) 的取值，只有 \(\dfrac{k}{p}\) 和 \(\dfrac{k}{p}-1\) 两种，在 \(j\in [0,k \bmod p]\) 的时候取到 \(\dfrac{k}{p}\)，否则取到 \(\dfrac{k}{p}-1\)。
那么只需要计算两个即可，前面的预处理较小范围的组合数前缀和可以直接算。
时间复杂度 \(O(2^{\log_p n})\)。
注意到 \(F(n,k)=F(n,k-1)+\binom{n}{k}\)，这一步使用卢卡斯定理在 \(O(\log n)\) 的时间内求出可以做到 \(O(\log^2)\)。
标签：frac,前缀,组合,dfrac,sum,计算,binom,bmod,log From： https://www.cnblogs.com/z-t-rui/p/18236009