Submission #1276839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276839		Davdav1232	Cubeword (CEOI19_cubeword)	C++20	100 / 100	316 ms	12084 KiB

cubeword

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef __int128_t lll;
ll MOD=998244353;

int main(){
    int n; cin>>n;
    lll num=62;
    vector<vector<vector<ll>>> words(8, vector<vector<ll>>(num, vector<ll>(num, 0)));
    map<char, ll> l;
    for(ll i='a'-'a'; i<='z'-'a'; i++){
        l[(i+'a')]=i;
    }
    for(ll i='A'-'A'; i<='Z'-'A'; i++){
        l[i+'A']=i+26;
    }
    l['0']=52;
    l['1']=53;
    l['2']=54;
    l['3']=55;
    l['4']=56;
    l['5']=57;
    l['6']=58;
    l['7']=59;
    l['8']=60;
    l['9']=61;

    set<ll> ss; 
    for(int i=0; i<n; i++){
        string s; cin>>s;
        ll a_s=0;
        ll curr_num=1;
        for(int i=0; i<s.size(); i++){
            a_s+=curr_num * (l[s[i]]+1);
            curr_num*=(num+1);
        }
        bool e = ss.insert(a_s).second;
        if(e) words[s.size()-3][l[s[0]]][l[s[s.size()-1]]]++;
 
        reverse(s.begin(), s.end());
        a_s=0;
        curr_num=1;
        for(int i=0; i<s.size(); i++){
            a_s+=curr_num * (l[s[i]]+1);
            curr_num*=(num+1);
        }
        e = ss.insert(a_s).second;  
        if(e) words[s.size()-3][l[s[0]]][l[s[s.size()-1]]]++;
    }
    ll ans=0;
    vector<ll> fact(5);
    fact[0]=1;
    fact[1]=1;
    fact[2]=2;
    fact[3]=6;
    fact[4]=24;
    for(int i=0; i<8; i++){
        //ok now choose 4 letters
        vector<vector<vector<ll>>> e(num, vector<vector<ll>> (num, vector<ll> (num, 0)));
        for(int a=0; a<num; a++){
            for(int b=a; b<num; b++){
                for(int c=b; c<num; c++){
                    for(int d=0; d<num; d++){
                        e[a][b][c]+=words[i][a][d]*words[i][b][d]*words[i][c][d];
                        e[a][b][c]%=MOD;
                    }
                }
            }
        }
        for(int a=0; a<num; a++){
            for(int b=a; b<num; b++){
                for(int c=b; c<num; c++){
                    for(int d=c; d<num; d++){
                        ll mul = 24;
                        if (a == d) mul = 1; 
                        else if (a == c || b == d) mul = 4;
                        else if (a == b && c == d) mul = 6;
                        else if (a == b || b == c || c == d) mul = 12;

                        ll add=e[a][b][c]*e[b][c][d];
                        add%=MOD;
                        add*=e[a][c][d];
                        add%=MOD;
                        add*=e[a][b][d];
                        add%=MOD;
                        add*=mul;
                        add%=MOD;
                        
                        
                        ans+=add;
                        ans%=MOD;
                    }
                }
            }
        }
    }
    cout<<ans;



    return 0;
}

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