algorithm - 解决方案数

Question

我被一个问题困住了，

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

其中 xi 是正整数，M 可以是 [1,6000000] 中的任何值。有多少unordered solutions with distinct xi's存在。我想知道这是否可以通过动态编程来完成（在给定的约束和内存限制内快速运行），或者我必须想出一个组合数学公式。
我要举报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 个，然后尝试获取一般论坛，如果您有时间，请证明它通过归纳），一旦你有了，你基本上就完成了。

重要提示：现在应该清楚了，我认为组合学方法比蛮力方法要好得多

Answer 2

您可以使用蛮力，只需创建一个向量（或其他动态容器）即可在您进行时推送解决方案。这不会是内存问题。但这需要很长时间才能处理。另一个想法是创建一个fstream，并定期刷新（每10000个解决方案）；