oj.uz

Submission #924819

# Submission time Handle Problem Language Result Execution time Memory
924819 2024-02-09T19:32:09 Z Camillus Cubeword (CEOI19_cubeword) C++17
0 / 100
 1100 ms 7764 KB 
/// @author Camillus
#include "bits/stdc++.h"
#pragma GCC optimize("O3")

using ll = long long;
using namespace std;

struct mint {
    static constexpr int mod = 998'244'353;
    int value = 0;
 
    mint() = default;
    mint(int value) : value(value) {}
 
    mint& operator+=(const mint &other) {
        value += other.value;
        if (value >= mod) {
            value -= mod;
        }
        return *this;
    }
 
    mint operator+(const mint &other) const {
        mint result = *this;
        return result += other;
    }
 
    mint& operator-=(const mint &other) {
        value += mod - other.value;
        if (value >= mod) {
            value -= mod;
        }
        return *this;
    }
 
    mint operator-(const mint &other) const {
        mint result = *this;
        return result -= other;
    }
 
    mint& operator*=(const mint &other) {
        value = 1ll * value * other.value % mod;
        return *this;
    }
 
    mint operator*(const mint &other) const {
        mint result = *this;
        return result *= other;
    }
 
    mint power(int k) const {
        mint result = 1;
        mint current = *this;
 
        while (k) {
            if (k & 1) {
                result *= current;
            }
            current *= current;
            k >>= 1;
        }
 
        return result;
    }
 
    mint& operator/=(const mint &other) {
        return this->operator*=(other.power(mod - 2));
    }
 
    mint operator/(const mint &other) const {
        mint result = *this;
        return result /= other;
    }
 
    bool operator==(const mint &other) const {
        return value == other.value;
    } 
};

static constexpr int SIGMA = 26 + 26 + 10;
mint cnt2[SIGMA][SIGMA];
mint 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);
    }

    mint 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] * cnt2[c][d];
                    }
                }
            }
        }

        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] * cnt3[c][b][d] * cnt3[a][c][d];
                    }
                }
            }
        }
    }

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

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1097 ms 7764 KB Output is correct
2 Execution timed out 1107 ms 7596 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1097 ms 7764 KB Output is correct
2 Execution timed out 1107 ms 7596 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1097 ms 7764 KB Output is correct
2 Execution timed out 1107 ms 7596 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1097 ms 7764 KB Output is correct
2 Execution timed out 1107 ms 7596 KB Time limit exceeded
3 Halted 0 ms 0 KB -