Problem: weak_typing_ch3 (2021 round1)

**Note: This problem shares similarities with Chapters [1](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-1/problems/A1/) and [2](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-1/problems/A2/). The solution to any chapter may help with solving the others, so please consider reading all of them first.**

Timmy the toddler is training to be a top typist. His teacher has assigned some homework in the form of a list of \(T\) string exercises to be typed, consisting of only the uppercase letters "F", "O", and "X".

Timmy is eating a popsicle on a hot summer afternoon, but still hopes to complete his homework. He would like to hold the popsicle with one hand, and type with the other. Unfortunately, Timmy is still a growing boy, and each of his hands is a tad too small to reach all the way across the keyboard. He can only reach the letters "F" and "X" with his left hand, and the letters "F" and "O" with his right.

Consider a string \(W\) which Timmy must type. Timmy may start typing with any hand of his choice (with the other holding the popsicle). He must then switch hands as necessary to type out the \(|W|\) letters in order, ending on any hand of his choice.

Let \(F(W)\) be the minimum number of times Timmy must switch hands to type such a string \(W\).

Because Timmy's teacher would like to assign longer strings more concisely, he has encoded each exercise in a special way, through a string \(U\) of length \(K\), consisting of only the characters "F", "O", "X", and ".". Consider a string \(S\) which is initially empty and then has \(K\) updates applied to it, one after another. The \(i\)th update is described by the character \(U_i\):

  - If \(U_i\) is "F", "O", or "X", then the single letter \(U_i\) is appended to the end of \(S\).
  - Otherwise, when \(U_i\) is ".", \(S\) is duplicated, with the entire current string \(S\) being appended to the end of itself (for example, if \(S\) = "OX", then \(S\) would become equal to "OXOX" after such an update). The first update is guaranteed to not be of this type.

Let \(G(S)\) be the sum of \(F(W)\) over all substrings \(W\) of the final string \(S\) after all \(K\) updates have been applied to it. Note that there are \(|S|*(|S|+1)/2\) such substrings. Please help Timmy compute the value of \(G(S)\) modulo \(1{,}000{,}000{,}007\).


# Constraints

\(1 \le T \le 70\)
\(1 \le K \le 800{,}000\)
\(U_1 \ne\) "."

Each string \(U\) consists only of the letters "F", "O", "X", and ".".
The sum of \(K\) across all exercises is at most \(4{,}000{,}000\).


# Input

Input begins with an integer \(T\), the number of exercises that Timmy has been assigned. For each exercise, there is first a line containing the single integer \(K\), followed by a second line containing the string \(U\) of length \(K\).


# Output

For the \(i\)th exercise, output a line containing *"Case #i: "* followed by a single integer, the value of \(G(S)\) for the final sequence \(S\), modulo \(1{,}000{,}000{,}007\).


# Sample Explanation

In the first exercise, the final string \(S\) is "XFO". It has \(6\) substrings to consider: "X", "F", "O", "XF", "FO", and "XFO". \(F\) has a value of \(0\) when evaluated on any of the first \(5\) of these, while \(F(``XFO") = 1\), as if Timmy begins with his left hand, he can type all \(3\) letters in order with \(1\) hand switch (for example, by switching to his right hand after typing the first letter). The answer is therefore \((0 + 0 + 0 + 0 + 0 + 1)\) modulo \(1{,}000{,}000{,}007 = 1\).

In the second exercise, the final string \(S\) is "FFFFOFFFF". \(F\) has a value of \(0\) when evaluated on any of its \(45\) substrings.

In the third exercise, \(F\) has a value of \(0\) for \(29\) of the substrings of \(S\), a value of \(1\) for another \(16\) of them, and a value of \(2\) for the remaining \(10\) of them. The answer is therefore \((0 * 29 + 1 * 16 + 2 * 10)\) modulo \(1{,}000{,}000{,}007 = 36\).

In the fourth exercise, the final string \(S\) is "XFOFXFOFXFOFX".

In the fifth exercise, the final string \(S\) consists of "OOXFOX" repeated \(4\) times.


Sample input:
5
3
XFO
8
F..OFFFF
10
FXXFXFOOXF
10
XFOF.XFOFX
8
O.XFOX..


Sample output:
Case #1: 1
Case #2: 0
Case #3: 36
Case #4: 146
Case #5: 1480


Solution: As in Chapter 2, we'll think of \(G(S)\) as being made up of a sum of products based on relevant pairs of "X"s and "O"s (which necessitate hand switches in between typing them). Each such pair of letters at indices \(a\) and \(b\) in \(S\) (such that \(a \lt b\)) contributes an addition of \(a * (|S| - b + 1)\) to \(G(S)\). We'll refer to \(a\) as the pair's \(L\) value, and to \((|S| - b + 1)\) as its \(R\) value.

We'll need a representation of a string \(S\) which allows us to support both types of updates while maintaining the value of \(G(S)\), but without an \(O(|S|)\) representation of the exact full content of \(S\) (as it can grow far too large). Our representation \(Z(S)\) shall consist of the following values (all stored modulo \(1{,}000{,}000{,}007\)):
- \(|S|\)
- \(I_1(S)\) and \(V_1(S)\), the index and value of the first non-"F" letter in \(S\) (if any)
- \(I_2(S)\) and \(V_2(S)\), the index and value of the last non-"F" letter in \(S\) (if any)
- \(P(S)\), the number of relevant letter pairs
- \(L'(S)\), the sum of pairs' \(L\) values
- \(R'(S)\), the sum of pairs' \(R\) values
- \(G(S)\)

Given two strings \(S_1\) and \(S_2\) to concatenate into \(S_1 S_2\), we'll seek an algorithm to compute \(Z(S_1 S_2)\) given \(Z(S_1)\) and \(Z(S_2)\). This will be enough to support both types of updates: duplicating \(S\) is equivalent to concatenating \(S\) and \(S\), while appending a single letter \(c\) to \(S\) is equivalent to concatenating \(S\) and \(c\). Note that \(Z(\)""\()\) and \(Z(c)\) (for any letter \(c\)) are simple to compute.

We can observe that concatenating \(S_1\) and \(S_2\) yields a string with all of the relevant letter pair from each of \(S_1\) and \(S_2\), plus at most one additional pair spanning between the two strings. If we ignore the possibility of that additional pair for now, the values of \(Z(S_1 S_2)\) can otherwise be computed without much trouble:
- \(|S_1 S_2|\) and \(P(S_1 S_2)\) are simply added together from those of \(S_1\) and \(S_2\)
- \(I_1(S_1 S_2)\) and \(V_1(S_1 S_2)\) are inherited from those of either \(S_1\) or \(S_2\) (with \(|S_1|\) added to \(I_1\) in the latter case), with \(I_2\) and \(V_2\) handled similarly
- \(L'(S_1 S_2) = L'(S_1) + L'(S_2) + P(S_2)*|S_1|\), with \(R'\) handled similarly
- \(G(S_1 S_2) = G(S_1) + G(S_2) + L'(S_1)*|S_2| + R'(S_2)*|S_1|\)

If \(V_2(S_1)\) and \(V_1(S_2)\) both exist and differ from one another, then an additional pair between indices \(I_2(S_1)\) and \(|S_1| + I_1(S_2)\) should be accounted for. This involves fairly simply updates to \(P(S_1 S_2)\), \(L'(S_1 S_2)\), \(R'(S_1 S_2)\), and \(G(S_1 S_2)\).

We can follow this process to arrive at \(Z(S)\) for the final string \(S\) (including the value of \(G(S)\)) in \(O(N)\) time.

[See David Harmeyer's solution video here](https://youtu.be/O1giTvqaxzM).


Code: #include <iostream>
#include <utility>
using namespace std;

const int MOD = 1000000007;

struct Seq {
  long long len{0}, ns{0}, sL{0}, sR{0}, ans{0};
  pair<long long, char> p1{-1, 0}, p2{-1, 0};
};

Seq concat(const Seq &A, const Seq &B) {
  Seq S;
  S.len = (A.len + B.len) % MOD;
  S.ns = (A.ns + B.ns) % MOD;
  S.p1 = A.p1.first >= 0 ? A.p1 : make_pair((B.p1.first + A.len) % MOD, B.p1.second);
  S.p2 = B.p2.first >= 0 ? make_pair((B.p2.first + A.len) % MOD, B.p2.second) : A.p2;
  S.sL = (A.sL + B.sL + B.ns*A.len) % MOD;
  S.sR = (A.sR + B.sR + A.ns*B.len) % MOD;
  S.ans = (A.ans + B.ans + A.sL*B.len + B.sR*A.len) % MOD;
  // Check if there's a new switch.
  if (A.p2.first >= 0 && B.p1.first >= 0 && A.p2.second != B.p1.second) {
    S.ns++;
    long long vL = A.p2.first + 1, vR = (B.len - B.p1.first + MOD) % MOD;
    S.sL = (S.sL + vL) % MOD;
    S.sR = (S.sR + vR) % MOD;
    S.ans = (S.ans + vL*vR) % MOD;
  }
  return S;
}

int K;
string U;

int solve() {
  cin >> K >> U;
  Seq S;
  for (int i = 0; i < K; i++) {
    Seq S2;
    if (U[i] == '.') {
      S2 = S;
    } else {
      S2.len = 1;
      if (U[i] != 'F') {
        S2.p1 = S2.p2 = make_pair(0, U[i]);
      }
    }
    S = concat(S, S2);
  }
  return S.ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}