范德蒙德卷积做一半！
Cry_For_theMoon
·
·
个人记录
可能不算什么新的东西，昨天在这个题里遇见了而已，感觉非常神，记录一下。
大家都知道：
\sum_{i=0}^{n} \dbinom{p+i-1}{i}\dbinom{n-i+q-1}{n-i}=\dbinom{n+p+q-1}{n}
道理也非常简单，枚举 i 以后，左边是 x_1+x_2+...+x_{p}=i 的非负解数，右边是 x_1+x_2+...+x_{q}=n-i 的非负解数。那么自然整个和式就是 x_1+x_2+...+x_{p+q}=n 的非负解数。
那么，如果我们的式子是：
\sum_{i=m}^{n} \dbinom{p+i-1}{i}\dbinom{n-i+q-1}{n-i}
也就是说，仅仅修改了求和的下指标，该如何处理呢？显然计算它，最坏还是 O(n) 的。
虽然我们找不到一个 O(1) 的式子，但我们确实可以导出一个和它相等的等式：
\sum_{i=1}^{p}\dbinom{i+m-2}{m-1}\dbinom{n-m+p+q-i}{n-m}
然后，我们就可以 O(p) 计算这个式子；当然，你也可以做到 O(q) 计算。
那么，到底是为什么来着？
首先我们的求和范围是 \sum_{m}^{n} 而不是 \sum_{0}^{m}，因为这可以更方便地赋予我们所求的内容组合意义：我们考虑有 p+q 个盒子里装了球，第 i 个盒子里的球标号为 i。然后前 p 个盒子的球是黑色，后 q 个盒子的球是红色。
则我们相当于在做这样一个事情：从 p+q 个盒子里选择 n 个球出来，只关注标号构成的多重集，然后对黑色球至少有 m 个的情况计数。
所以原来的式子就是在枚举，我们到底有多少个黑色球。然后左边是在把黑色球分给 p 个盒子，右边是在把红色球分给 q 个盒子。
那么下面的式子又是在做什么呢？对于任何一个黑球出现次数 \ge m 的多重集 S，我们把黑色球按照标号顺序排开：111..222..333... 这样的形式。然后我们定义 F(S) 是第 m 个黑球的标号。那么，其实我们就是在枚举 i，然后计算有多少个 S 满足 F(S)=i 的。因此，左边的组合数是在枚举前 m-1 个黑球，它们可以分配被标号为 1\sim i 的盒子，而后面的 n-m 个黑球+红球，如果它是黑球，就可以分配给标号为 i\sim p 的盒子，否则就分配给 p+1\sim q 的盒子。所以我们其实就是在把后面的 n-m 个球分配给 (p+q)-i+1 个盒子。然后我们从组合意义证明了两边式子的相等。