在网格上放置硬币的方法计数

Question

这个问题要求我们找出在一个N*M的网格上放置R个硬币的方式数量，使得每一行和每一列都至少有一个硬币。给定的限制条件是N，M < 200，R < N*M。我最初考虑使用回溯算法，但我意识到它永远不会在时间内完成。有人能指导我另外一种解决方案吗？（DP，封闭式公式）。任何提示都将不胜感激。谢谢。

- frodo

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) 

您需要评估N+1个不同的a值。

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

解释

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

a(m,n,r)是将r个硬币放在大小为m*n的网格上的方法数，使得每个m列都被占用，但并非所有行都必须被占用。

包含-排除将其转化为正确的答案。（思路是我们从a(M,N,R)中获得第一个估计值。这会高估正确答案，因为并非所有行都被占用，所以我们减去只占用N-1行的情况a(M,N-1,R)。然后这会低估，所以我们需要再次进行修正...）

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

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

- Peter de Rivaz

---

你可能需要解释一下如何使用二进制矩阵来解决一个问题，其中解决方案不一定涉及每个条目中仅有0或1个硬币。 - Dennis Meng

啊，我明白你的意思了。我们需要澄清在网格中单个方格上可以放置多少硬币。因为之前问题中的代码假设最多只能放置 1 枚硬币，所以我也是这样假设的。我会在问题中加入请求澄清的要求。 - Peter de Rivaz

如果这些条目确实是二进制的，那么我就不会费心尝试发布答案了；这比我想出来的任何东西都更简洁。 - Dennis Meng

等一下...我认为这解决了我的答案中的第四部分，将它们结合起来，我相信你应该能够解决它。 - Keldon Alleyne

Answer 2

这很困难，但如果你先计算出每行和每列至少有一枚硬币的方式数量（称为保留硬币），答案将是 #1 (n! / r! (n - r)!) * 的乘积，其中 #2 n = N*M - NUMBER_OF_RESERVE_COINS，#3 r = (R - NUMBER_OF_RESERVE_COINS)，对于 #4 每个保留一枚硬币的排列。

#4 是更棘手的部分。对于 N*M 其中 N!=M，abs(N-M) 告诉你单行/列上会有多少个保留硬币。我在确定下一步正确的处理方式方面遇到了麻烦，主要是由于时间不足（尽管我可以在周末回来），但我希望我提供的信息对你有用，并且如果我所说的是正确的，你将能够完成这个过程。

- Keldon Alleyne