华科大-04. 美丽字符串
2023.10.24活动
「10·24」程序员节编程竞赛
设s下标从0开始。
我们分别求每个前缀的贡献。
对于s[i] = '0'的贡献，我们假设已经统计了前缀s[0...i]中的'0'的个数c0。
这时候，扩展串长度为2i+1，在排序后要保证串中心为'0'，那么至少需要i+1个'0'字符。我们已经有了c0个'0'字符。还需要至少i＋1-c0个字符。而在扩展串中我们可以操控的位置是i个，所以考虑i个位置中分别选i+1-c0个的情况，i+1-c0+1个的情况，等等，直到i个的情况。所以只需要计算组合数$C_{i}^{i+1-c0}+C_{i}^{i+1-c0+1}+\cdots+C_{i}^{i}$
转化一下得到$C_{i}^{c0-1}+C_{i}^{c0-2}+\cdots+C_{i}^{0}$。对于每一个前缀串，都需要计算这么一个组合数，直接遍历计算妥妥超时。必须$O(1)$计算出该值。
发现一个重大规律就是i和c0只增不减。
设$S_{i,j} = C_{i}^{0}+C_{i}^{1}+\cdots+C_{i}^{j}$
对于s[0...i]有j个'0'，已知$S_{i,j}$的情况下，s[i+1]='1'时，我们只需要求$S_{i+1,j+1}$，并将其加入答案中;s[i+1]='0'时，我们需要求$S_{i+1,j}$。
通过杨辉三角发现一个组合恒等式$C_{i}^{j}+C_{i}^{j+1} = C_{i+1}^{j+1}$
$2*S_{i,j} - C_{i}^{j} = S_{i+1, j}$
$2*S_{i,j} - C_{i}^{j} + C_{i+1, j+1} = S_{i+1, j+1}$
至此状态转移只需$O(1)$做到。总时间复杂度$O(n)$
对于s[i]='1'的情况，同理。
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
| class Solution {
public:
using ll = long long;
const ll MOD = 998244353;
#define N 200005
ll fac[N], inv_fac[N];
ll fpow(ll x, ll p, ll m) {
ll rt = 1;
while (p) {
if (p&1) rt *= x, rt %= m;
x *= x; x %= m;
p >>= 1;
}
return rt;
}
void PP() {
fac[0] = 1;
for (int i=1; i<N; i++) {
fac[i] = fac[i-1]*i%MOD;
}
inv_fac[N-1] = fpow(fac[N-1], MOD-2, MOD);
for (int i=N-2; i>=0; i--) {
inv_fac[i] = inv_fac[i+1]*(i+1)%MOD;
}
}
ll C(int n, int m) {
if (n<0 || m < 0 || n<m) return 0;
return fac[n]*inv_fac[m]%MOD*inv_fac[n-m]%MOD;
}
int beautifulString(string s) {
PP();
ll ans = 0, c1 = 0, p1 = 0, c0 = 0, p0 = 0;
int n = s.size();
for (int i=0; i<n; i++) {
if (s[i] == '1') c1++;
else c0++;
if (s[i] == '1') {
p1 = 2*p1-C(i-1, c1-2)+C(i, c1-1);
p1 = (p1+MOD)%MOD;
p0 = 2*p0-C(i-1, c0-1);
p0 = (p0+MOD)%MOD;
ans += p1;
} else {
p0 = 2*p0-C(i-1, c0-2)+C(i, c0-1);
p0 = (p0+MOD)%MOD;
p1 = 2*p1-C(i-1, c1-1);
p1 = (p1+MOD)%MOD;
ans += p0;
}
ans %= MOD;
}
return ans;
}
};
|