模块化分区

Question

给定一个非负整数列表 a₀,a₁,a₂,. . . ,a_n和一个常量正整数m。我们想要生成 a'₀,a'₁,a'_{2 形式的所有非负整数列表},. . . ,a'_n 这样：

1. 存在一个i使得a_i≠a'_i.
2. 对于所有的i，我们有a_i ≥ a'_i
3. a₀ + a₁ + a₂ + 。 . . + a_n - a'₀ - a'₁ - a'₂ - 。 . . - a'_n 是 m
的倍数

就时间而言，java 的最佳算法是什么。我尝试了两种不同的方法。

1. 对于0和a_is之和之间的所有km：首先将km的所有分区生成为n个部分。对于这些分区中的每一个，从原始整数序列中按分量减去它。如果所有分量都是非负的，则结果列表有效。
2. 生成所有较小的位置并检查它们是否满足条件3。

令人惊讶的是，我的第二个想法比第一个想法快得多，但仍然相当慢。我应该如何处理这个问题？这个问题在本质上类似于 Generating the partitions of a number.

Answer 1

这可以在多项式时间内解决 O(nm²) 使用动态规划。

设f(i,r)为构建序列a'₀,a'[=108的方式数=]1, ..., a'_i 这样

(a₀ + a₁, ... + a_i - a '₀ - a'₁ - ... - a'_i) mod m = r.

第一个参数的选择很明显：我们将从左到右查看序列并记录序列前缀的结果。 第二个参数是我们到目前为止的余数 modulo m，因为为了构建所有可能的序列，我们必须考虑其间所有可能的余数，而不是只是零。

为了计算f (i, r)，我们需要考虑(a_i - a'_i) mod m 并使用之前计算的 f (i - 1, *) .

• If (a_i - a'_i) mod m = 0，还有u = [a_i / m] + 1 a'_i 的选择：这些是 a_i, a_i - m, a'_i - 2 m, ..., a'_i - u m。 所以，我们必须添加 ([a_i / m] + 1) * f (i - 1, r) 到我们的答案：对于长度为 i - 1 且总余数为 r 的每个可能答案，我们可以选择每个 [a _i / m] + a'_i 的 1 个可能值使得新的总余数序列也是 r.

• If (a_i - a'_i) mod m = m - 1,还有v = [(a_i - 1 ) / m] + 1 a'_i这样的选择：这些是a_i - 1, a_i - 1 - m, a'_i - 1 - 2 m , ..., a'_i - 1 - v m。 所以，我们必须添加 ([(a_i - 1) / m] + 1) * f (i - 1 , (r + m - 1) mod m) 我们的答案：对于长度为 i - 1[= 的每个可能答案162=] 总余数 (r + m - 1) mod m，我们可以选择每个 [(a_i - 1) / m] + a'_i 的 1 个可能值使得总余数新序列现在是 r.

• ...

• If (a_i - a'_i) mod m = 1,还有w = [(a_i - (m - 1)) / m] + a'_i的1个这样的选择：这些是a_i - (m - 1), a_i - (m - 1) - m, a'_i - (m - 1) - 2 m, ..., a'_i - (m - 1) - w m。 所以，我们必须添加 ([(a_i - (m - 1)) / m] + 1) * f (i - 1, (r + 1) mod m) 我们的答案：对于每个可能的答案长度 i - 1 总余数 (r + 1) mod m,我们可以选择每个 [(a_i - (m - 1)) / m] + a'_i 的 1 个可能值使得新序列的总余数现在为 r.

综上所述，

f (i, r) = 总和 {by s = 0 to m - 1} of ([(a_i - s) / m] + 1) * f (i - 1, (r + m - s) mod m).

我们对所有 i 和所有 r 都这样做。 基数将是 f (-1, 0) = 1 （有一个空序列，总余数为 0）和 f (-1, t) = 0 for t > 0（不存在总余数 > 0 的空序列）。 答案会是f(n,0)（序列数a'₀,a'₁, ..., a'_i 总余数为 0).

实施时，注意将整数除法舍入并取非负数 modulo：在接近 CPU 的语言中（如 C 或 C++ or even Java），整数默认情况下，除法和余数计算向零舍入，因此当我们分别需要 -1 和 1 时，-1 / 2 的整数结果将是 0 和 -1 mod 2 将是 -1。