「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)$ 。

最后的式子:

枚举 $i$,计算所有 $i$ 位数产生的贡献。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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;
}

本文标题:「Codeforces 520E」Pluses everywhere

文章作者:Heartlessly

发布时间:2019年11月05日 - 20:32:55

最后更新:2019年11月07日 - 20:50:37

原始链接:https://heartlessly.github.io/problems/codeforces-520e/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%