Submission #703138

#	Time	Username	Problem	Language	Result	Execution time	Memory
703138		Cyanmond	Cubeword (CEOI19_cubeword)	C++17	84 / 100	1193 ms	138844 KiB

cubeword

#include <bits/stdc++.h>

using i64 = long long;
constexpr int L = 8;
constexpr i64 mod = 998244353;

/*
value of C
subtask 1 : 6
subtask 2 : 16
subtask 3 : 32
subtask 4 : 62
*/

int main() {
    int N;
    std::cin >> N;
    std::vector<std::string> words(N);
    for (auto &e : words) {
        std::cin >> e;
        auto b = e;
        std::reverse(b.begin(), b.end());
        if (e > b) {
            e = b;
        }
    }
    std::sort(words.begin(), words.end());
    words.erase(std::unique(words.begin(), words.end()), words.end());
    N = (int)words.size();

    std::vector<std::vector<int>> W(N);
    std::vector<char> chars;
    for (const auto &e : words) {
        for (const auto c : e) {
            chars.push_back(c);
        }
    }
    std::sort(chars.begin(), chars.end());
    chars.erase(std::unique(chars.begin(), chars.end()), chars.end());
    for (int i = 0; i < N; ++i) {
        for (const auto e : words[i]) {
            W[i].push_back((int)(std::lower_bound(chars.begin(), chars.end(), e) - chars.begin()));
        }
    }
    const int C = chars.size();
    std::array<std::vector<std::vector<i64>>, L> U;
    for (auto &vec : U) {
        vec.resize(C);
        for (auto &vec2 : vec) {
            vec2.assign(C, 0);
        }
    }
    for (int i = 0; i < N; ++i) {
        const int a = (int)W[i].size();
        ++U[a - 3][W[i][0]][W[i][a - 1]];
        auto w2 = W[i];
        std::reverse(w2.begin(), w2.end());
        if (W[i] != w2) {
            ++U[a - 3][w2[0]][w2[a - 1]];
        }
    }

    std::vector memo(C, std::vector(C, std::vector(C, std::vector(C, -1ll))));
    std::vector mul(C, std::vector(C, std::vector(C, 0ll)));
    auto solve = [&](std::vector<std::vector<i64>> V) -> i64 {
        // C^8
        for (auto &vecss : memo) {
            for (auto &vecs : vecss) {
                for (auto &vec : vecs) {
                    std::fill(vec.begin(), vec.end(), -1);
                }
            }
        }

        for (int a = 0; a < C; ++a) {
            for (int b = 0; b < C; ++b) {
                for (int c = 0; c < C; ++c) {
                    if (not(a <= b and b <= c)) {
                        int na = a, nb = b, nc = c;
                        if (na > nb) std::swap(na, nb);
                        if (na > nc) std::swap(na, nc);
                        if (nb > nc) std::swap(nb, nc);
                        mul[a][b][c] = mul[na][nb][nc];
                        continue;
                    }
                    i64 s = 0;
                    for (int i = 0; i < C; ++i) {
                        i64 p = V[a][i] * V[b][i] * V[c][i];
                        s += p;
                        s %= mod;
                    }
                    mul[a][b][c] = s;
                }
            }
        }
        auto calc = [&](int a, int b, int c, int d) -> i64 {
            i64 ret = mul[a][b][c];
            ret *= mul[a][b][d];
            ret %= mod;
            ret *= mul[a][c][d];
            ret %= mod;
            ret *= mul[b][c][d];
            ret %= mod;
            return ret;
        };
        i64 res = 0;
        for (int a = 0; a < C; ++a) {
            for (int b = 0; b < C; ++b) {
                for (int c = 0; c < C; ++c) {
                    for (int d = 0; d < C; ++d) {
                        res += calc(a, b, c, d);
                        res %= mod;
                    }
                }
            }
        }
        return res;
    };
    i64 answer = 0;
    for (const auto &e : U) {
        answer += solve(e);
        answer %= mod;
    }
    std::cout << answer << std::endl;
}

• Subtask 1: 21 / 21
• Subtask 2: 29 / 29
• Subtask 3: 34 / 34
• Subtask 4: 0 / 16