提出 #67007456

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <atcoder/all>
using namespace std;

using mint = atcoder::modint998244353;

struct trie {
    using ar = array<int, 2>;
    vector<ar> pos;
    ar def;
    int now_sz;
    vector<int> cnt_node;
    vector<mint> cnt_ok;
    vector<bool> is_terminated;
    trie() = default;
    trie(int len) {
        pos.reserve(len + 1);
        cnt_ok.reserve(len + 1);
        cnt_node.reserve(len + 1);
        is_terminated.reserve(len + 1);
        def.fill(-1);
        now_sz = 0;
        make_node();
    }
    int make_node() {
        pos.push_back(def);
        cnt_ok.push_back(0);
        cnt_node.push_back(0);
        is_terminated.push_back(false);
        return now_sz++;
    }
    void add(string &s) {
        vector<int> idx = {0};
        idx.reserve(s.size());
        int now = 0;
        for(int i = 0; i < (int)s.size(); i++) {
            

            cnt_node[now]++;

            int d = s[i] - 'A';
            int &nx = pos[now][d];
            if (nx == -1)
                nx = make_node();
            
            if (i == (int)s.size() - 1)
                is_terminated[nx] = true;

            now = nx;
            idx.push_back(now);
        }

        // 逆順にcntを更新したい
        reverse(idx.begin(), idx.end());
        for (int i = 0; i < (int)idx.size(); i++) {
            int j = idx[i];

            mint tmp = 1;
            // そこで終わるものがない場合
            // 両方のノードでいい感じに終わってもらう必要がある
            for (int d = 0; d < 2; d++) {
                if (pos[j][d] == -1) 
                    tmp *= 0;
                else 
                    tmp *= cnt_ok[pos[j][d]];
            }
            // そこで終わるものがあって採用する場合
            // 下のノードはどう選んでもよい
            if (is_terminated[j]) {
                tmp += mint(2).pow(cnt_node[j]);
            }
                
            cnt_ok[j] = tmp;

            // cout << j << ' ';
            // cout << cnt_ok[j].val() << ' ';
        }
        // cout << endl;
    }
};

int main() {
    int N;
    cin >> N;
    vector<string> S(N);
    for (int i = 0; i < N; i++) cin >> S[i];

    trie tr(1'000'000);
    for (int i = 0; i < N; i++) {
        tr.add(S[i]);

        cout << tr.cnt_ok[0].val() << endl;
    }
    return 0;
}

提出情報

ジャッジ結果