algorithm - 解决方案数量

Question

我遇到了一个问题，

  x1 + x2 + x3 +x4 +x5 + x6 < M

其中 xi 是正整数，M 可以是 [1,6000000] 中的任何值。存在多少个具有不同 xi 的无序解。我想知道这是否可以通过动态编程来完成(它在给定的约束和内存限制下快速运行)，或者我必须想出一个组合数学公式。
我必须报告 answer modulo 1000000007
PS:我不要解法

Answer 1

你不要完整的解决方案，我就不给你；我会尽力为您指明正确的方向。

首先，您需要将问题分解为更简单的问题。在您的情况下，这可以解决问题:

|(x_1,...x6) : sum(x_i) < M | = sum( |(x_1,...,x6) : sum(x_i) = N|)

对于 N=6,...,M-1 。现在，您只需要不同的解决方案，因此您可以假设:

x_1 <= x_2 <= ... <= x_6

现在，计算可以使 k 元素总和为 N 的方法的数量并不难(首先尝试使用 2 个元素，而不是 3 个，然后尝试获得一般的 forumla，如果您有时间，请通过归纳法证明它)，一旦有了，您就基本上完成了。

重要说明:现在应该很清楚了，我认为组合数学方法比蛮力方法好得多