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

Question

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

Answer 1

回答

根据OEIS 序列 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)。

解释

这个公式可以使用包含排除原理两次推导出来。

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)，我们知道所有列都被占用。

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

Answer 2

这很难，但如果你首先计算出每行和每列至少有一枚硬币（称为储备硬币）有多少种方法。答案将是 #1 的乘积(n! / r! (n - r)!) *，其中 #2n = N*M - NUMBER_OF_RESERVE_COINS和 #3r = (R - NUMBER_OF_RESERVE_COINS)表示 #4 的每一种安排，在每一行/列上保留一个硬币。

#4 是更棘手的事情发生的地方。对于 N*M，其中 N!=M，abs(N-M)告诉您单行/列上将有多少储备硬币。我无法确定进行下一步的正确方法，主要是因为时间不够（虽然我可以在周末回到这里），但我希望我已经为您提供了有用的信息，如果我说的是正确的，您将能够完成该过程。