记录一个组合意义的题目
对于所有的 \(s\in [1,n]\) ，求出：
\[\sum_{i=p}^m{i+s-1\choose s-1}{m-i+n-s-1\choose n-s-1} \]其中 \(p,m\) 是给定的常数，\(n,m,p\le 10^6\)。
来源：在星河里
我们将 \(s\) 的答案设作 \(f(s)\)。
考虑组合意义：将 \(m\) 个小球放入 \(n\) 个盒子，且前 \(s\) 个盒子至少要占 \(p\) 个球。
那么对于 \(f(s+1)\)，相比 \(f(s)\) 所多的方案恰好是第 \(p\) 个球处在第 \(s+1\) 的盒子的情况，第 \(1\sim p-1\) 个球处于前 \(s+1\) 个盒子而第 \(p+1\sim m\) 个球处于第 \(s+1\sim n\) 个盒子，即：\(f(s+1)=f(s)+{p+s-1\choose s}{m-p-1+n-s-1\choose n-s-1}\)
于是 \(\mathcal O(n+m)\) 解决了这道题目。
这是一种对于变参求值的快速计算方法：算出一个，其他递推
这是一种考虑组合意义的角度：小球放盒子
标签：盒子,组合,记录,choose,题目,sim,个球 From： https://www.cnblogs.com/lupengheyyds/p/18679862