一些前置组合数问题
$$
m \binom n m = (n - m + 1) \binom n {m - 1}
$$证明方法为将组合数拆为阶乘。
$$
\forall 1 \le i < n, \binom {n + m} n = \sum _ {j = 0} ^ m \binom {i + j} j \binom {n + m - i - j - 1} {m - j}
$$考虑组合数意义，等式左侧可以理解为从 $(0, 0)$ 走向 $(n, m)$ 每次可以使得横坐标加一，或者纵坐标加一。考虑分解这个过程，对于每个纵坐标，横坐标从 $i$ 增加到 $i + 1$ 的过程，即 $(0, 0) \to (i, j)$ 与 $(i + 1, j) \to (n, m)$ 方案数相乘。
$$
\forall 1 \le i < n, 1 \le s < m, \sum _ {j = 0} ^ s \binom {i + j} j \binom {n + m - i - j - 1} {m - j} = \sum _ {j = i + 1} ^ n \binom {j + s} s \binom {n + m - j - s - 1} {n - j}
$$左式和上一个结论的右式相似。现在有了范围的限制，即横坐标从 $i$ 增加到 $i + 1$ 的过程，只能从 $[0, s]$ 纵坐标通过，这意味着要超过 $s$ ，只能在后面实现，即 $(0, 0) \to (j, s)$ 与 $(j, s + 1) \to (n, m)$ 的方案数相乘。
考虑拆贡献：
$$
ANS = \sum _ {i = 1} ^ {n - 1} w _ i \sum _ {j = 0} ^ m\left | s _ i - j\right | Div(j, i) Div(m - j, n - i)
$$
即枚举 $b _ i$ 的前缀和 $j$ ，前面 $i$ 分 $j$ 个，后面 $n - i$ 分 $m - j$ 个，考虑插板法，可以知道
$$
Div (n, m) = \binom {n + m - 1}{m - 1}
$$
所以有：
$$
\begin {aligned}
ANS & = \sum _ {i = 1} ^ {n - 1} w _ i \sum _ {j = 0} ^ m \left | s _ i - j\right | \binom {i + j - 1}{i - 1} \binom {n + m - i - j - 1} {n - i - 1} \\
& = \sum _ {i = 1} ^ {n - 1} w _ i (2\sum _ {j = 0} ^ {s _ i}(s _ i - j) \binom {i + j - 1}{i - 1} \binom {n + m - i - j - 1} {n - i - 1} + \sum _ {j = 0} ^ m (j - s _ i)\binom {i + j - 1}{i - 1} \binom {n + m - i - j - 1} {n - i - 1})
\end {aligned}
$$
依次考虑：
$$
\begin {aligned}
A = & \sum _ {j = 0} ^ m (j - s _ i)\binom {i + j - 1}{i - 1} \binom {n + m - i - j - 1} {n - i - 1} \\
= & \sum _ {j = 0} ^ m j\binom {i + j - 1}{i - 1} \binom {n + m - i - j - 1} {n - i - 1} - s _ i\sum _ {j = 0} ^ m\binom {i + j - 1}{i - 1} \binom {n + m - i - j - 1} {n - i - 1} \\
= & \sum _ {j = 0} ^ m i \binom {i + j - 1}{i} \binom {n + m - i - j - 1} {n - i - 1} - s _ i\sum _ {j = 0} ^ m \binom {i + j - 1}{i - 1} \binom {n + m - i - j - 1} {n - i - 1} \\
= & \sum _ {j = 1} ^ m i \binom {i + j - 1}{i} \binom {n + m - i - j - 1} {n - i - 1} - s _ i\sum _ {j = 0} ^ m \binom {i + j - 1}{i - 1} \binom {n + m - i - j - 1} {n - i - 1} \\
= & i \sum _ {j = 0} ^ {m - 1} \binom {i + j}{i} \binom {n + m - i - j - 2} {n - i - 1} - s _ i\sum _ {j = 0} ^ m \binom {i + j - 1}{i - 1} \binom {n + m - i - j - 1} {n - i - 1} \\
= & i \binom {n + m - 1} n - s _ i \binom {n + m - 1} m
\end {aligned}
$$
$$
\begin {aligned}
B = & \sum _ {j = 0} ^ {s _ i}(s _ i - j) \binom {i + j - 1}{i - 1} \binom {n + m - i - j - 1} {n - i - 1} \\
= & s _ i\sum _ {j = 0} ^ {s _ i} \binom {i + j - 1}{i - 1} \binom {n + m - i - j - 1} {n - i - 1} - \sum _ {j = 0} ^ {s _ i} j \binom {i + j - 1}{i - 1} \binom {n + m - i - j - 1} {n - i - 1} \\
= & s _ i\sum _ {j = 0} ^ {s _ i} \binom {i + j - 1}{i - 1} \binom {n + m - i - j - 1} {n - i - 1} - i \sum _ {j = 0} ^ {s _ i} \binom {i + j - 1}{i} \binom {n + m - i - j - 1} {n - i - 1} \\
= & s _ i\sum _ {j = 0} ^ {s _ i} \binom {i + j - 1}{i - 1} \binom {n + m - i - j - 1} {n - i - 1}- i\sum _ {j = 0} ^ {s _ i - 1} \binom {i + j}{j} \binom {n + m - i - j - 2} {m - j - 1} \\
= & s _ i\sum _ {j = i} ^ {n - 1} \binom {j + s _ i}{j} \binom {n + m - j - s _ i - 2}{n - j - 1}- i \sum _ {j = i + 1} ^ n \binom {j + s _ i - 1} j \binom {n + m - j - s _ i - 1}{n - j} \\
\end {aligned}
$$
至此可以同时维护 $4$ 个值实现 $O(1)$ 转移了。均摊复杂度 $O(n + m)$ 。
对于 $A$ 式，每个 $i$ 的变化和 $s _ i$ 的变化很好维护。考虑 $B$ 式，即 $f$ 为答案 $A + 2B$ ，即 $g _ 0$ 为 $s _ i$ 增加时 $B$ 中贡献的数，$g _ 1$ 为 $i$ 增加时 $B$ 中减少的数。考虑如何维护 $g _ 0, g _ 1$ 。那么最开始的时候，有 $g _ 0 = \binom {n + m - 2} m, g _ 1 = 0$ ，可以推出 $g _ 0, g _ 1$ 的变化。
查看代码
1 |
|