隔板法

Published: December 20, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 隔板法

隔板法

对于n个非负变量$x_1,x_2,\ldots,x_n$，问满足下面等式的分配方案有多少种：

$$x_1+x_2+\ldots+x_n=m$$

这等价于m个小球，我们向其中插入$n-1$个挡板，将其切分为n部分的方案数，因此我们可以直接得出方案数为：

$${m+n-1 \choose n-1}$$

现在考虑满足下面不等式的分配方案有多少种：

$$L\leq x_1+x_2+\ldots+x_n\leq R$$

我们现在进行推导：

$$\begin{aligned} &\sum_{i=L}^R{i+n-1\choose i}\\ =&\sum_{i=L}^R{i+n-1\choose i}+{L+n-1\choose L-1}-{L+n-1\choose L-1}\\ =&\sum_{i=L+1}^R{i+n-1\choose i}+{L+n-1\choose L}+{L+n-1\choose L-1}-{L+n-1\choose L-1}\\ =&\sum_{i=L+1}^R{i+n-1\choose i}+{L+n\choose L}-{L+n-1\choose L-1}\\ \ldots\\ =&{R+n\choose R}-{L+n-1\choose L-1} \end{aligned}$$

现在考虑一个更简单的不等式的分配方案：

$$x_1+x_2+\ldots+x_n\leq m$$

进行推导：

$$\begin{aligned} &\sum_{i=0}^m{i+n-1\choose i}\\ =&\sum_{i=1}^m{i+n-1\choose i}+1\\ =&{m+n\choose m}-{n\choose 0}+1\\ =&{m+n\choose m} \end{aligned}$$

其实这个问题也等价于下面等式成立的前提下，前n个变量有多少种分配方案。

$$x_1+x_2+\ldots+x_n+x_{n+1}=m$$

由于前n个变量唯一决定变量$x_{n+1}$，因此等于等式的总分配数。

题目1：考虑所有非负整数变量$x_1,\ldots,x_n$的赋值方案，要求满足$x_1+\ldots+x_n=m$。考虑某个赋值方案，记任意一个下标集合$A$，定义这个下标集合的权重为$w(A)=\prod_{i\in A}x_i$。现在要求求对于所有大小为$k$的下标集合，计算所有方案下它们权重的总和。

由于这些变量仅仅指标不同，因此对于两个大小均为$k$的下标集合，它们在所有方案下权重之和应该是相同的。于是乎我们要考虑在所有方案下，$\prod_{1\leq i\leq k}x_i$的值的和，最后乘上${n\choose k}$就是我们要求的结果了。

现在考虑怎么计算$\prod_{1\leq i\leq k}x_i$，DP当然可以，但是时间复杂度为$O(n^2)$。也可以用生成函数，但是有点复杂，而且时间复杂度也好不到哪里去。

这个问题实际上有$O(1)$的做法（不考虑预处理$O(n)$时间）。非常简单，这个问题等价于将一个长度为$m$个线段分解为$n$个长度为整数的线段，且前$k$个线段需要从中间某个整数位置（不能和左边界重合）再选择一个中间点，问最终有多少不同的方案（长度为$L$的线段，选择中间点有$L$种可能）。而这个问题等价于直接将原序列拆分成$n+k$段，其中特定的$k$段不能为空。这个可以通过隔板法解决，即${n+m-1 \choose n+k-1}$。

题目2：考虑这样一个问题，有$n$个非负偶数$x_1,\ldots,x_n$和$m$个非负奇数$y_1,\ldots,y_m$，要求计算有多少种不同的赋值方案，满足$x_1+\ldots+x_n+y_1+\ldots+y_m\leq K$。将结果模上某个素数$p$。其中$0\leq n,m\leq 100$，$K\leq 10^{18}$。

我们额外加入一个非负变量$z$，因此问题要我们计算有多少不同的赋值方案，满足$x_1+\ldots+x_n+y_1+\ldots+y_m+z=K$。

一般的思路是用生成函数来求解，但是不好求解。

我们可以发现$n,m$非常小，因此我们可以考虑用动态规划来求解。记$dp(i,j)$表示前$j$个未知数总和为$i$的方案赋值数，那么我们可以用动态规划来求解，时间复杂度为$O((n+m)K)$。

但是仔细观察可以发现动态规划的递推公式是线性关系。即有$A\cdot dp(i,?)=dp(i+1,?)$，其中$A$是一个$R\times R$的矩阵，其中$R=401$。

于是问题的时间复杂度为$O(R^3\log_2K)$，过有些勉强。

这里可以考虑用BM算法来优化。我们可以用$O(R^2)$的时间复杂度搞出前面$2R$项，之后用BM算法推出最短递推公式。之后用多项式快速模$O(R^2\log_2K)$求解。

提供一道题目：https://atcoder.jp/contests/aising2020/tasks/aising2020_f。

题目3：给定$n$个非负整数$a_1,\ldots,a_n$，记非负整数序列$b_1,\ldots,b_n$合法当且仅当它们的和不超过$m$。现在希望对所有可能的$b$序列，计算下式：$\prod_{i=1}^n{b_i\choose a_i}$，并输出它们的和。

仔细观察，问题实际上要我们将$m$个排序的球分成$n+1$段，之后第$i$段球取$a_i$个球进行标记，其余球另外进行标记。问能产生多少不同的标记序列。

我们可以通过插入隔板的方式，先加入$n$个球，第$i$个球用于隔开第$i$和第$i+1$段。之后我们还需要总共从$m+n$个球中选择$n+\sum_{i=1}^na_i$个特殊的球进行标记，第一段为第$a_1+1$个标记的球左边部分，第二段为$a_1+1$个标记的球右边同时在第$a_1+a_2+2$个标记的球左边，其余类似。

所以总共可以产生的序列数目为${m+n\choose n+\sum_{i=1}^na_i}$。

提供一道题目。