隔板法
隔板法
对于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}$。
提供一道题目。