Submission #924820

#	Time	Username	Problem	Language	Result	Execution time	Memory
924820		Camillus	Cubeword (CEOI19_cubeword)	C++17	100 / 100	1084 ms	9588 KiB

cubeword

/// @author Camillus
#include "bits/stdc++.h"
#pragma GCC optimize("O3")

using ll = long long;
using namespace std;

static constexpr ll mod = 998'244'353;

static constexpr int SIGMA = 26 + 26 + 10;
ll cnt2[SIGMA][SIGMA];
ll cnt3[SIGMA][SIGMA][SIGMA];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    map<int, vector<string>> b;

    map<int, int> ord;

    int sigma = 0;

    for (char x = 'a'; x <= 'z'; x++) {
        ord[x] = sigma++;
    }
    
    for (char x = 'A'; x <= 'Z'; x++) {
        ord[x] = sigma++;
    }

    for (char x = '0'; x <= '9'; x++) {
        ord[x] = sigma++;
    }

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;

        b[s.size()].push_back(s);
    }

    ll ans = 0;

    for (const auto &[x, y] : b) {
        memset(cnt2, 0, sizeof(cnt2));
        memset(cnt3, 0, sizeof(cnt3));

        set<string> z;
        for (const string &s : y) {
            string t = s;
            reverse(t.begin(), t.end());
            z.insert(t);
            z.insert(s);
        }

        for (const string &s : z) {
            int a = ord[s.front()];
            int b = ord[s.back()];
            cnt2[a][b] += 1;
        }

        for (int a = 0; a < SIGMA; a++) {
            for (int b = 0; b < SIGMA; b++) {
                for (int c = 0; c < SIGMA; c++) {
                    for (int d = 0; d < SIGMA; d++) {
                        cnt3[a][b][c] += cnt2[a][d] * cnt2[b][d] % mod * cnt2[c][d] % mod;
                        if (cnt3[a][b][c] >= mod) {
                            cnt3[a][b][c] -= mod;
                        }
                    }
                }
            }
        }

        for (int a = 0; a < SIGMA; a++) {
            for (int b = 0; b < SIGMA; b++) {
                for (int c = 0; c < SIGMA; c++) {
                    for (int d = 0; d < SIGMA; d++) {
                        ans += cnt3[a][b][d] * cnt3[a][b][c] % mod * cnt3[c][b][d] % mod * cnt3[a][c][d] % mod;
                        if (ans >= mod) {
                            ans -= mod;
                        }
                    }
                }
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

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