题面

凛冬将至，松鼠正忙于采取豆豆。它们从 nn 棵树上采取豆豆，但处于可持续性发展的考虑，它们一共最多采取 mm 粒豆豆。假设每棵树上都有无限多的豆豆，请计算采取的方案种数并将结果对质数 pp 取模。

数据范围：

1≤n,m≤1091 \le n, m \le 10^9

1≤p≤1051 \le p \le 10^5 （保证 pp 为质数）

题目链接

分析

实际上这个问题可以转换为求下述方程解的个数：

x1+x2+⋯+xn≤m (xi∈N) x_1 + x_2 + \dots + x_n \leq m \ (x_i \in N)

我们首先考虑等于 mm 的时候解的个数，不难考虑到使用隔板法。由于每个 xix_i 都可以取 00 ，不妨对它们都加上 11 使其取值范围变为 [1,+∞)[1, +\infty) ：

x1+x2+⋯+xn=m⇒(x1+1)+(x2+1)+⋯+(xn+1)=m+n \begin{aligned} x_1 + x_2 + \dots + x_n & = m \\ \Rightarrow (x_1 + 1) + (x_2 + 1) + \dots + (x_n + 1) & = m + n \end{aligned}

于是我们就可以愉快地使用隔板法啦，其解的种数为：

(m+n−1n−1) \binom{m + n - 1}{n - 1}

也就是：

(m+n−1m) \binom{m + n - 1}{m}

这样一来，我们所要求的答案即：

(n−10)+(1+n−11)+(2+n−12)+⋯+(m+n−1m) \binom{n - 1}{0} + \binom{1 + n - 1}{1} + \binom{2 + n - 1}{2} + \dots +\binom{m + n - 1}{m}

我们联想到组合数的递推式：

(nm)=(n−1m)+(n−1m−1) \binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1}

于是答案可化简为：

(n−10)+(1+n−11)+(2+n−12)+⋯+(m+n−1m)=(n0)+(n1)+(n+12)+⋯+(m+n−1m)=(n+11)+(n+12)+⋯+(m+n−1m)=…=(m+nm) \begin{aligned} & \binom{n - 1}{0} + \binom{1 + n - 1}{1} + \binom{2 + n - 1}{2} + \dots + \binom{m + n - 1}{m} \\ & = \binom{n}{0} + \binom{n}{1} + \binom{n + 1}{2} + \dots + \binom{m + n - 1}{m} \\ & = \binom{n + 1}{1} + \binom{n + 1}{2} + \dots + \binom{m + n - 1}{m} \\ & = \dots \\ & = \binom{m + n} {m} \end{aligned}

具体求解的时候考虑使用 Lucas 定理， 即当 pp 是质数时，对于任意整数 1≤m≤n1 \le m \le n 时有：

(nm)≡(n mod pm mod p)⋅(n/pm/p)(modp) \binom{n}{m} \equiv \binom{n \bmod p}{m \bmod p} \cdot \binom{n \left.\right/ p}{m \left.\right/ p} \pmod{p}

同时在计算大组合数取模的时候，可先计算分子 n!n! 再计算分母 m!(n−m)!m!(n - m)! 每项的逆元，全部乘起来即可。复杂度 O(nlog⁡n)\mathcal{O}(n\log{n}) 。

实现

完整参考代码