俞越201811161904122

数论 2021-03-02

数论

DS(1) 未归档(9) 组合数学(1) 胡扯(10) 记录(1)

/ 注册

2021-03-02

426 浏览 0 回复 2021-03-02

俞越201811161904122

+关注

范德蒙特卷积部分和

对于n,m,k,多次给定a,求

$∑_{i=k} \binom{a+(i)-1}{(i)-1}*\binom{m-a+(n-i)-1}{(n-i)-1}$

上式组合意义为 $m$ 个球放进 $n$ 个盒子中，前 $a$ 个盒子中球的个数 $\ge k$ 的方案数。
考虑第k个球，一定在前a个盒子中的某一个
枚举第k个球的位置得 $∑_{i=1}^{a} \binom{k-1+i-1}{i-1}*\binom{n-k+(n-i+1)-1}{(n-i+1)-1}$ 前缀和即可

举报

收藏

赞

评论加载中...