题解 CF520E 【Pluses everywhere】
Heartlessly
2019-11-06 20:45:27
## Description
给定一个 $n$ 位数 $a$，请你在这些数位之间添加 $m$ 个 `+` 号，得到一个表达式。求所有可能的不同表达式的和，答案对 $10^9 + 7$ 取模。
$(0 \leq m < n \leq 10^5)$
## Solution
考虑单独计算每一个 $a_i$ 的贡献。
首先一共有 $n - 1$ 个位置可以放加号，根据离 $a_i$ 最近且在 $a_i$ 之后的加号位置分情况讨论：
若最近的加号在 $a_i$ 后面，则剩下 $m - 1$ 个加号，有 $n - 2$ 个位置可以放，$a_i$ 的贡献为 $a_i \times {\rm C}_{n-2}^{m - 1}$；
若最近的加号在 $a_{i+1}$ 后面，则剩下 $m - 1$ 个加号，有 $n - 3$ 个位置可以放，$a_i$ 的贡献为 $a_i \times 10 \times {\rm C}_{n-3}^{m - 1}$；
若最近的加号在 $a_{i+2}$ 后面，则剩下 $m - 1$ 个加号，有 $n - 4$ 个位置可以放，$a_i$ 的贡献为 $a_i \times 10^2 \times {\rm C}_{n-4}^{m - 1}$；
……
若最近的加号在 $a_{i+n-m-1}$ 后面，则剩下 $m - 1$ 个加号，有 $m - 1$ 个位置可以放，$a_i$ 的贡献为 $a_i \times 10^{n - m - 1} \times {\rm C}_{m - 1}^{m - 1}$ 。（当且仅当其它加数都是一位数时 $a_i$ 的单次贡献为 $a_i \times 10^{n - m - 1}$）
特殊地，当最近的加号在 $a_{n}$ 后面时，剩下 $m$ 个加号，有 $i - 1$ 个位置可以放，$a_i$ 的贡献为$a_i \times 10^{n - i} \times {\rm C}_{i - 1}^{m}$ 。
答案就是贡献总和。
直接枚举 $a_i$ 的贡献为 $10^j$ 的时间复杂度是 $O(n^2)$ 的。
我们发现贡献是 $10^j$ 的数字乘上的组合数是相同的，因此前缀和预处理出能产生 $10^j$ 贡献的数字总和即可，注意加号放在 $a_n$ 后时要单独计算，时间复杂度为 $O(n)$ 。
最后的式子：
$$\sum\limits_{i = 1}^{n - m} 10^{i - 1} \times \left(\sum\limits_{j = 1}^{n - i}a_j \times {\rm C}_{n - 1 - i}^{m - 1} + a_{n - i + 1} \times {\rm C}_{n - i}^{m}\right)$$
枚举 $i$，计算所有 $i$ 位数产生的贡献。
## Code
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}
inline void readDigit(int &x) {
char c = getchar();
for (; !isdigit(c); c = getchar());
x = c ^ 48;
}
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}
const int MAXN = 1e5, MOD = 1e9 + 7;
int n, m, ans, a[MAXN + 5], pre[MAXN + 5], fac[MAXN + 5], inv[MAXN + 5];
inline int quickPow(int x, int p) {
int res = 1;
for (; p; p >>= 1, x = 1ll * x * x % MOD)
if (p & 1) res = 1ll * res * x % MOD;
return res;
}
inline void init() {
fac[0] = 1;
for (int i = 1; i <= MAXN; ++i) fac[i] = 1ll * fac[i - 1] * i % MOD;
inv[MAXN] = quickPow(fac[MAXN], MOD - 2);
for (int i = MAXN - 1; ~i; --i) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
}
inline int c(int n, int m) {
if (n < 0 || m < 0 || n < m) return 0;
return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
int main() {
read(n), read(m);
for (int i = 1; i <= n; ++i) {
readDigit(a[i]);
pre[i] = pre[i - 1] + a[i];
}
init();//预处理组合数
for (int cur = 1, i = 1; i <= n - m; ++i, cur = 1ll * cur * 10 % MOD)
ans = (ans + 1ll * cur * (1ll * pre[n - i] * c(n - 1 - i, m - 1) % MOD +
1ll * a[n - i + 1] * c(n - i, m) % MOD) % MOD) % MOD;
write(ans);
putchar('\n');
return 0;
}
```