Submission #953615

#	Time	Username	Problem	Language	Result	Execution time	Memory
953615		LucaIlie	Cubeword (CEOI19_cubeword)	C++17	84 / 100	1115 ms	16552 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

const int MAX_ID = 62;
const int MIN_LEN = 3;
const int MAX_LEN = 10;
const int MOD = 998244353;
unordered_set<string> s[MAX_LEN + 1];
unordered_map<char, int> id;
int m;
int coef[MAX_ID][MAX_ID], prod[MAX_ID][MAX_ID][MAX_ID];

int solve() {
    int ans = 0;

    for ( int a = 0; a < m; a++ ) {
        for ( int b = 0; b < m; b++ ) {
            for ( int c = 0; c < m; c++ ) {
                prod[a][b][c] = 0;
                for ( int i = 0; i < m; i++ )
                    prod[a][b][c] = (prod[a][b][c] + (long long)coef[a][i] * coef[b][i] % MOD * coef[c][i]) % MOD;
            }
        }
    }


    for ( int a = 0; a < m; a++ ) {
        for ( int b = 0; b < m; b++ ) {
            for ( int c = 0; c < m; c++ ) {
                for ( int d = 0; d < m; d++ )
                    ans = (ans + prod[a][b][c] * (long long)prod[a][b][d] % MOD * prod[a][c][d] % MOD * prod[b][c][d]) % MOD;
            }
        }
    }

    return ans;
}

int main() {
    cin.tie( NULL );
    ios_base::sync_with_stdio( false );
    
    int n;

    cin >> n;
    for ( int i = 0; i < n; i++ ) {
        string t;
        cin >> t;
        s[t.size()].insert( t );
        reverse( t.begin(), t.end() );
        s[t.size()].insert( t );
        for ( int i = 0; i < t.size(); i++ )
            id[t[i]] = 1;
    }

    m = 0;
    for ( auto p: id )
        id[p.first] = m++;

    int ans = 0;
    for ( int l = MIN_LEN; l <= MAX_LEN; l++ ) {
        if ( s[l].size() == 0 )
            continue;

        for ( int i = 0; i < m; i++ ) {
            for ( int j = 0; j < m; j++ )
                coef[i][j] = 0;
        }
        for ( string t: s[l] )
            coef[id[t[0]]][id[t.back()]]++;

        ans = (ans + solve()) % MOD;
    }

    cout << ans;

    return 0;
}

Compilation message (stderr)

cubeword.cpp: In function 'int main()':
cubeword.cpp:53:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for ( int i = 0; i < t.size(); i++ )
      |                          ~~^~~~~~~~~~

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