Submission #703131

#	Time	Username	Problem	Language	Result	Execution time	Memory
703131		Cyanmond	Cubeword (CEOI19_cubeword)	C++17	50 / 100	1189 ms	14720 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]];
        }
    }

    auto solve = [&](std::vector<std::vector<i64>> V) -> i64 {
        // C^8
        std::map<std::array<int, 4>, i64> memo;

        auto calc = [&](std::array<int, 4> cList) -> i64 {
            i64 ret = 1;
            for (int x = 0; x < 4; ++x) {
                i64 s = 0;
                for (int i = 0; i < C; ++i) {
                    i64 c = 1;
                    for (int j = 0; j < 4; ++j) {
                        if (x != j) c *= V[cList[j]][i];
                    }
                    s += c;
                    s %= mod;
                }
                ret *= s;
                ret %= mod;
            }
            return memo[cList] = 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.find(list) != memo.end()) {
                            res += memo[list];
                        } 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: 0 / 34
• Subtask 4: 0 / 16