题目描述
https://acm.hdu.edu.cn/showproblem.php?pid=7060
简要题解：给定一个长度为 $n$ 的数字和整数 $k$，求将这个数字划分成不超过 $k$ 段的所有划分方法的价值和，定义一种划分方法的价值为它各段的价值和，一段数字的价值就是这个数字的值，例如：$114514$ 的一种划分 $(114)(5)(14)$ 的总价值是 $114+5+14=133$
$1\le k\le n\le 10^6$
Solution
我们考虑对于每个区间 $[l,r]$ 计算它的价值会被计算所少次
为了方便设 $l>1\wedge r <n$，$s=l-1,t=n-r$
容易得到次数就是 $\sum_{d=2}^{k-1}\sum_{i=1}^{d-1}\binom{s-1}{i-1}\binom{t-1}{d-i-1}=\sum_{d=2}^{k-1}\binom{s+t-2}{d-2}=\sum_{d=0}^{k-3}\binom{s+t-2}{d}$，这是一个组合数前缀和的形式
容易发现，这个东西只跟 $[l,r]$ 的长度有关，我们令 $f_i$ 表示长度为 $i$ 的区间的和，那么可以得到随着 $i$ 的增加，这个组合数的上指标在减少，且总共只会移动 $O(n)$，我们可以 $O(n)$ 维护它的变化
另外前缀和后缀以及 $k\le 2$ 的情况要单独考虑
时间复杂度 $O(n)$
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| #include <iostream>
#include <vector>
#include <cstring>
#define maxn 1000010
#define ll long long
using namespace std;
const int p = 998244353;
ll pow_mod(ll x, ll n) {
ll s = 1;
for (; n; n >>= 1, x = x * x % p)
if (n & 1) s = s * x % p;
return s;
}
int n, k, s[maxn];
char c[maxn];
ll pre[maxn], suf[maxn], f[maxn];
ll inv[maxn], fac[maxn];
void init_C(int n) {
fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % p;
inv[n] = pow_mod(fac[n], p - 2); for (int i = n - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % p;
}
ll C(int n, int m) { return n < m ? 0 : fac[n] * inv[m] % p * inv[n - m] % p; }
struct Csum {
int l, r; ll inv2, sum;
void init() { l = r = 1; sum = 2; inv2 = pow_mod(2, p - 2); }
ll move(int L, int R) { L = min(L, R);
while (r < R) sum = (2 * sum - C(r++, l)) % p;
while (l > L) sum = (sum - C(r, l--)) % p;
while (r > R) sum = (sum + C(--r, l)) * inv2 % p;
while (l < L) sum = (sum + C(r, ++l)) % p;
return sum;
}
ll get() { return sum; }
} S;
void work() {
cin >> k >> c + 1; n = strlen(c + 1);
s[n + 1] = 0; for (int i = n; i; --i) s[i] = s[i + 1] + c[i] - '0';
for (int i = 1; i <= n; ++i) pre[i] = (pre[i - 1] * 10 + c[i] - '0') % p;
ll mul = 1; for (int i = n; i; --i) suf[i] = (c[i] - '0') * mul % p, mul = mul * 10 % p;
suf[n + 1] = 0; for (int i = n; i; --i) suf[i] = (suf[i] + suf[i + 1]) % p;
if (k <= 2) {
if (k == 1) cout << pre[n] << "\n";
else {
ll ans = pre[n];
for (int i = 1; i < n; ++i)
ans = (ans + pre[i] + suf[i + 1]) % p;
cout << ans << "\n";
}
return ;
}
for (int i = 1; i <= n; ++i) f[i] = ((f[i - 1] - suf[n - i + 2]) * 10 + s[i]) % p;
for (int i = 1; i <= n; ++i) f[i] = (f[i] - pre[i] - suf[n - i + 1]) % p;
S.init(); ll ans = pre[n];
for (int i = 1; i <= n - 2; ++i)
ans = (ans + f[i] * S.move(k - 3, n - i - 2)) % p;
for (int i = 1; i < n; ++i)
ans = (ans + pre[i] * S.move(k - 2, n - i - 1)) % p;
for (int i = 2; i <= n; ++i)
ans = (ans + suf[i] * S.move(k - 2, i - 2)) % p;
cout << (ans + p) % p << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T; init_C(1000000);
while (T--) work();
return 0;
}
|