寻找 520

根据题意，我们需要考虑所有位置不同的 520 子序列的位置。根据分数我们有下面几种做法：

20 分的做法

由于至多只有 5 个问号，我们可以 枚举这些位置的取值然后从每一个位置出发 DFS 搜索找答案并去重即可。令 为 ? 的个数，则复杂度为 。

50 分的做法

现在整个字符串的长度有 ， 的 DFS 显然是无法承受的。我们来考虑怎么优化这个 DFS。

我们考虑枚举 2 的位置，观察到对于每个 2，只有它前面的 5 和后面的 0 参与到答案的贡献来，而后面的 5 和前面 0 没有任何贡献。这就提示我们先对整个序列扫一遍，计算 5 和 0 个数的前缀和（注意有了 之后，我们计算区间内的和可以简单计算为 ），然后再扫一遍，根据 2 进行计数即可。

所以我们只需要枚举 ? 处的字符分别跑一遍上面的计数过程然后加起来就有答案了，整体复杂度 。

100 分的做法

我们考虑第二种做法，容易注意到，随着 2 的位置的不同，我们枚举出来的 520 子串是不重不漏的。这就提示我们小幅修改上面的 40 分做法就有新的答案：我们扫第一遍统计的时候，把 ? 当做 5 和 0 也统计进前缀和中，然后第二遍枚举的时候，当前字符为 2 或者 ? 都统计进答案就可以了。复杂度 ，实现的时候注意一下区间边界，统计不要有重复。

C++ 参考代码：

class Solution {
  using ll = long long;
  const static int SIZE = 1e6 + 10;
  const static int MOD = 998244353;

  int fives[SIZE], zeros[SIZE];

public:
  /**
   * 寻找所有的 520 子序列
   * @param S string字符串 牛牛准备的数字字符串
   * @return int整型
   */
  int findOccurrences(string S) {
    int n = S.size();

    for (int i = 1; i <= n; i++) {
      fives[i] = fives[i - 1];
      zeros[i] = zeros[i - 1];
      if (S[i - 1] == '5') {
        fives[i]++;
      } else if (S[i - 1] == '0') {
        zeros[i]++;
      } else if (S[i - 1] == '?') {
        fives[i]++;
        zeros[i]++;
      }
    }

    ll ans = 0;

    for (int i = 1; i <= n; i++) {
      if (S[i - 1] == '2' || S[i - 1] == '?') {
        ans = (ans + 1LL * fives[i - 1] * (zeros[n] - zeros[i]) % MOD) % MOD;
      }
    }

    return ans;
  }
};