题目大意

你和对手进行乒乓球比赛，你们原本进行了局比赛，代表你赢下了第局，代表你输掉了第局。

现在我可以操控这个比赛规则，让游戏赛制变成在赢下球制，也就是我在赢下球后，如果和对手比分差值大于等于我就拿下一个小分，否则就是对手拿下一个小分，如果差值为或者那么接着进行下一局，那么我在球赛制下，进行完局比赛我能赢得的小分用表示。

题目求

Solution

考点：预处理模拟题

首先我们可以预处理出从这些位置里面有多少个和多少个，这样用前缀和的形式就可以找到任意区间内和的数量。

并且我们可以知道第个出现的下标在哪里，以及第个出现的下标在哪里。

那么当我们枚举这个球赛制的时候，我们就可以知道上一次加小分的位置在哪里，从这个位置往后个就是我下一次赢球的最小下标，同理可以找到对手赢球的最小下标。

将这两个下标取之后局面就会出现两种；

  1. 要么有人已经拿下了这一个小分，那么直接看下是不是我赢下了这局比赛就行。
  2. 要么两人差距为，那么这时候再看下一局是谁赢下，如果比完下一局比分差值为了，同理统计下是不是我赢下了这局比赛，如果比完差值为了，我们就不能简单的再慢慢一步步往后挪，我们要预处理一个平局数组，找到当第局比赛平局的时候下一次分出胜负在那个局面下，用这个数组跳跃查找就行了。这个数组预处理也很容易，只需要倒序的处理局比赛的情况即可。

这样我们发现每次枚举球赛制的话最小往后移动步，那么总的移动次数大概就是

时间复杂度就是

#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
const int N = 1e6 + 7;
ll n, m;
char s[N];
int cntw[N], cntl[N];
int posw[N << 1], posl[N << 1];

int tiebreak[N];

int solve() {
    n = read();
    scanf("%s", s + 1);

    ms(posw,0x3f);ms(posl,0x3f);
    for (int i = 1; i <= n; ++i) {
        cntw[i] = cntw[i - 1];
        cntl[i] = cntl[i - 1];
        if (s[i] == 'W') {
            ++cntw[i];
            posw[cntw[i]] = i;
        }
        else {
            ++cntl[i];
            posl[cntl[i]] = i;
        }
    }

    tiebreak[n - 1] = tiebreak[n] = n + 1; // 平局数组
    for (int i = n - 2; i >= 1; --i) {
        tiebreak[i] = s[i + 1] == s[i + 2] ? i + 2 : tiebreak[i + 2];
    }

    int res = 0, xs = 1;

    for (int i = 1; i <= n; ++i) {
        int l = 0, r = 0;
        int cnt = 0;
        while (l < n) {
            int W = posw[cntw[r] + i];
            int L = posl[cntl[r] + i];
            r = min(L, W);
            if (r > n)    break;

            if (abs((cntw[r] - cntw[l]) - (cntl[r] - cntl[l])) >= 2) {
                if (cntw[r] - cntw[l] > cntl[r] - cntl[l])
                    ++cnt;
                l = r;
                continue;
            }

            // 之前的r一定有人领先1分
            ++r; // 要么平局 要么赢下
            if (r > n)    break;

            if (abs((cntw[r] - cntw[l]) - (cntl[r] - cntl[l])) >= 2) {
                if (cntw[r] - cntw[l] > cntl[r] - cntl[l])
                    ++cnt;
                l = r;
                continue;
            }

            r = tiebreak[r];
            if (r > n)    break;
            if (cntw[r] - cntw[l] > cntl[r] - cntl[l])
                ++cnt;
            l = r;
        }
        res = (res + cnt * xs) % MOD;
        xs = xs * (n + 1) % MOD;
    }

    print(res);


    return 1;
}