【组合数学、范德蒙德恒等式】ABC433F
WanderOvO
·
·
题解
【组合数学、范德蒙德恒等式】ABC433F
原题链接
简要题意
给定一个数字字符串 S，计算其子序列中满足“1122 结构”的数量。
所谓 1122 结构指：字符串由 k 个数字 d 和随后的 k 个数字 d+1 组成（k \ge 1, 0 \le d \le 8）。
例如：1122 (k=2, d=1)、444555 (k=3, d=4)。
## 思路
### 1. 拆解与枚举
由于 $d$ 只能是 $0 \sim 8$，我们首先枚举这 9 种相邻数字对 $(d, d+1)$。对于每一种情况，我们独立计算贡献并累加。
### 2. 定序去重（关键观察）
为了防止同一个子序列被重复计算，我们需要找到一个**唯一的统计标准**。
我们规定：**在枚举数字对 $(d, d+1)$ 时，固定子序列中最后一个 $d$ 在原字符串 $S$ 中的位置为 $i$。**
这样，对于任何一个确定的 1122 子序列，其第一个数字段的终点是唯一的，从而实现了不重不漏。
### 3. 组合数学建模
假设当前枚举到位置 $i$ 且 $S[i] = d$：
- 设 $A$ 为 $S[1 \dots i]$ 中数字 $d$ 的出现次数。
- 设 $B$ 为 $S[i+1 \dots n]$ 中数字 $d+1$ 的出现次数。
- 若该子序列的半长度为 $k$：
- 左侧需从剩余的 $A-1$ 个 $d$ 中选出 $k-1$ 个，方案数为 $\binom{A-1}{k-1}$。
- 右侧需从 $B$ 个 $d+1$ 中选出 $k$ 个，方案数为 $\binom{B}{k}$。
- 该位置的总贡献为：$\sum_{k=1}^{\min(A, B)} \binom{A-1}{k-1} \binom{B}{k}$。
### 4. 范德蒙德恒等式优化
直接枚举 $k$ 会导致 $O(N^2)$ 的复杂度，在 $N=10^6$ 下无法接受。观察求和式：
利用 $\binom{n}{r} = \binom{n}{n-r}$，将 $\binom{B}{k}$ 改写为 $\binom{B}{B-k}$。
则原式为：$\sum \binom{A-1}{k-1} \binom{B}{B-k}$。
根据**范德蒙德恒等式**，这等价于从 $(A-1) + B$ 个元素中选取 $(k-1) + (B-k) = B-1$ 个元素。
即：
$$\text{Contribution} = \binom{A+B-1}{B-1} = \binom{A+B-1}{A}$$
通过预处理阶乘逆元，我们可以 $O(1)$ 计算该结果，使总复杂度降为 $O(9N)$。