问题引入

在一次歌唱比赛中，有三位竞选者。现有5位专业评审，每人有一票，而为了不让任何一人难堪，每位竞选者都至少会获得一票，问：一共有多少种票数的分配方法呢？

思考

那么该问题 应为 排列组合问题中 球同，盒不同 ， 不允许空盒 情况

数据范围较小时，可以把每种情况列举出来

例如保证每个人都有一张票，此时还剩2张票分给三个人 两张票 一人只能一张：C 3 2，两张票 一人只能两张：

C 3 1

数据范围较大时，这种就比较困难了

因此引入隔板法来优化解题思路

就是想办法将5张票分为3堆，一堆分给一个人

在5 张票之间（4个空隙）插入两个隔板，就是三堆 ： C 4 2

若将上述票数扩大为100，同理 100 张票分成三堆 ， 需要2个隔板，插在100张票之间（99个空）： C 99 2

这就是一般的隔板法（需保证各项都>=1）

将问题抽象化

把三位竞选者的票数分别为x，y，z，则有关系式 x + y + z = 5 , x , y , z >= 1

那么问题就转化为 x + y + z = n 的正整数解个数

隔板法的本质就是m元一次方程的正整数解个数

x1+x2+x3+…+xm = n :

将n分为n个1，将n个1分为m堆，一个元分一堆 ： C n-1 m-1

隔板法衍生问题

学校有10个推优名额分给1，2，3班，那么每个班级获得的推优名额数不小于班号的分法有几种？

将问题抽象化

设1，2，3班的名额分别为x , y , z ,则有 x + y + z = 10, 其中 x >= 1 , y >= 2 , z >= 3

• 一般的隔板法问题要求 堆中个数>=1

将问题转化为一般隔板法问题

设 u = y - 1 -> u >= 1

v = z - 2 -> v >= 1

x + u + v = 7

或者可以思考为

将每班的推优名额先固定为班号，因此剩下了4个名额，4个名额随机分给这三个班， 每个班多分的名额大于等于0，可以利用公式将该项优化为>=1,具体操作看总结

隔板法进阶问题

学校马上要举行校运会了，有众多志愿岗位需要被分配。但是负责老师临时有事现在由你来分配这些岗位。
现在有n个岗位，m位志愿者，每个岗位至少需要ai​个志愿者，你需要将志愿者分配到岗位上，并且可以有志愿者空闲下来作预备。
请你给出可能的分配情况总数。

​ 答案可能会很大，故需要对998,244,353取模。

​ 注：所有岗位需求志愿者的总和不超过志愿者的总和且志愿者间无差别。

1<=n<=1000,1<=ai<=m<=2000

通过一组样例来分析

3个岗位，每个岗位要求1，2，3人，一共10人

• 首先转化为一般隔板法问题，我们可以先将这些岗位上人填满，剩余的人随机分配至这些岗位

• 所以开设的岗位a=1,b=2,c=3, 这些岗位还需要a >= 0 , b >= 0 ,c >= 0 ，剩余4人

• 本题中说到你需要将志愿者分配到岗位上，并且可以有志愿者空闲下来作预备。

• 因此我们需要在多设置一个岗位，用来存空闲者（该岗位可以有人，也可以无人），但这个岗位首先是0，因此这个岗位x>=0

• 可列出隔板法方程 a + b + c + x = 4，（a,b,c,d>=0）

• 但此时a，b，c，d均>=0，不满足隔板法条件，进行优化

• 得出最终方程 aa + bb + cc + xx = 8 ，（aa,bb,cc,dd>=1

• 8个人分4个岗位，隔板法，C(7,3)

还有一种思路类似

• 将每个岗位留一个人，每个岗位上还需至少一个1才可以，此时剩余7个人
• 因此开设的岗位为a=0,b=1,c=2 这些岗位还需要 a >= 1, b >= 1 , c >= 1 人，剩余7人
• 可将该问题分为两部分：有空余人员和没有空余人员
• 无空余人员，a + b + c = 7 （a,b,c>=1）隔板法C(6,2)
• 有空余人员,开设空余岗位x(此时x>=1,因为x=0在无空余人员时考虑过了)，a + b + c + x = 7 （a,b,c,x>=1）（a,b,c>=1）
• 将上述两种情况相加即可

求组合数的方法有多种（dp递推求组合数，乘法逆元求组合数），具体可看数论模块写的代码实现

总结：

对于x1+x2+x3+…+xm = n

所有项x>=1（一般情况）

一般隔板法问题，直接用公式（n-1个间隙中插入m-1个隔板）C(n-1,m-1)

**如果某项x >= 1 + i **

用票数解释

可以理解为x至少1+i张票 ,因此我们可以先给它分i张票 ， 在进行隔板法给它分1或多张票的情况

x1+x2+x3+…+xm = n

如果x1 >= 1+i

因此我们可以设 xx1 =x1 - i ，xx1 >= 1, 同时等式右边也应减去i ： n=n-i

原式转化为xx1+x2+x3+…+xm = n - i

如果某项x >=0 （允许盒子为空情况）

那么该情况应为 球同，盒不同 ， 允许空盒

用票数解释

可以理解为x可以没有票，那我们可以先给它1张票，再进行隔板法给它分票（这样就可以分到空票了），分完再给它拿回来

x1+x2+x3+…+xm = n x1 >= 0 -> xx1 >= x1+1 , n=n+1

xx1+x2+x3+…+xm = n + 1 -> C n+1-1 m-1

如果均 >=0,上述式子可改为

x1+x2+x3+…+xm = n + m(m个1) -> C n+m-1 m-1