当前位置: 首页 > news >正文

SCP/NOIP 复习:插板法

自己写一遍插板法的东西,顺便补上 oiwiki 上没有的一个证明。

偏向整理,别人估计不知道我在干什么。

基本模型:\(x_0+x_1+...+x_k=n\) 的正整数或非负整数解数量,可以抽象为元素组的划分。

正整数解的数量

也是插板法最基本的模型。

\(n\)相同的元素,将它们分成 \(k\) 组,并且要求每组不是空的,求统共有多少种分配方法。

注意是元素相同组别不同。

为什么标粗相同的元素?不相同就不能用插班法了,插班法依赖于元素的不可区分性。

我们将这个问题视作把 \(k-1\) 个隔板放入 \(n-1\) 个空隙之间。

也就是 \(\binom{n-1}{k-1}\)

问题等同于求解 \(x_0+x_1+...+x_k=n\) 的正整数解数量。

这里的 \(x_i\) 表示 \(i\) 组的个数。

非负整数解的数量

现在去掉限制每组不是空,也就是允许每组是空的。

由于元素的等同的,我们可以先添加 \(k\) 个元素,再进行上述插班法,最后再抽去我们添加的元素。

得到答案 \(\binom{n+k-1}{k-1}\)=\(\binom{n+k-1}{n}\)

问题等同于求解 \(x_0+x_1+...+x_k=n\) 的非负整数解数量。

以上便是基本的两大模型,我们遇到问题可以试着转化模型。

下界不同的整数解的数量

我们规定对于第 \(i\) 组必须至少要分配到 \(a_i\) 个元素。

这个时候我们选择转化成数学模型,问题变复杂时我们不能总是依赖直观。

我们设 \(x_i\) 为每组的个数,尝试转化成我们熟悉的数学模型。

\(x_0+x_1+...+x_k=n\)

\(x_i'=x_i-a_i\),这个样子我们就可以转化成以下东西。

\(x_0'+x_1'+...+x_k'=n - \sum a_i\)

其中 \(x_i\) 必须是非负整数。

这不就转化成之前的问题了。

答案自然是 \(\binom{n-\sum a_i +k-1}{n-\sum a_i}\)

不相邻的排列数量

\(1到n\) 的自然数可以选(一个排列),我们需要选择 \(k\) 个数,使得这些数在大小上互相不相邻,请问有多少种选法。

这个看似不太可以使用插板法分析,明明元素之间并不是相同的。

但是我们发现两个离得最近的被选择的数之间的大小差异是相同的。

我们考虑如下转化。

\(x_i\) 为比 \(x\) 小的最大数与 \(x\) 中间的没有被选的数量,\(miao\) 表示比 \(k\) 大的没有被选的数量。

这个样子我们可以列出来式子 \(x_1+x_2+...+x_k+miao=n-k\)

其中 \(x_1 \ge 0\),其他 \(x_i \ge 1\)\(miao\ge 0\)

这个样子就成了之前的老问题。

我们转化一下,仿照上边的思路。

\(x_1'=x_1+1\)\(miao'=miao+1\)

这样就成了第二个问题。

\(x_1'+x_2+...+x_k+miao'=n-k+2\)

\(x_i,miao\) 都是非负整数。

直接套刚才式子得出答案是 \(\binom{n-k+1}{k}\)

为什么不是 \(k-1\)\(miao\) 也是元素啊。

简单的例题 P2638

复习玩排列组合正好写到一道,遂补上去。

一共有 \(n\) 个储存区,储存区里边可以放任意多 0 和 1,当然,也可以什么都不放。

我们的 0 和 1 的总数量是有限的,放的时候并不一定要放完才行。

0 一共有 \(a\) 个,1 一共有 \(b\) 个。

询问一共有多少种方法。

我一开始并没有思路,于是尝试将问题转化为数学模型来分析。

一转化出来就知道怎么做了。

\(x_i\) 表示 \(i\) 格子中的 0 个数

\(y_i\) 表示 \(i\) 格子中的 1 个数。

枚举使用了 \(i\) 个 0,\(j\) 个 1。

我们得到数学问题,分别求以下的非负整数解个数。

\(x_1+...+x_n=i\)

\(y_1+...+y_n=j\)

因为两个互不影响,所以把答案乘起来就行了,怎么算我就不多说了,和上边显然是一样的。

形式化就是求解 \(\sum_{i=0}^{a}\sum_{j=0}^{b}\binom{i+n-1}{i}\times\binom{j+n-1}{j}\)

有个神经病的 hack 需要 __int128 才可以通过。

代码↓

#include <bits/stdc++.h>
#define int __int128
using namespace std;
const int MN=51;
int C[MN][MN], ans=0;
void Pre(){for(int i=0; i<MN; ++i){for(int j=0; j<=i; ++j){if(!j) C[i][j]=1;else C[i][j]=C[i-1][j]+C[i-1][j-1];}}
}
int n, a, b;
inline void Read(int &n){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}n=x*f;
}
inline void print(int n){if(n<0){putchar('-');n*=-1;}if(n>9) print(n/10);putchar(n%10+'0');
}
signed main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);Pre(); Read(n), Read(a), Read(b);for(int i=0; i<=a; ++i){for(int j=0; j<=b; ++j){ans+=C[i+n-1][i]*C[j+n-1][j];}}print(ans);return 0;
}
http://www.hskmm.com/?act=detail&tid=29591

相关文章:

  • 内存泄漏与SWAP
  • 今天开通自己的博客啦,加油加油!成为合格的牛马! - Irving11
  • 2025安全光栅厂家最新权威推荐榜:精准防护与高效性能的工业
  • 分块学习笔记
  • 2025年10月精加工车间恒温恒湿系统厂家推荐:精准控温与高效节能首
  • 977. 有序数组的平方 双指针
  • 完整教程:iSCSI服务器
  • 深入解析:数据库视图:虚拟表的强大应用
  • agc001_c题解
  • 【IMU】6轴数据校准算法
  • 2025 年 MES 服务商 TOP 平台机构推荐排行榜,mes 系统 /mes 软件 /mes 制造执行系统 /mes 生产制造执行系统 /mes 生产管理系统公司推荐
  • 2025 年10月 WMS 服务商最新推荐榜单,wms系统 wms软件,wms仓库管理软件,wms仓库管理系统软件公司推荐
  • 【仿生机器人】核心采购清单 (仿生机器人头方案)
  • CF数据结构题做题记录-1
  • 完整教程:安宝特产品丨FME Realize:重构数据与现实的边界,让空间计算赋能现场决策
  • 尝试对音频功率放大器芯片的噪声基底特性进行测量与计算:以纳芯威NS4268为例
  • 3.1 策略梯度方法(Policy Gradient Methods)
  • perl语言中的三目运算符和do代码块
  • CCPC2023女生专场 游记(VP)
  • 2.5 分布式学习(Distributed Learning)
  • 心得:刷算法的痛点-只根据题目的case思考,不考虑边界情况,写出一坨shit
  • OI 数论 1
  • 2.4 DQN 变体(Rainbow)
  • Emacs折腾日记(三十二)——org mode的基本美化
  • 2025 工业风机十大品牌全景解析报告:覆盖离心风机,防爆风机,矿用风机的最新推荐
  • 2.3 深度 Q 网络(Deep Q-Network, DQN)
  • Linux存储媒介devmount
  • Linux系统目录(文件)结构
  • 实用指南:如何读懂Mach-O:构建macOS和iOS应用安全的第一道认知防线
  • vim配置使用