「Codeforces 520E」Pluses everywhere

Description

给定一个 $n$ 位数 $a$，请你在这些数位之间添加 $m$ 个 + 号，得到一个表达式。求所有可能的不同表达式的和，答案对 $10^9 + 7$ 取模。

$(0 \leq m < n \leq 10^5)$

Source

[Luogu]CF520E

[Codeforces]520E

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

#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;
}