algorithm - 计算将硬币放在网格上的方法

Question

该问题要求我们找出在 N*M 网格上放置 R 个硬币的方式的数量，使得每一行和每一列至少有一个硬币。给出的约束是 N , M < 200 , R < N*M。我最初想到回溯，但我意识到它永远不会及时完成。有人可以指导我找到另一个解决方案吗？ (DP，封闭式公式。)任何指针都会很好。谢谢。

Answer 1

回答

根据 OEIS sequence A055602一个可能的解决方案是:

Let a(m, n, r) = Sum_{i=0..m} (-1)^i*binomial(m, i)*binomial((m-i)*n, r)

Answer = Sum_{i=0..N} (-1)^i*binomial(N, i)*a(M, N-i, R) 

您需要计算 a 的 N+1 个不同值。

假设您已经预先计算了二项式系数，a 的每个评估都是 O(M)，因此总复杂度是 O(NM)。

解释

这个公式可以使用inclusion-exclusion principle推导出来两次。

a(m,n,r) 是将 r 个硬币放在大小为 m*n 的网格上的方式的数量，使得 m 列中的每一列都被占用，但不一定所有行都被占用。

包含-排除将其转化为正确答案。 (这个想法是我们从 a(M,N,R) 中得到我们的第一个估计。这高估了正确答案，因为不是所有的行都被占用所以我们减去只占用 N 的情况 a(M,N-1,R) -1 行。这会低估所以我们需要再次更正...)

类似地，我们可以通过考虑 b(m,n,r) 来计算 a(m,n,r)，这是将 r 个硬币放置在我们不关心行或列被占用的网格上的方法的数量.这可以简单地从在网格大小 m*n 中选择 r 个位置的方法的数量得出，即二项式 (m*n,r)。我们使用 IE 将其转换为函数 a(m,n,r)，我们知道所有列都已被占用。

如果您想对每个方 block 上的硬币数量允许不同的条件，那么您只需将 b(m,n,r) 更改为适当的计数函数即可。