제출 #1103831

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1103831		haianhnguyen08102007	Cubeword (CEOI19_cubeword)	C++17	100 / 100	1035 ms	19404 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef vector <ll> vi;
typedef vector <vi> vvi;
typedef vector <vvi> vvvi;

const int alfa = 1 + ('z' - 'a');
const int ALFA = 2 * alfa + 10;
const ll mod = 998244353;

int char_to_int(char c){
    if (c > 'Z') return c - 'a';
    if (c > '9') return alfa + (c - 'A');
    return 2 * alfa + (c - '0');
}

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

//    freopen("PIZZASHOP.INP", "r", stdin);
//    freopen("PIZZASHOP.OUT", "w", stdout);

    int n;
    cin >> n;

    set <string> S;

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

        S.insert(s);
        reverse(s.begin(), s.end());
        S.insert(s);
    }

    vvvi freq(11, vvi(ALFA, vi(ALFA, 0)));
    for (string s: S){
        freq[s.size()][char_to_int(s.front())][char_to_int(s.back())] += 1;
    }

    ll ans = 0;

    for (int l = 3; l <= 10; ++l){
        vvi curr_freq = freq[l];

        vvvi C(ALFA, vvi(ALFA, vi(ALFA, 0)));

        for (int a = 0; a < ALFA; ++a){
            for (int b = 0; b < ALFA; ++b){
                for (int c = 0; c < ALFA; ++c){
                    for (int d = 0; d < ALFA; ++d){
                        C[a][b][c] += (curr_freq[a][d] * curr_freq[b][d] * curr_freq[c][d]) % mod;
                    }
                    C[a][b][c] %= mod;
                }
            }
        }

        for (int a = 0; a < ALFA; ++a){
            for (int b = 0; b < ALFA; ++b){
                for (int c = 0; c < ALFA; ++c){
                    for (int d = 0; d < ALFA; ++d){
                        ans += (((C[a][b][c] * C[b][c][d]) % mod) * ((C[c][d][a] * C[d][a][b]) % mod)) % mod;
                    }
                    ans %= mod;
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

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