Submission #19000337


Source Code Expand

Copy
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


struct ModInt(int M_) {
  import std.conv : to;
  alias M = M_;
  int x;
  this(ModInt a) { x = a.x; }
  this(long a) { x = cast(int)(a % M); if (x < 0) x += M; }
  ref ModInt opAssign(long a) { return (this = ModInt(a)); }
  ref ModInt opOpAssign(string op)(ModInt a) {
    static if (op == "+") { x += a.x; if (x >= M) x -= M; }
    else static if (op == "-") { x -= a.x; if (x < 0) x += M; }
    else static if (op == "*") { x = cast(int)((cast(long)(x) * a.x) % M); }
    else static if (op == "/") { this *= a.inv(); }
    else static assert(false);
    return this;
  }
  ref ModInt opOpAssign(string op)(long a) {
    static if (op == "^^") {
      if (a < 0) return (this = inv()^^(-a));
      ModInt t2 = this, te = ModInt(1);
      for (long e = a; e > 0; e >>= 1) {
        if (e & 1) te *= t2;
        t2 *= t2;
      }
      x = cast(int)(te.x);
      return this;
    } else return mixin("this " ~ op ~ "= ModInt(a)");
  }
  ModInt inv() const {
    int a = x, b = M, y = 1, z = 0, t;
    for (; ; ) {
      t = a / b; a -= t * b;
      if (a == 0) {
        assert(b == 1 || b == -1);
        return ModInt(b * z);
      }
      y -= t * z;
      t = b / a; b -= t * a;
      if (b == 0) {
        assert(a == 1 || a == -1);
        return ModInt(a * y);
      }
      z -= t * y;
    }
  }
  ModInt opUnary(string op: "-")() const { return ModInt(-x); }
  ModInt opBinary(string op, T)(T a) const {
    return mixin("ModInt(this) " ~ op ~ "= a");
  }
  ModInt opBinaryRight(string op)(long a) const {
    return mixin("ModInt(a) " ~ op ~ "= this");
  }
  bool opCast(T: bool)() const { return (x != 0); }
  string toString() const { return x.to!string; }
}

enum MO = 998244353;
alias Mint = ModInt!MO;

enum E = 20;

void main() {
  try {
    for (; ; ) {
      const S = readToken();
      const N = cast(int)(S.length);
      
      auto nextB = new int[N + 1];
      nextB[N] = N;
      foreach_reverse (i; 0 .. N) {
        nextB[i] = (S[i] == 'B') ? i : nextB[i + 1];
      }
      
      auto dpSum = new Mint[E + 1][N + 1];
      Mint[E + 1] here;
      foreach_reverse (i; 0 .. N) {
        here[] = Mint(0);
        if (S[i] == 'B' || S[i] == '?') {
          if (nextB[i + 1] == N) {
            here[0] += 1;
          }
          foreach (e; 0 .. E) {
            const lb = i + 1 + (1 << e);
            const ub = nextB[i + 1];
            if (lb <= ub) {
              here[e + 1] += dpSum[lb][e] - dpSum[min(ub + 1, N)][e];
            }
          }
        }
        foreach (e; 0 .. E + 1) {
          dpSum[i][e] = here[e] + dpSum[i + 1][e];
        }
        debug {
          writeln(i, ": ", here);
        }
      }
      
      Mint ans;
      if (nextB[0] == N) {
        ans += 1;
      }
      foreach (e; 0 .. E + 1) {
        const ub = nextB[0];
        ans += dpSum[0][e] - dpSum[min(ub + 1, N)][e];
      }
      debug {
        writeln("snuke: ", ans);
      }
      ans = Mint(2)^^(S.count('?')) - ans;
      writeln(ans);
    }
  } catch (EOFException e) {
  }
}

Submission Info

Submission Time
Task C - Block Game
User hos_lyric
Language D (LDC 1.20.1)
Score 1000
Code Size 4319 Byte
Status AC
Exec Time 150 ms
Memory 90232 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 150 ms 90076 KB
001.txt AC 149 ms 90096 KB
002.txt AC 84 ms 89972 KB
003.txt AC 102 ms 90216 KB
004.txt AC 134 ms 90088 KB
005.txt AC 132 ms 90160 KB
006.txt AC 134 ms 89996 KB
007.txt AC 134 ms 90092 KB
008.txt AC 134 ms 90052 KB
009.txt AC 107 ms 89976 KB
010.txt AC 63 ms 42988 KB
011.txt AC 12 ms 5584 KB
012.txt AC 68 ms 50780 KB
013.txt AC 116 ms 86356 KB
014.txt AC 106 ms 80440 KB
015.txt AC 133 ms 90232 KB
016.txt AC 127 ms 90096 KB
017.txt AC 124 ms 90128 KB
018.txt AC 122 ms 90008 KB
019.txt AC 123 ms 89996 KB
example0.txt AC 4 ms 3120 KB
example1.txt AC 3 ms 3124 KB