Submission #1231025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231025		KindaNameless	Cubeword (CEOI19_cubeword)	C++20	100 / 100	422 ms	8856 KiB

cubeword

    #include <bits/stdc++.h>
    using namespace std;

    #define ll long long
    #define ld long double

    const ll MOD = 998244353;

    int id(char c) {
        if('0' <= c && c <= '9') {
            return c - '0';
        }
        if('A' <= c && c <= 'Z') {
            return 10 + c - 'A';
        }
        return 36 + c - 'a';
    }

    ll perm(int a, int b, int c, int d) {
        if(a == b && b == c && c == d) {
            return 1;
        }
        if(a == b && b == c) {
            return 4;
        }
        if(b == c && c == d) {
            return 4;
        }
        if(a == b && c == d) {
            return 6;
        }
        if(a == b) {
            return 12;
        }
        if(b == c) {
            return 12;
        }
        if(c == d) {
            return 12;
        }
        return 24;
    }

    vector<string> inc[11];

    ll calc(int len) {
        if(inc[len].empty()) {
            return 0;
        }

        sort(inc[len].begin(), inc[len].end());
        inc[len].resize(unique(inc[len].begin(), inc[len].end()) - inc[len].begin());

        vector<vector<ll>> direct(62, vector<ll>(62, 0));

        for(string elem : inc[len]) {
            direct[id(elem[0])][id(elem.back())]++;
        }

        vector<vector<vector<ll>>> dp(62, vector<vector<ll>>(62, vector<ll>(62, 0)));

        for(int a = 0; a < 62; ++a){
            for(int b = 0; b < 62; ++b) {
                for(int c = 0; c < 62; ++c) {
                    for(int d = 0; d < 62; ++d) {
                        dp[a][b][c] += direct[a][d] * direct[b][d] % MOD * direct[c][d] % MOD;
                        if(dp[a][b][c] >= MOD)dp[a][b][c] -= MOD;
                    }
                }
            }
        }

        ll answer = 0;
        for(int a = 0; a < 62; ++a) {
            for(int b = a; b < 62; ++b) {
                for(int c = b; c < 62; ++c) {
                    for(int d = c; d < 62; ++d) {
                        answer += perm(a, b, c, d) * dp[a][b][c] % MOD * dp[a][b][d] % MOD * dp[a][c][d] % MOD * dp[b][c][d] % MOD;
                        if(answer >= MOD)answer -= MOD;
                    }
                }
            }
        }

        return answer;
    }

    void solve() {
        int N; cin >> N;

        for(int i = 1; i <= N; ++i) {
            string s; cin >> s;
            inc[(int)s.size()].push_back(s);
            inc[(int)s.size()].push_back(string(s.rbegin(), s.rend()));
        }

        ll answer = 0;
        for(int len = 3; len <= 10; ++len) {
            answer += calc(len);
            if(answer >= MOD)answer -= MOD;
        }

        cout << answer;
    }

    int main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

        int tc = 1; //cin >> tc;

        while(tc--) {
            solve();
        }

        return 0;
    }

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