Submission #960811

#	Time	Username	Problem	Language	Result	Execution time	Memory
960811		ALTAKEXE	Cubeword (CEOI19_cubeword)	C++17	100 / 100	1051 ms	9040 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;
vector<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()].push_back( t );
        string w = t;
        reverse( w.begin(), w.end() );
        if ( w != t )
            s[t.size()].push_back( w );
        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;
        }
        sort( s[l].begin(), s[l].end() );
        for ( int i = 0; i < s[l].size(); i++ ) {
            if ( i == 0 || s[l][i] != s[l][i - 1])
                coef[id[s[l][i][0]]][id[s[l][i].back()]]++;
        }
 
        ans = (ans + solve()) % MOD;
    }
 
    cout << ans;
 
    return 0;
}

Compilation message (stderr)

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

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