blocks|key|3773590|text|这很难，但如果你一开始就计算出每行和每列至少有一枚硬币的方法(称之为储备硬币)。答案将是#1+(n!+/+r!+(n+-+r)!)+*的乘积，其中#2+n+=+N*M+-+NUMBER_OF_RESERVE_COINS和#3+r+=+(R+-+NUMBER_OF_RESERVE_COINS)对应于#4，每行/列保留一枚硬币。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|3773591|#4是更棘手的事情发生的地方。对于N*M，其中N!=M，abs(N-M)将告诉您单行/列上将有多少个储备硬币。我在寻找下一步的正确方法时遇到了麻烦，主要是因为时间不够(虽然我可以在周末回到这里)，但我希望我已经为您提供了有用的信息，如果我所说的是正确的，您将能够完成这一过程。|3773592|entityMap^0|1B|K|24|X|35|X|0|S|8|0^^$0|@$1|2|3|4|5|6|7|J|8|@$9|K|A|L|B|C]|$9|M|A|N|B|C]|$9|O|A|P|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|Q|8|@$9|R|A|S|B|C]]|D|@]|E|$]]|$1|H|3|-4|5|6|7|T|8|@]|D|@]|E|$]]]|I|$]]

This is tough, but if you begin by working out how many ways you can have at least one coin on each row and column (call them reserve coins). The answer will be the product of #1 <code>(n! / r! (n - r)!) *</code>, where #2 <code>n = N*M - NUMBER_OF_RESERVE_COINS</code> and #3 <code>r = (R - NUMBER_OF_RESERVE_COINS)</code> for #4 each arrangement of reserving one coin on each row/column.

#4 is where the trickier stuff takes place. For N*M where N!=M, <code>abs(N-M)</code> tells you how many reserve coins will be on a single rows/columns. I'm having trouble on identifying the correct way of proceeding to the next step, mainly due to lack of time (though I can return to this on the weekend), but I hope I have provided you with useful information, and if what I have said is correct that you will be able to complete the process.

blocks|key|444271|text|回答|type|unstyled|depth|inlineStyleRanges|entityRanges|data|444272|根据OEIS+sequence+A055602的说法，一个可能的解决方案是：|offset|length|444273|Let+a(m,+n,+r)+=+Sum_{i=0..m}+(-1)%5Ei*binomial(m,+i)*binomial((m-i)*n,+r)

Answer+=+Sum_{i=0..N}+(-1)%5Ei*binomial(N,+i)*a(M,+N-i,+R)+|code-block|syntax|javascript|444274|您将需要计算N%2B1的不同值。|444275|假设您已经预先计算了二项式系数，则a的每次评估都是O(M)，因此总复杂度为O(NM)。|444276|释义|444277|该公式可以使用inclusion-exclusion+principle导出两次。|444278|a(m，n，r)是将r个硬币放在大小为m*n的网格上的方法的数量，使得m列中的每一列都被占用，但不是所有行都被占用。|444279|包含-排除将这个问题转化为正确的答案。(这个想法是我们从a(M，N，R)得到我们的第一个估计。这高估了正确的答案，因为不是所有的行都被占用了，所以我们减去只占用N-1行的情况a(M，N-1，R)。这就低估了，所以我们需要再次修正...)|444280|类似地，我们可以通过考虑b(m，n，r)来计算a(m，n，r)，b(m，n，r)是在网格上放置r个硬币的方式的数量，其中我们不关心行或列是否被占用。这可以简单地从选择网格大小为m*n的r个位置的方式的数量中导出，即二项式(m*n，r)。我们使用IE将其转换为函数a(m，n，r)，其中我们知道所有列都被占用。|444281|如果您希望每个正方形上的硬币数量有不同的条件，则只需将b(m，n，r)更改为适当的计数函数即可。|444282|entityMap|0|LINK|mutability|MUTABLE|url|http://oeis.org/A055602|1|http://en.wikipedia.org/wiki/Inclusion%25E2%2580%2593exclusion_principle^0|0|2|L|0|0|0|0|0|0|7|T|1|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1A|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1B|8|@]|9|@$D|1C|E|1D|1|1E]]|A|$]]|$1|F|3|G|5|H|7|1F|8|@]|9|@]|A|$I|J]]|$1|K|3|L|5|6|7|1G|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|1H|8|@]|9|@]|A|$]]|$1|O|3|P|5|6|7|1I|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1J|8|@]|9|@$D|1K|E|1L|1|1M]]|A|$]]|$1|S|3|T|5|6|7|1N|8|@]|9|@]|A|$]]|$1|U|3|V|5|6|7|1O|8|@]|9|@]|A|$]]|$1|W|3|X|5|6|7|1P|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|6|7|1Q|8|@]|9|@]|A|$]]|$1|10|3|-4|5|6|7|1R|8|@]|9|@]|A|$]]]|11|$12|$5|13|14|15|A|$16|17]]|18|$5|13|14|15|A|$16|19]]]]

<h2>Answer</h2>

According to <a href="http://oeis.org/A055602" rel="nofollow">OEIS sequence A055602</a> one possible solution to this is:

<pre><code>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) 
</code></pre>

You will need to evaluate N+1 different values for a.

Assuming you have precomputed binomial coefficients, each evaluation of a is O(M) so the total complexity is O(NM).

<h2>Interpretation</h2>

This formula can be derived using the <a href="http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle" rel="nofollow">inclusion-exclusion principle</a> twice.

a(m,n,r) is the number of ways of putting r coins on a grid of size m*n such that every one of the m columns is occupied, but not all the rows are necessarily occupied.

Inclusion-Exclusion turns this into the correct answer. (The idea is that we get our first estimate from a(M,N,R). This overestimates the correct answer because not all rows are occupied so we subtract cases a(M,N-1,R) where we only occupy N-1 rows. This then underestimates so we need to correct again...)

Similarly we can compute a(m,n,r) by considering b(m,n,r) which is the number of ways of placing r coins on a grid where we don't care about rows or columns being occupied. This can be derived simply from the number of ways of choosing r places in a grid size m*n , i.e. binomial(m*n,r). We use IE to turn this into the function a(m,n,r) where we know that all columns are occupied.

If you want to allow different conditions on the number of coins on each square, then you can just change b(m,n,r) to the appropriate counting function.

the problem requires us to find out the number of ways of placing R coins on a N*M grid such that each row and column has at least one coin. Constraints given are N , M &lt; 200 , R &lt; N*M. I initially thought of backtracking, but i was made to realise that it would never finish in time . Can someone guide me to another solution? (DP , closed form formula.) any pointers would be nice. Thanks.

Counting ways of placing coins on a grid

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

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

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

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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