本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-18 14:23:23

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

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

• $i \le n-x-1$。

  当前作为 $10^i$ 被计入答案的次数为 $\binom{n-1-i-1}{k-1} = \binom{n-i-2}{k-1}$。

  即，剩余可以放加号的空位的数量是 $n-1-i-1$，然后由于右边固定了一个加号做结尾，所以只需要再放 $k-1$ 个加号。

• $i = n-x$。

  当前作为 $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)$ 算出贡献了。