范德蒙德卷积的奇妙用法

· · 算法·理论

求解满足以下方程的解的个数：

\sum_{i = 1}^n x_i = M \quad \text{且} \quad 0 \le x_i < p_i

已知数据范围为 (n \le 32)。

定义子集和 v_S = \sum_{i \in S} p_i，并令 m = n - 1。 通过容斥原理将总答案表示为：

\text{Ans} = \sum_{S \subseteq \{1 \dots n\}, v_S \le M} (-1)^{|S|} \binom{M - v_S + m}{m}

考虑到 n \le 32，直接枚举所有子集复杂度过高。我们需要将维度均分为两半，差分成两个分别只与集合 A 和集合 B 有关的式子：

\sum_{v_A \le M} (-1)^{|S_A|} \sum_{v_B \le M - v_A} (-1)^{|S_B|} \binom{(M - v_A) - v_B + m}{m}

利用范德蒙德卷积分离变量

我们令 X = M - v_A，Y = v_B。可以得到：

\binom{X - Y + m}{m} = \sum_{i = 0}^m \binom{X + m}{m - i} \binom{-Y}{i}

交换求和次序，即可得到最终公式：

\sum_{v_A \le M} (-1)^{|S_A|} \sum_{i = 0}^m \binom{X + m}{m - i} \left( \sum_{v_B \le X} (-1)^{|S_B|} \binom{-Y}{i} \right)

其中：\binom{-Y}{i} = \frac{(-Y)^{\underline{i}}}{i!}