Submission #69382266

---

Source Code Expand

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<class T>
using vec = vector<T>;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KoRoVa
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 1e6 + 11, inf = 1000111222;


const int mod = 998244353;


inline void inc(int &x, int y) {
    x += y;
    if (x >= mod) {
        x -= mod;
    }
}

inline void dec(int &x, int y) {
    x -= y;
    if (x < 0) {
        x += mod;
    }
}

inline int neg (int x) {
    return x ? mod - x : 0;
}

inline int mul(int x, int y) {
    return (1LL * x * y) % mod;
}

int power(int x, int y) {
    if (y < 0) {
        y += mod - 1;
    }
    if (y == 0) {
        return 1;
    }
    if (y % 2 == 0) {
        return power(mul(x, x), y / 2);
    }
    return mul(x, power(x, y - 1));
}

inline int inv(int x) {
    return power(x, mod - 2);
}


// new mint part


inline int divide (int x, int y) {
    return mul(x, inv(y));
}

struct mint {
#define oper_apply(op, f) mint& operator op (const mint &x) {f(val, x.val); return *this;}
#define oper_apply_const(op, f) mint operator op (const mint &x) const {mint tmp = *this; f(tmp.val, x.val); return tmp;}
#define oper_return(op, f) mint& operator op (const mint &x) {val = f(val, x.val); return *this;}
#define oper_return_const(op, f) mint operator op (const mint &x) const {return mint(f(val, x.val));}

    int val;

    mint(int x = 0) : val(x) {}

    oper_apply(+=, inc);
    oper_apply_const(+, inc);
    oper_apply(-=, dec);
    oper_apply_const(-, dec);
    oper_return(*=, mul);
    oper_return_const(*, mul);
    oper_return(/=, divide);
    oper_return_const(/, divide);
    oper_return(^=, power);
    oper_return_const(^, power);
};

const int max_f = 11;
const int max_rf = max_f;
static_assert(max_f >= 1 && max_rf >= 1);

mint f[max_f], rf[max_rf];

bool frf_calculated = []() {
    f[0] = 1;
    for (int i = 1; i < max_f; ++i) {
        f[i] = f[i - 1] * mint(i);
    }
    mint x = f[min(max_f, max_rf) - 1];
    for (int i = max_f; i < max_rf; ++i) {
        x *= mint(i);
    }
    rf[max_rf - 1] = inv(x.val);
    for (int i = max_rf - 2; i >= 0; --i) {
        rf[i] = rf[i + 1] * mint(i + 1);
    }
    return true;
}();

inline mint A (int n, int k) {
    if (k < 0 || k > n) return 0;
    return f[n] * rf[n - k];
}

inline mint C (int n, int k) {
    if (k < 0 || k > n) return 0;
    return A(n, k) * rf[k];
}


struct node {
    int to[2];
    mint dp;
    int cnt, in;
    node () : to(), dp(0), cnt(0), in(0) {}
};

node t[max_n];

int all = 1;

mint st[max_n];


inline void upd (int v) {
    t[v].dp = 0;
    if (t[v].to[0] && t[v].to[1]) {
        t[v].dp += t[t[v].to[0]].dp * t[t[v].to[1]].dp;
    }
    t[v].dp += (st[t[v].cnt] - 1) * st[t[v].in - t[v].cnt];
}


inline void add (string &s, int pos, int v = 0) {
    ++t[v].in;
    if (pos == len(s)) {
        ++t[v].cnt;

        upd(v);

        return;
    }
    int to = s[pos] == 'B';
    if (!t[v].to[to]) {
        t[v].to[to] = all++;
    }
    add(s, pos + 1, t[v].to[to]);
    upd(v);
}


int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    st[0] = 1;
    for (int i = 1; i < max_n; i++) {
        st[i] = st[i - 1] * 2;
    }

    int n;
    cin >> n;
    string s;
    for (int i = 0; i < n; i++) {
        cin >> s;
        add(s, 0);
        cout << t[0].dp.val << '\n';
    }
}

/*
KoRoVa!
*/

Submission Info

Judge Result