Submission #1048580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048580		andrey27_sm	Cubeword (CEOI19_cubeword)	C++17	84 / 100	1101 ms	8972 KiB

cubeword

//#pragma GCC optimze("O3,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll mod = 998244353;
ll tmp[62][62][62];
inline ll solve(vector<string> words){
    map<pair<char,char>,set<string>> mp;
    set<char> st;
    for(auto& word : words){
        st.insert(word[0]);
        st.insert(word.back());
        mp[{word[0],word.back()}].insert(word);
        reverse(word.begin(),word.end());
        mp[{word[0],word.back()}].insert(word);
        reverse(word.begin(),word.end());
    }
    vector<int> links(128,-1);
    int n = st.size();
    vector<vector<ll>> indeg(n,vector<ll>(n,0));
    {
        int i = 0;
        for(auto& c : st){
            links[c] = i++;
        }
    }
    for(auto& [k,v] : mp){
        if(v.size() > 0){
            indeg[links[k.first]][links[k.second]]+=v.size();
        }
    }
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                tmp[i][j][k] = 0;
                for(int l = 0; l < n; l++){
                    ll ans1 = (ll)indeg[k][l] * indeg[i][l];
                    ans1%=mod;
                    ans1*=indeg[j][l];
                    ans1%=mod;
                    tmp[i][j][k] = (tmp[i][j][k] + ans1) % mod;
                }
            }
        }
    }
    ll ans = 0;
    for(int i = 0; i < n; i++){ // top
        for(int j = 0; j < n; j++){ // top
            for(int k = 0; k < n; k++){ // bot
                for (int l = 0; l < n; ++l) { // bot
                    ll ans_tmp = tmp[i][j][k]*tmp[i][j][l];
                    ans_tmp%=mod;
                    ans_tmp*=tmp[i][k][l];
                    ans_tmp%=mod;
                    ans_tmp*=tmp[j][k][l];
                    ans_tmp%=mod;
                    ans = (ans + ans_tmp) % mod;
                }
            }
        }
    }
    return ans;
}
inline void solve(){
    int n;
    cin >> n;
    vector<vector<string>> words(11,vector<string>());
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        words[s.size()].push_back(s);
    }
    ll ans = 0;
    for(int i = 1; i <= 10; i++){
        if(words[i].empty()) continue;
        ans = (ans + solve(words[i])) % mod;
    }
    cout << ans << "\n";

}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t--)
        solve();
}

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