题解：P10380 「ALFR Round 1」D 小山的元力

· · 题解

同样，对于第一档部分分，直接暴力即可。

正解

既然需要求出每一种分法所贡献的值，不妨求出每一堆所贡献的值。

先考虑第一堆。

显然，可以考虑枚举第一堆的元素数量，即将 i 从 0 枚举到 n，其中 i=0 的情况可以省略。当第一堆的元素数量确定时，它所产生的贡献与方案数有关。

这里的方案数值的是：当第一堆的元素数量为 i 时，总共有多少种分法。

假设有 x 中分法，那么此时所产生的贡献即为：i×x。

关键在于如何求 x。

由于第一堆的数量已经确定，所以可以转换为这个问题：求将 n−i 个元素分为 m−1 堆的方案数。

这个问题可以用隔板法解决，方案数即为：C^{m-2}_{n-i+m-2}。

第一堆考虑完毕后，在考虑其他堆。

拿第二堆举例，第二堆的元素数量 i 也可以从 0 枚举到 n，且确定第二堆的元素数量后，方案数也为 C{m-2}_{n-i+m-2}。唯一与第一堆不同的是，它所产生的贡献为 2×i×x，

同理，第三堆所产生的贡献即为：$6×i×x$。 依此类推，可以用递推的方法求出每一堆所产生的贡献。 注意特判 $m=1$ 的情况。