题解：CF520E Pluses everywhere

__vector__ · 2025-09-18 14:23:23 · 题解

考虑分别计算每一位产生的贡献，加起来得到总和。

假设当前是从左边数第 x 位，那么分类讨论两种情况。

• 当前作为 $10^i$ 被计入答案的次数为 $\binom{n-1-i-1}{k-1} = \binom{n-i-2}{k-1}$。 即，剩余可以放加号的空位的数量是 $n-1-i-1$，然后由于右边固定了一个加号做结尾，所以只需要再放 $k-1$ 个加号。
• 当前作为 $10^i$ 被记入答案的次数为 $\binom{x-1}{k}$。 即，位置 $1$ 到 $x$ 有 $x-1$ 个空位，填 $k$ 个加号，且当前数字段一直到结尾。

考虑预处理 p_i = \sum\limits_{j=1}^i \binom{n-j-2}{k-1}10^j。

然后枚举每一位就能 O(1) 算出贡献了。