type
status
date
slug
summary
tags
category
icon
password
Email
文章首发于我的个人博客：欢迎大佬们来逛逛
隔板法
隔板法能够解决的问题：
- 求线性不定方程的解的组数
- 求相同元素分组的方案数
给我们 个球， 个盒子，要求把这些球放进这些盒子中，一共有多少种不同的放的方案数？
例如：
，方案如下：
容易看出，我们可以划分为 1 1 2 ; 1 2 1; 2 1 1 三种不同的方案。
我们可以把这个问题转换为这样的一个模型：
- 在 的条件下，求 的方程解的组数
即在这个问题中，方程的解的组数就是：
如何解决这个问题呢？
注意到我们总共有 个盒子，相当于我们有 块板子，然后把这两块板子放到不同的间隔方案数。
对于板子，我们有 块；对于间隔，我们有 个位置。
因此就是求： 的方案数
扩展
与前面不同，我们需要求在 的条件下，求 的方程解的组数
假设 ，那么
因此就可以转换为求： 的方法数
我们需要求在 的条件下，求 的方程解的组数
假设 ，那么
因此就可以转换为求： 的方案数
例题
- 首先求出 的值，作为
- 然后直接求对应的方案数：
- 对于如何处理这个组合数，我们使用求组合数的递推的方法，其中我们需要用到高精度加法来处理。
- 作者:Yuleo
- 链接:https://www.helloylh.com/article/16c6b131-3334-40aa-9ff2-4010c2358c6a
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。