求出给定集合的所有子集的最小公倍数之和

Question

给定: set (),with .A = {a0, a1, ..., aN-1}1 ≤ N ≤ 1002 ≤ ai ≤ 500

问:找到所有A大小至少为2的子集的所有最小公倍数(LCM)的总和.

一组的LCM 被定义为最小整数,使得对于所有.B = {b0, b1, ..., bk-1}Bminbi | Bmin0 ≤ i < k

例:

让N = 3与A = {2, 6, 7},则:

LCM({2, 6})      =    6
LCM({2, 7})      =   14
LCM({6, 7})      =   42
LCM({2, 6, 7})   =   42
----------------------- +
answer              104

天真的方法是简单地计算所有子集的最小公倍数,这对于相当大的不可行.O(2N)N

---

解决方案草图

问题来自竞赛^*,它也提供了解决方案草图.这是我的问题所在:我不明白暗示的方法.

该解决方案读取(模数一些小的固定语法问题):

解决方案有点棘手.如果我们仔细观察,我们会看到整数在2和之间500.因此,如果我们对数字进行素数分析,我们将获得以下最大权力:

 2 8  
 3 5
 5 3
 7 3
11 2
13 2
17 2
19 2

除此之外,所有质数都有幂1.因此,我们可以很容易地计算所有可能的状态,使用这些整数,离开9 * 6 * 4 * 4 * 3 * 3 * 3 * 3状态,这几乎是70000.对于其他整数我们可以像下面这样的DP: dp[70000][i],其中i可0到100.但是,dp[i]依赖于dp[i-1],所以dp[70000][2]就足够了.这留下了n * 70000可行的复杂性.

我有以下具体问题:

• 这些州是什么意思？
• 是否dp代表动态编程,如果是,那么正在解决哪些递归关系？
• 如何dp[i]计算dp[i-1]？
• 为什么大素数不会对国家数量有所贡献？它们中的每一个都发生一次0或1多次.是否应该2为每个素数乘以一个状态的数量(再次导致不可行的状态空间)？

_{^*可以从此来源找到原始问题描述(问题F).这个问题是该描述的简化版本.}

Answer 1

讨论

在阅读了实际的竞赛描述（第 10 页或第 11 页）和解决方案草图后，我不得不得出结论，解决方案草图的作者的写作相当不精确。

高级问题是计算如果通过公平抛硬币随机选择组件的预期寿命。这就是计算所有子集的 LCM 的原因——所有子集有效地代表了样本空间。您最终可能会得到任何可能的组件集。设备的故障时间基于设备的 LCM。因此，预期寿命是所有组的 LCM 的平均值。

请注意，这应该包括仅包含一项的集合的 LCM（在这种情况下，我们假设 LCM 是元素本身）。解决方案草图似乎是破坏性的，也许是因为他们以不太优雅的方式处理它。

这些状态是什么意思？

草图作者只使用了“状态”这个词两次，但显然设法改变了含义。在第一次使用“状态”这个词时，他们似乎正在讨论可能的组件选择。在第二次使用中，他们可能会谈论可能的故障时间。他们可能会混淆这个术语，因为他们的动态编程解决方案根据该词的一种使用来初始化值，而递归关系则源于另一种使用。

dp代表动态规划吗？

我想说要么是这样，要么是巧合，因为解决方案草图似乎很大程度上暗示了动态编程。

如果是这样，正在解决什么递归关系？如何根据 dp[i-1] 计算 dp[i]？

我能想到的是，在他们的解决方案中，状态 i代表失败时间，，T(i)并且已经计算了失败时间的次数，dp[i]。所得总和将是所有 的总和dp[i] * T(i)。

dp[i][0]那么将仅计算第一个组件的故障时间。dp[i][1]那么就是第一个和第二个组件的故障时间。dp[i][2]将是第一、第二和第三。ETC..

使用零进行初始化dp[i][0]，除了dp[T(c)][0]（其中c是考虑的第一个组件）应该为 1（因为到目前为止该组件的故障时间已被计算一次）。

dp[i][n]为dp[i][n-1]每个组件填充c：

• 对于每个i，复制dp[i][n-1]到dp[i][n].
• 加 1 到dp[T(c)][n].
• 对于每个i，添加dp[i][n-1]到dp[LCM(T(i), T(c))][n].

这是在做什么？假设您知道故障时间为j，但您添加了故障时间为 的组件k。无论您之前拥有什么组件，您新的失败时间都是LCM(j, k)。这是根据以下事实得出的：对于两个集合A和B，LCM(A union B} = LCM(LCM(A), LCM(B))。

同样，如果我们考虑的故障时间为T(i)，新组件的故障时间为T(c)，则最终的故障时间为LCM(T(i), T(c))。请注意，我们记录了配置的故障时间dp[i][n-1]，因此一旦引入新组件，我们应该记录许多新的故障时间。

为什么大素数对状态数没有贡献？

它们中的每一个都出现 0 次或 1 次。对于每个素数，状态数不应该乘以 2（再次导致不可行的状态空间）吗？

当然，你是对的。然而，解决方案草图指出，具有大素数的数字以另一种（未指定）方式处理。

如果我们确实将它们包括在内会发生什么？我们需要代表的州数量将激增至一个不切实际的数字。因此，作者对这些数字的解释不同。请注意，如果小于或等于 500 的数字包含大于 19 的质数，则其他因数乘以 21 或更少。这使得这些数字适合暴力破解，不需要表格。