Submission #703136

#	Time	Username	Problem	Language	Result	Execution time	Memory
703136		Cyanmond	Cubeword (CEOI19_cubeword)	C++17	84 / 100	1176 ms	138856 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))));
    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);
                }
            }
        }

        std::vector mul(C, std::vector(C, std::vector(C, 0ll)));
        for (int a = 0; a < C; ++a) {
            for (int b = 0; b < C; ++b) {
                for (int c = 0; c < C; ++c) {
                    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 = [&](const std::array<int, 4> &cList) -> i64 {
            i64 ret = mul[cList[0]][cList[1]][cList[2]];
            ret *= mul[cList[0]][cList[1]][cList[3]];
            ret %= mod;
            ret *= mul[cList[0]][cList[2]][cList[3]];
            ret %= mod;
            ret *= mul[cList[1]][cList[2]][cList[3]];
            ret %= mod;
            return memo[cList[0]][cList[1]][cList[2]][cList[3]] = 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) {
                        std::array<int, 4> list = {{a, b, c, d}};
                        std::sort(list.begin(), list.end());
                        if (memo[list[0]][list[1]][list[2]][list[3]] != -1) {
                            res += memo[list[0]][list[1]][list[2]][list[3]];
                        } else {
                            res += calc(list);
                        }
                        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