Description

给定长度为 n 的 01 串 S,定义 F(x, y) (x <= y)为 S 串第 x 位到第 y 位中 ‘1’ 的个数。 求有多少个三元组 (i, j, k) 满足 i < j < k, Sj = 1 且 F(i, j) = F(j, k)

Hint

3≤n≤2∗1053 \leq n \leq 2 * 10^5

Solution

考试的时候一直是往先确定j，然后再去计算i和k的取值的方面想的，然后不知道怎么优化到O(N)O(N)。。。 可以发现，当确定了i和k时，j就能被确定。并且只有当F(i,k)为奇数且除了i和k之外至少要有一个1时才存在j。然后我们用前缀和搞一下就可以了

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
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int Maxn = 2 * 1e5 + 100;

int A[Maxn], N;
int Sum[Maxn], SUM[Maxn][2], Next[Maxn], Pre[Maxn];

inline int safe_getchar ()
{
    char ch = getchar();
    while (ch != '0' && ch != '1') ch = getchar();
    return ch - '0';
}

main()
{
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
    scanf("%lld", &N);
    for (int i = 1; i <= N; ++i)
        A[i] = safe_getchar(), Sum[i] = Sum[i - 1] + A[i];
    int cnt1 = 0, cnt2 = 0, Ans = 0, pos = 0;
    SUM[0][0] = 1;
    for (int i = 1; i <= N; ++i)
    {
        if (Sum[i] & 1)
            SUM[i][1] = SUM[i - 1][1] + 1, SUM[i][0] = SUM[i - 1][0];
        else 
            SUM[i][0] = SUM[i - 1][0] + 1, SUM[i][1] = SUM[i - 1][1];
        Pre[i] = pos;
        if (A[i])
            pos = i;
    }
    for (int i = 2; i <= N; ++i)
    {
        Ans += SUM[Pre[i] - 2][((Sum[i] % 2) ^ 1)];
//      cout<<i<<" "<<Ans<<endl;
    }
    cout<<Ans<<endl;
    return 0;
}