Submission #1038844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038844		mbalsells	Cubeword (CEOI19_cubeword)	C++14	100 / 100	1053 ms	19420 KiB

cubeword

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <assert.h>
#include <map>

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');
}

int main (){
    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;
}


/*
3
TURING
SUBMIT
ACCEPT


3
MAN1LA
MAN60S
AN4NAS

*/

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