<p>如果你看一下“尝试所有组合”暴力解决方案的时间复杂性,它等于<code>O((N choose K) * K) = O(K * N^K</code>),因为有<code>N choose K</code>种方法从<code>1 to N</code>中选择<code>K</code>个不同的整数,计算它们的和需要<code>K-1</code>个加法。除了<code>N</code>和<code>K</code>的极小值之外,这是天文数字上的大</p>
<p><strong>更好的解决方案:动态规划</strong></p>
<p>一个更快、更简单的解决方案是动态规划。我们可以把它写成一个3D动态规划问题:</p>
<pre class="lang-py prettyprint-override"><code>Let dp[i][j][r], 0 <= i <= N; 0 <= j <= K; 0 <= r < M
be the number of combinations of j ints from [1, 2, ..., i]
with sum congruent to r modulo M. We want dp[N][K][0]
dp[i][j][r] = 1 if i == j == r == 0
0 if i == 0 and (j /= 0 or r /= 0)
1 if j == 0 and r == 0
0 if j == 0 and r /= 0
dp[i-1][j][r] + dp[i-1][j-1][(r-i) % M] otherwise
</code></pre>
<p>公式中添加了很多边缘情况,但最重要的是最后一种情况:我们的动态编程子问题最多依赖于2个其他子问题,因此总运行时间是DP数组的大小:<code>O(nmk)</code>。下面是一个Python实现:</p>
<pre class="lang-py prettyprint-override"><code>def get_combinations_dp(max_part_size: int, total_num_parts: int, mod: int) -> int:
BIG_MOD = 10 ** 9 + 7
# Optimization if no partitions exist
if total_num_parts > max_part_size:
return 0
largest_sum = ((max_part_size * (max_part_size + 1) // 2)
- ((max_part_size - total_num_parts) *
(max_part_size - total_num_parts + 1) // 2))
# Optimization if largest partition sum still smaller than mod
if largest_sum < mod:
return 0
dp = [[0 for _ in range(mod)] for _ in range(total_num_parts + 1)]
dp[0][0] = 1
for curr_max_part in range(1, max_part_size + 1):
for curr_num_parts in reversed(range(0, total_num_parts)):
for rem in range(mod):
dp[curr_num_parts + 1][(rem + curr_max_part) % mod] += dp[curr_num_parts][rem]
dp[curr_num_parts + 1][(rem + curr_max_part) % mod] %= BIG_MOD
return dp[total_num_parts][0]
</code></pre>
<p>参数是<code>N, K, M</code>,重命名为<code>max_part_size, total_num_parts, mod</code>,如果没有分区,可以通过一些可选的预检查立即返回<code>0</code></p>
<p>现在,假设您想做得比<code>O(nmk)</code>更好。在这里,事情变得棘手。如果你想做得更好,我能想象的唯一方法就是找到这些分区的生成函数,并使用FFT或其他快速多项式乘法模<code>10**9 + 7</code>。首先,我建议使用math stackexchange上的<a href="https://math.stackexchange.com/questions/646705/counting-integer-partitions-of-n-into-exactly-k-distinct-parts-size-at-most-m">this thread</a>来研究如何做到这一点,这涉及到根据更为知名的分区号精确计算这些分区,其生成函数已经为人所知。即使如此,我也找不到任何关于生成函数是否具有短表示的内容,直接使用分区号并不能改善<code>O(nmk)</code>的复杂性</p>
<p><strong>使用组合数学</strong></p>
<p>如果您仍然想使用这种动态规划方法,可以使用组合数学进行一些小的修改,当<code>N</code>大于<code>M*K</code>时,组合数学可能会渐进地更快:它在时间<code>O((M*K)^2)</code>中运行,而时间不依赖于<code>N</code>。我们的想法是使用我们的DP公式,但是我们现在不是从<code>[1, ... N]</code>中选择K个不同的整数,而是从<code>[0, ... M-1]</code>中选择K个(可能重复的)剩余类</p>
<p>这是怎么回事?首先,我们需要计算<code>[1, ... N]</code>中有多少整数属于每个剩余类<code>i mod M</code>。打这个电话<code>R[i]</code>,换成<code>0 <= i < M</code>。你可以这样计算</p>
<pre><code>R[i] = floor(N/M) + (1 if 0 < i <= N%M else 0)
</code></pre>
<p>现在我们可以编写一个稍加修改的动态规划定义和公式:</p>
<pre class="lang-py prettyprint-override"><code>Let dp[i][j][r], 0 <= i <= M; 0 <= j <= K; 0 <= r < M
be the number of combinations with replacement of j ints from
residue classes [0, 1, ... i-1] with sum congruent to r modulo M.
We want dp[M][K][0]:
dp[i][j][r] = 1 if i == j == r == 0
0 if i == 0 and (j /= 0 or r /= 0)
0 if i < 0 or j < 0
F(i, j, r) otherwise
F(i, j, r) = Sum from p = 0 to min(R[i], j) of:
(R[i] choose p) * dp[i-1][j-p][(r - i*p) % M]
</code></pre>