Submission #19718608

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

template<uint_fast64_t Modulus = MOD>
struct Modint {
  using u64 = uint_fast64_t;
  u64 a;

  constexpr Modint(const u64 x = 0) noexcept : a(x % Modulus) {}

  constexpr Modint operator+(const Modint rhs) const noexcept {
    return Modint(*this) += rhs;
  }
  constexpr Modint operator-(const Modint rhs) const noexcept {
    return Modint(*this) -= rhs;
  }
  constexpr Modint operator*(const Modint rhs) const noexcept {
    return Modint(*this) *= rhs;
  }
  constexpr Modint operator/(const Modint rhs) const noexcept {
    return Modint(*this) /= rhs;
  }

  constexpr Modint &operator+=(const Modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) a -= Modulus;
    return *this;
  }
  constexpr Modint &operator-=(const Modint rhs) noexcept {
    if (a < rhs.a) a += Modulus;
    a -= rhs.a;
    return *this;
  }
  constexpr Modint &operator*=(const Modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr Modint &operator/=(Modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp & 1) *this *= rhs;
      rhs *= rhs;
      exp >>= 1;
    }
    return *this;
  }

  Modint pow(u64 t) const {
    if (!t) return 1;
    Modint x = pow(t>>1);
    x *= x;
    if (t&1) x *= *this;
    return x;
  }

  explicit operator bool() const {
    return a;
  }

  friend ostream &operator<<(ostream &os, const Modint &m) {
    return os << m.a;
  }
};

using mint = Modint<>;

void solve() {
  string s; cin >> s;
  int n = s.size();

  vector<int> b;
  for(int i=0; i<n; ++i) {
    if(s[i] == 'B') {
      b.emplace_back(i);
    }
  }
  b.emplace_back(n);

  vector<vector<mint>> imos(n+3, vector<mint>(22, 0));
  imos[0][21] = 1;

  int k = 0;
  mint ans = 0;

  for(int i=0; i<n; ++i) {
    for(int j=0; j<22; ++j) {
      imos[i+1][j] += imos[i][j];
    }
    if(s[i] != 'S') {
      if(s[i] == 'B') {
        ++k;
      } else {
        ans *= 2;
      }
      ans += imos[i+1][0];
      mint sum = accumulate(begin(imos[i+1]) + 1, end(imos[i+1]), mint(0));
      for(int j=0; ; ++j) {
        imos[i+2 + ((1<<j)>>1)][j] += sum;
        if(i+1 + (1<<j) > b[k]) break;
        sum -= imos[i+1][j+1];
        imos[i+2 + (1<<j)][j] -= sum;
      }
      if(s[i] == 'B') {
        imos[i+1].assign(22, 0);
      }
    }
  }

  cout << ans << endl;
}

signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  solve();
  return 0;
}

Submission Info

Judge Result