题解：CF1948F Rare Coins

令 $[l, r]$ 中有 $a$ 个金币，$[l,r]$ 外有 $b$ 个金币。$[l, r]$ 中有 $c$ 个银币，$[l, r]$ 外有 $d$ 个银币。

不妨枚举 $[l, r]$ 中有多少银币的价值为 $1$，$[l, r]$ 外有多少银币的价值为 $1$。令为 $x, y$。那么如果 $(x, y)$ 满足以下条件，就应将 $\dbinom cx \dbinom dy$ 累加入答案。

- $0 \le x \le c$
- $0 \le y \le d$
- $a+x > b+y$

其中第三条等价于 $x-y\ge b-a+1$。接下来令 $k=b-a+1$。

既然 $x,y$ 的差值不低于 $k$，那么不妨枚举这个差值 $p \in [k,c]$（上限 $c$ 在 $x$ 最大，$y$ 最小时取到）。那么答案为：

$$
\sum_{p=k}^{c} \sum_{y=0}^d \dbinom c{y+p}\dbinom dy
$$

~~可以证明~~我们来证明一下后面这个和式的答案为 $\dbinom {c+d}{d+p}$。

$$
\begin{aligned}
\sum_{y=0}^d \dbinom c{y+p}\dbinom dy &= 
\sum_{y=0}^d \dbinom c{(c-p)-y}\dbinom dy \\
&= \dbinom {c+d}{c-p} \\
&= \dbinom {c+d}{d+p}
\end{aligned}
$$

其中倒数第二步用到了范德蒙德卷积。证明考虑其组合意义，等式右边指从 $c+d$ 个物品中选择 $c-p$ 个的方案数，于是枚举 $i$ 表示在前 $c$ 个物品中选了 $i$ 个，那么剩下的 $c-p-i$ 个物品就应从后 $d$ 个中选，也就是等式左边的意义。

所以答案：

$$
\sum_{p=k}^{c} \dbinom {c+d}{d+p}
$$

换个记号：

$$
\sum_{p=k+d}^{c+d} \dbinom {c+d}{p}
$$

注意到对于每次询问 $c+d$ 的值是固定的，是整个序列的银币总数。所以预处理上指标为 $c+d$ 的组合数，再前缀和即可。

<https://codeforces.com/contest/1948/submission/291181927>

正在渲染内容...