Submission #19718608


Source Code Expand

Copy
#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

Submission Time
Task C - Block Game
User chiara_kyokkou
Language C++ (GCC 9.2.1)
Score 1000
Code Size 2636 Byte
Status AC
Exec Time 503 ms
Memory 219064 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 2
AC × 22
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt AC 490 ms 215112 KB
001.txt AC 503 ms 214988 KB
002.txt AC 225 ms 215216 KB
003.txt AC 252 ms 219064 KB
004.txt AC 407 ms 215108 KB
005.txt AC 405 ms 215120 KB
006.txt AC 406 ms 215216 KB
007.txt AC 406 ms 214984 KB
008.txt AC 405 ms 215036 KB
009.txt AC 254 ms 216504 KB
010.txt AC 177 ms 99928 KB
011.txt AC 17 ms 8928 KB
012.txt AC 197 ms 119576 KB
013.txt AC 345 ms 205744 KB
014.txt AC 318 ms 191624 KB
015.txt AC 396 ms 215124 KB
016.txt AC 371 ms 215140 KB
017.txt AC 367 ms 215104 KB
018.txt AC 355 ms 215212 KB
019.txt AC 359 ms 215160 KB
example0.txt AC 2 ms 3520 KB
example1.txt AC 3 ms 3632 KB