题意
设 \(f_{n, m}\) 表示 \(m\) 维空间能被 \(n\) 个 \(m - 1\) 维空间划分的最大区域数。
求 \(\sum_{i = 0} ^ m f_{n, i}\)
\(n, m \le 10 ^ {18}, p \le 2 \times 10 ^ 7\)
Sol
注意到：\(f_{n, m} = f_{n - 1, m - 1} + f_{n - 1, m}\)。
不难想到 \(f\) 应该是组合数的前缀和。
集中注意力：$$f_{n, m} = \sum_{i = 0} ^ {m} \dbinom{n}{i}$$
所以：
\[\begin{align*} \sum_{i = 0} ^ {m} f_{n, i} &= \sum_{i = 0} ^ {n} \sum_{j = 0} ^ {m} \dbinom{i}{j} \end{align*}\]考虑合并上指标。
\[\begin{align*} \sum_{i = 0} ^ {m} f_{n, i} &= \sum_{i = 0} ^ {n} \sum_{j = 0} ^ {m} \dbinom{i}{j}\\ &= (\sum_{j = 0} ^ {m + 1} \dbinom{n + 1}{j}) - 1 \end{align*}\]注意到 \(p\) 很小，使用Lucas 定理。
\[\begin{align*} \sum_{i = 0} ^ {m} \dbinom{n}{i} &= \sum_{i = 0} ^ {m} \dbinom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{i}{p} \rfloor} \dbinom{n \mod p}{i \mod p} \end{align*}\]考虑枚举余数，右边会多一坨出来，单独加上就行。
\[= \sum_{i = 0} ^ {p - 1} \dbinom{n \mod p}{i} \sum_{j = 0} ^ {\lfloor \frac{m}{p} \rfloor - 1} \dbinom{\lfloor \frac{n}{p} \rfloor}{j} + \dbinom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor} \sum_{i = 0} ^ {m \mod p} \dbinom{n \mod p}{i} \]注意到中间有个：\(\sum_{j = 0} ^ {\lfloor \frac{m}{p} \rfloor - 1} \dbinom{\lfloor \frac{n}{p} \rfloor}{j}\)，这就是不就我们要求的原式吗。
直接递归求解即可。
复杂度：\(O(p \log_{p} n)\)
标签：lfloor,LY1169,frac,dbinom,省选,sum,20230328,rfloor,align From： https://www.cnblogs.com/cxqghzj/p/18083150