题目本质上求的是 \(\sum a_i=m, a_i\le k\) 的方案数
那么 \(dp\) 的做法很显然
然后考虑咋做 \(n\le 10^9\) 的部分
这时候需要再去看一遍题目，发现 \(n>m\) 的时候无解
用隔板法来解决剩下的问题
如果没有限制的话那么 \(\binom {m-1}{n-1}\)
然后容斥： $ans=\sum_{i=0}^n (-1)^i \binom{m-i\times k-1}{n-1}\binom ni $
复兴了隔板法
题目中条件给到了一共的身高可能只有 \(6000\) 种
那么离散化之后套一个 \(\Theta(n^2 k)\) 的 \(dp\) 就行了
\(@ZZ\_zuozhe\) 使用了斜率优化的手段 \(orz\)
模拟即可
我写了两天，交出了 \(13k\) 的代码
设 \(f_{i,j,k,x}\) 为可以放 \(i\) 个个数为 \(1\) 的小球， \(j\) 个个数为 $2 $ 的小球，\(k\) 个个数为 \(3\) 的小球
那么枚举上次拿了多少小球可以得到转移方程
直接记搜上去即可
原文：https://www.cnblogs.com/yspm/p/13867142.html