D 三哼儿经 EASY

平方复杂度的方法

对于字符串\(S\)

我们考虑每一个字符\(S[pos], pos\in[0, n)\).

计算有多少个以第\(pos\)个字符结尾的,含有奇数个字符的子串.

我么可以这样想:

一个以第\(pos\)个字符为结尾的子串\(S[start, pos]\),可以看作是子串\(S[0, pos]\)删掉前面的\(S[0,start)\).

然后可以发现

• 如果\(S[0,pos]\)里出现了奇数个\(1\),而子串\(S[0,start)\)里出现了偶数个\(1\),那么显然\(S[start, pos]\)这个子串含有奇数\(1\).

• 如果\(S[0,pos]\)里出现了偶数个\(1\),而子串\(S[0,start)\)里出现了奇数个\(1\),那么显然\(S[start, pos]\)这个子串含有奇数\(1\).

所以对于每一个字符\(S[pos]\),我们可以通过以上的方法来计算.

要注意,\(S[0,pos]\)本身也要考虑,也就是要考虑\(start\)为0的情况(也就是前面部分是空串\(S[0,0)\)).

伪代码如下

int len = strlen(S);
int one_cnt = 0;
int ans = 0;
for (int pos = 0; pos < len; ++S)
{
    int one_tmp = 0;
    if (S[pos] == '1') one_cnt++;
    if (one_cnt % 2) ans++; //S[0,0) 
    for (int start = 0; start < pos; ++start)
    {
        if (S[start] == '1') one_tmp++;
        if ((one_cnt) % 2 != (one_tmp) % 2) ans++;
    }
}

线性复杂度的方法

他们求和就能得到答案.

这时你会发现,这样对于每一个子串\(S[0,pos]\),都要往前面找有多少个\(S[0.start)\)符合条件,这是应该\(O(n^2)\)的.

可以这样优化.

我们用两个变量\(cnt0\)和\(cnt1\),分别有多少个 \(S[0,x), x\in[0, pos)\)含有奇数个\(1\),多少个 \(S[0,x), x\in[0, pos)\)含有偶数个\(1\).

在循环\(pos\)的时候就可进行维护这两个变量.

• 如果当前的如果\(S[0,pos]\)里出现了奇数个\(1\),那么答案就加上\(cnt0\).

• 如果当前的如果\(S[0,pos]\)里出现了偶数个\(1\),那么答案就加上\(cnt1\).

int len = strlen(S);
int cnt0 = 0, cnt1 = 0;
int one_cnt = 0;
int ans = 0;
cnt0++; //一开始cnt0计算了S[0.0);
for (int pos = 0; pos < len; ++S)
{
    if (S[pos] == '1') one_cnt++;
    if (one_cnt % 2) cnt1++;
    else cnt0++;
    if (one_cnt % 2) ans += cnt0;
    else ans += cnt1;
}

以下是巨丑无比的标程

#include <stdio.h>
#include <string.h>

#define maxn (100000+100)
#define p (998244353)

long long cnt[2];
char str[maxn];

int main()
{
    int n;
    int i;
    long long ans, pre1;
    while (scanf("%d", &n) != EOF)
    {
        scanf("%s", str);
        ans = pre1 = 0;
        cnt[0] = 1; cnt[1] = 0;

        for (i = 0; i < n; ++i)
        {
            pre1 += (str[i] == '1');
            ans = (ans + cnt[!(pre1%2)]) % p;
            cnt[pre1%2] += 1;
        }
        printf("%lld\n", ans);
    }
}

三哼儿经HARD

题目要求算:

原字符串的每一个子串\(S[start,pos]\)里面包含多少个符合条件的子串\(S[st, ed](start\leq st \leq ed \leq pos)\).

但是这很难算,所以我们应该算的是:

每一个符合条件的子串\(S[start, pos]\)被多少个子串\(S[st,ed](st\leq start \leq pos \leq ed)\)包含.

平方复杂度的方法

对于字符串

0110101

我们考虑他的这个子串\(S[1, 4]=1101\),如果要找一个子串\(S[st,ed](st\leq start \leq pos \leq ed)\).

那么\(st\)的取值只能是\([0,start]\)(也就是\(0, 1\)),\(ed\)的取值只能是\([pos, len)\)也就是(\(4,5,6\)).

所以子串\(S[1,4]\)被\((start+1)*(len-pos) = 6\)个子串包含着(\(S[0, 4], S[0,5], S[0,6], S[1,4], S[1,5], S[1,6]\)).

如果要求\(O(n^2)\)的复杂度,你应该已经知道该怎么算了.

我们可以\(O(n^2)\)地找到每一个符合条件的子串,然后\(O(1)\)地计算答案.

线性复杂度的方法

然而这题需要\(O(n)\),那么我们又可以优化一下.

如果我们考虑字符\(pos\),我们还是可以像EASY一样,\(O(1)\)地找到每一个\(start\).

但是这题还要算他在多少个子串里出现过,那怎么办?

还是上面那个字符串

0110101

如果\(pos=4\),他前面的符合条件的\(start\)有\(\{1, 4\}\).

如果要算每一对\(start\)和\(pos\)的贡献,我们可以知道是\((start+1)*(len-pos)\),

那么要一次性算多对\(start\)和\(pos\),动用小学学过的乘法分配率

\[(start_1+1)*(len-pos) + (start_2+1)*(len-pos)+...\\ =(start_1+1 + start_2+1 + ...)*(len-pos) \]

所以对于每一个\(pos\), 只要记录下所有小于\(pos\)的\(start\).

参考上面记录\(cnt0\)和\(cnt1\)的方法,我们就可\(O(n)\)算出答案了.

• \(cnt0\):如果一个子串\(S[0,start), start\in[0,pos]\),里面包含偶数个\(1\),那么cnt+=start+1

• \(cnt1\):如果一个子串\(S[0,start), start\in[0,pos]\),里面包含奇数个\(1\),那么cnt+=start+1

丑代码如下,我写的时候脑子一片浆糊,但是我懒得再写一个了(反正懂的都懂.

#include <stdio.h>
#include <string.h>

#define maxn (100000+100)
#define p (998244353)

long long cnt[2];
char str[maxn];

int main()
{
    int n;
    int i;
    long long ans, pre1;
    while (scanf("%d", &n) != EOF)
    {
        scanf("%s", str+1);
        ans = pre1 = 0;
        cnt[0] = 1; cnt[1] = 0;

        for (i = 1; i <= n; ++i)
        {
            pre1 += (str[i] == '1');
            ans = (ans + cnt[!(pre1%2)]*(n-i+1) % p) % p;
            cnt[pre1%2] = (cnt[pre1%2] + i + 1) % p;
        }
        printf("%lld\n", ans);
    }
}