HDUOJ 3037 - Saving Beans

题面

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

数据范围

1n,m1091 \le n, m \le 10^9

1p1051 \le p \le 10^5(保证 pp 为质数)

题目链接

分析

实际上这个问题可以转换为求下述方程解的个数:
x1+x2++xnm (xiN)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+n1n1)\binom{m + n - 1}{n - 1}
也就是:
(m+n1m)\binom{m + n - 1}{m}

这样一来,我们所要求的答案即:
(n10)+(1+n11)+(2+n12)++(m+n1m)\binom{n - 1}{0} + \binom{1 + n - 1}{1} + \binom{2 + n - 1}{2} + \dots +\binom{m + n - 1}{m}
我们联想到组合数的递推式:
(nm)=(n1m)+(n1m1)\binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1}

于是答案可化简为:
(n10)+(1+n11)+(2+n12)++(m+n1m)=(n0)+(n1)+(n+12)++(m+n1m)=(n+11)+(n+12)++(m+n1m)==(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 是质数时,对于任意整数 1mn1 \le m \le n 时有:
(nm)(nmodpmmodp)(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!(nm)!m!(n - m)! 每项的逆元,全部乘起来即可。复杂度 O(nlogn)\mathcal{O}(n\log{n})

实现

完整参考代码

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/05/26/hduoj-3037/