Overview

Find the number of ways to replace each C with A or B such that the resulting string does not contain AA. We use dynamic programming (DP), processing the characters from left to right and branching based on whether the last character is A or B.

Analysis

Trying all replacements is too slow

If there are \(K\) occurrences of C, there are \(2^K\) possible ways to replace them. An approach that enumerates all of them to check whether they contain AA will not run in time, since \(N\) can be up to \(2 \times 10^6\).

Only the immediately preceding character matters

Consider appending the next character to the end of a string that already satisfies the condition.

• If we append A, the immediately preceding character must be B.
• If we append B, the immediately preceding character can be either A or B.

In other words, to determine whether the next character can be appended, we only need the last character, not the entire string up to that point.

Therefore, we can count the valid replacements by dividing them into those ending with A and those ending with B.

Algorithm

DP State

After processing some prefix of characters, we maintain the following two values. All values are computed modulo \(998244353\).

• dpA: The number of valid replacements for the processed prefix that end with A
• dpB: The number of valid replacements for the processed prefix that end with B

Initialization

Before processing any characters, we initialize:

• dpA = 0
• dpB = 1

There is \(1\) way to form an empty string. Since the first character can be either A or B, we can consider that there is a virtual B immediately before the string and assign this \(1\) way to dpB.

Transitions

Let the current character be c, and let the values after processing be nextA and nextB.

Placing A at the current position

We can place A if c is A or C. However, if the preceding character is A, it forms AA, so we can only transition from cases where the string ends with B.

• If c != 'B', then \(\mathrm{nextA} = \mathrm{dpB}\)
• Otherwise, \(\mathrm{nextA} = 0\)

Placing B at the current position

We can place B if c is B or C. There is no restriction on the preceding character.

• If c != 'A', then \(\mathrm{nextB} = (\mathrm{dpA} + \mathrm{dpB}) \bmod 998244353\)
• Otherwise, \(\mathrm{nextB} = 0\)

After computing both values, update dpA and dpB with nextA and nextB, respectively.

These transitions count all ways to append characters without creating a new AA. Moreover, since the cases of appending A and appending B are mutually exclusive, each replacement is counted exactly once.

Concrete Example

Consider the case where \(S = \texttt{CCA}\).

Processed Prefix	dpA	dpB
Empty string	\(0\)	\(1\)
C	\(1\)	\(1\)
CC	\(1\)	\(2\)
CCA	\(2\)	\(0\)

Up to CC, the string ending in A is BA, and those ending in B are AB and BB.

The final A can only be appended to strings ending in B, so there are \(2\) completed strings: ABA and BBA.

Answer

After processing all characters, we sum the cases ending in A and ending in B.

The answer is \((\mathrm{dpA} + \mathrm{dpB}) \bmod 998244353\). If no valid replacement exists, both will be \(0\), and the answer will be \(0\) as well.

Complexity

• Time Complexity: \(O(N)\)
  We perform a constant number of operations for each character.
• Space Complexity: \(O(N)\)
  In the provided code, \(O(N)\) space is used to store the input string. The additional space for the DP itself is \(O(1)\).

Implementation Notes

• Compute both transitions using the values before the update.
  If you overwrite dpA first, the updated value will mistakenly be used when computing nextB. As in the provided code, prepare nextA and nextB before updating.

• Always keep each state less than \(998244353\).
  Since dpA + dpB is at most \(2 \times (998244353 - 1)\), the modulo can be obtained by subtracting the modulus at most once if the sum is greater than or equal to the modulus. This sum also fits within the range of a signed \(32\)-bit integer in C++.

• There is no need to detect fixed AA separately.
  Processing an A immediately after an A makes both dpA and dpB equal to \(0\), so impossible cases are correctly handled by the DP alone.

  Source Code

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    string S;
    cin >> N >> S;

    constexpr int MOD = 998244353;
    int dpA = 0, dpB = 1;

    for (char c : S) {
        int nextA = (c != 'B') ? dpB : 0;
        int nextB = 0;
        if (c != 'A') {
            nextB = dpA + dpB;
            if (nextB >= MOD) nextB -= MOD;
        }
        dpA = nextA;
        dpB = nextB;
    }

    int answer = dpA + dpB;
    if (answer >= MOD) answer -= MOD;
    cout << answer << '\n';

    return 0;
}

---

This editorial was generated by gpt-6-astra-medium.